ruby - Rubyを使用した任意精度演算

Question

Rubyはこれをどのように行うのですか？イェルクや他の誰かが舞台裏で何が起こっているのか知っていますか？

残念ながら、私はCをよく知らないのでbignum.c、ほとんど役に立ちません。誰かが（平易な英語で）それが使用している奇跡のアルゴリズムの背後にある理論を説明できるのはちょっと興味がありました。

irb(main):001:0> 999**999

36806348825922326789470084006052186583833823203735320465595962143702560930047223153010387361450517521869134525758989639113039318944796977164583238219236607653663113200177617597793217865870366077846576581183082787698201412402294867197567813172495806442794990281049897327103078771678146741952418004073439899695293083250893411694596612017673512082315195977953685229009037745250223699083945341679064045611647113975154675004860218929102864097057476260018595022613824453018748921161586402113531207791201884463078030746220525280773775767209432069237310103251745951849752401512016516672418981676639724782417539480202822816002710062399887366743579907305461890685546048835142661131063402348904429186051035230191242660848880746231212659020683041378266455426041126637886662665375576362779656908293178564560081623689116814177499326748817170217219107273106921688166829462567949269614897699986871567144087420642721205671737309963971116890119744041659022652419278284289641541461168818739123204832773896582026593409310817205487518824659176087713165789563358657661185727701178249794352294501124843043920129701511946873071236400763937391081195343030947683245323012399675023571078708664107031028872538959513893678471527415042649541619666983267998025343680786418716005458904566402715881795854937449051239905544881914848704936367461166460989003008854959199246636005004256627034833091179548764704594930128661465865007129969565224526608067298992179934250929163533082787426478958730697447232771870430635244592599615561915378391323721271601041029499987756974528735342290344338756274645252286042041668901973291379807377328153357091020520776715712817418487335705083075277790004194325673849906782148842105387086902273869881605981057922100256088299988476325216174756689383517855896114234930446650640237355631870717571086698303531312206832110245782411201496938722547625934287286636355038384072001083290669536055355664754529584996627998083056124296001365452951499511358490905081301519892828320218919461550140343555306014771313976632319574332484804734757547322819849234323149658088505733051094905849052773866269748029358361223313450207818201434719252239144908773857908158579561354719859966127356766244149040186283981782268657311299866303886831497425976603934089402430838345103987467406116053824239280358075823275574931084369419478799155664790709184960070471200337110392696713740812571363139669934373328801425408481937938055517477702084356868992734894948420104259527193263068574761383538543442480702461516184822371598979717815516995112105228514915713769771885044970884333047530144037309461111963136170293634226321938279399689598833170189069368986245902077559943950687000513075042794974707139009525675920342667180337706810974462990976917631952683782436492684473054552464649432182624192510715804056160770636448491097834866938814201683879290292615897935543248361151758860596774539395

score 18 · Accepted Answer

シンプル：一年生以来、あなたと同じようにそれを行います。10を基数で計算しないことを除いて、40億を基数で計算します（そして変更します）。

考えてみてください。私たちの0記数法では、からまでの数しか表現できません9。6+7では、オーバーフローせずにどのように計算できるでしょうか。簡単：実際にはオーバーフローします！の結果をと6+7の間の数値として表すことはできませんが、次の場所にオーバーフローして、との間の2つの数値として表すことができます： 3×10 ⁰ +1× ¹⁰¹。2つの数字を追加する場合は、右から数字で追加し、左にオーバーフロー（「キャリー」）します。2つの数値を乗算する場合は、一方の数値のすべての桁にもう一方の数値を個別に乗算してから、中間結果を合計する必要があります。0909

BigNum演算（これは、数値がネイティブマシンの数値よりも大きいこの種の演算と呼ばれるものです）は、基本的に同じように機能します。ベースが10ではなく、2でもないことを除いて、ネイティブマシンの整数のサイズです。したがって、32ビットマシンでは、ベース232または4294967296になり^ます。

具体的には、Rubyでは、Integer実際には決してインスタンス化されない抽象クラスです。代わりに、2つのサブクラスとがFixnumありBignum、サイズに応じて、数値はそれらの間を自動的に移動します。MRIおよびYARVでは、Fixnumは、マシンのネイティブワードサイズに応じて、31ビットまたは63ビットの符号付き整数（1ビットはタグ付けに使用されます）を保持できます。JRubyでは、Fixnumは、32ビットマシンでも完全な64ビット符号付き整数を保持できます。

最も簡単な操作は、2つの数値を加算することです。そして、YARVのbignum.c+の実装、またはむしろYARVの実装を見ると、従うのはそれほど悪くありません。Cも読めませんが、個々の数字がどのようにループするかははっきりとわかります。bigadd_core

score 2 · Accepted Answer

あなたはのためのソースを読むことができますbignum.c...

非常に高いレベルでは、実装の詳細に立ち入ることなく、sbignumは小学校で行っていたように「手作業で」計算されます。現在、適用できる最適化は確かにたくさんありますが、それがその要点です。

score 2 · Accepted Answer

実装の詳細がわからないので、基本的なBigNumber実装がどのように機能するかについて説明します。

基本的に、CPUの「整数」に依存する代わりに、複数のCPU整数を使用して独自の整数を作成します。arbritraryの精度を保存するために、2ビットがあるとしましょう。したがって、現在の整数は11です。1つ追加します。通常のCPU整数では、これは00にロールオーバーします

ただし、大きな数値の場合、ロールオーバーして「固定」整数幅を維持する代わりに、別のビットを割り当てて加算をシミュレートし、数値が正しい100になるようにします。

紙の上で2進数学を行う方法を調べてみてください。非常にシンプルで、アルゴリズムに変換するのは簡単です。

score 1 · Accepted Answer

2011年1月18日にリリースされたばかりのBeaconautAPICalc2は、bignum算術、暗号分析、および数論研究のための任意精度の整数計算機です......

http://www.beaconaut.com/forums/default.aspx?g=posts&t=13

score 0 · Accepted Answer

Bignumクラスを使用します

irb(main):001:0> (999**999).class
=> Bignum

Rdocはもちろん利用可能です

ruby - Rubyを使用した任意精度演算

5 に答える 5

Related

Reference