5

Ruby 到底是怎么做到的？Jörg 或其他人是否知道幕后发生的事情？

不幸的是，我不太了解 C，所以bignum.c对我帮助不大。我只是有点好奇，有人可以（用简单的英语）解释它使用的任何奇迹算法背后的理论。

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

368063488259223267894700840060521865838338232037353204655959621437025609300472231530103873614505175218691345257589896391130393189447969771645832382192366076536631132001776175977932178658703660778465765811830827876982014124022948671975678131724958064427949902810498973271030787716781467419524180040734398996952930832508934116945966120176735120823151959779536852290090377452502236990839453416790640456116471139751546750048602189291028640970574762600185950226138244530187489211615864021135312077912018844630780307462205252807737757672094320692373101032517459518497524015120165166724189816766397247824175394802028228160027100623998873667435799073054618906855460488351426611310634023489044291860510352301912426608488807462312126590206830413782664554260411266378866626653755763627796569082931785645600816236891168141774993267488171702172191072731069216881668294625679492696148976999868715671440874206427212056717373099639711168901197440416590226524192782842896415414611688187391232048327738965820265934093108172054875188246591760877131657895633586576611857277011782497943522945011248430439201297015119468730712364007639373910811953430309476832453230123996750235710787086641070310288725389595138936784715274150426495416196669832679980253436807864187160054589045664027158817958549374490512399055448819148487049363674611664609890030088549591992466360050042566270348330911795487647045949301286614658650071299695652245266080672989921799342509291635330827874264789587306974472327718704306352445925996155619153783913237212716010410294999877569745287353422903443387562746452522860420416689019732913798073773281533570910205207767157128174184873357050830752777900041943256738499067821488421053870869022738698816059810579221002560882999884763252161747566893835178558961142349304466506402373556318707175710866983035313122068321102457824112014969387225476259342872866363550383840720010832906695360553556647545295849966279980830561242960013654529514995113584909050813015198928283202189194615501403435553060147713139766323195743324848047347575473228198492343231496580885057330510949058490527738662697480293583612233134502078182014347192522391449087738579081585795613547198599661273567662441490401862839817822686573112998663038868314974259766039340894024308383451039874674061160538242392803580758232755749310843694194787991556647907091849600704712003371103926967137408125713631396699343733288014254084819379380555174777020843568689927348949484201042595271932630685747613835385434424807024615161848223715989797178155169951121052285149157137697718850449708843330475301440373094611119631361702936342263219382793996895988331701890693689862459020775599439506870005130750427949747071390095256759203426671803377068109744629909769176319526837824364926844730545524646494321826241925107158040561607706364484910978348669388142016838792902926158979355432483611517588605967745393958061959024834251565197963477521095821435651996730128376734574843289089682710350244222290017891280419782767803785277960834729869249991658417000499998999

4

5 回答 5

18

很简单：从一年级开始，它就和你一样。除了它不以 10 为底进行计算外，它以 40 亿为底（和变化）计算。

想一想：使用我们的数字系统，我们只能表示从0到 的数字9。那么，我们怎样才能在6+7不溢出的情况下进行计算呢？简单：我们确实溢出了！我们不能将 的结果表示为and6+7之间的数字，但我们可以溢出到下一个位置并将其表示为and之间的两个数字：3×10 0 + 1×10 1。如果要添加两个数字，请从右侧按数字添加，然后溢出（“进位”）到左侧。如果要将两个数字相乘，则必须将一个数字的每个数字分别与另一个数字相乘，然后将中间结果相加。0909

BigNum 算术（这就是这种数字大于本机机器数的算术通常被称为）的工作方式基本相同。除了基数不是 10，也不是 2，它是本机机器整数的大小。因此，在 32 位机器上，它将是基数 2 32或 4 294 967 296。

具体来说，在 RubyInteger中实际上是一个从未实例化的抽象类。相反，它有两个子类，Fixnum和Bignum，并且数字会在它们之间自动迁移，具体取决于它们的大小。在 MRI 和 YARV 中，Fixnum 可以保存 31 位或 63 位有符号整数（一位用于标记），具体取决于机器的本机字长。在 JRuby 中，Fixnum 可以保存完整的 64 位有符号整数，即使在 32 位机器上也是如此。

最简单的操作是将两个数字相加。如果您查看YARV 的bignum.c+的实现，或者更确切地说是在其中的实现，那么遵循它并不算太糟糕。我也看不懂 C，但你可以清楚地看到它是如何在单个数字上循环的。bigadd_core

于 2010-05-19T18:18:26.170 回答
2

I don't know of the implementation details so I'll cover how a basic Big Number implementation would work.

Basically instead of relying on CPU "integers" it will create it's own using multiple CPU integers. To store arbritrary precision, well lets say you have 2 bits. So the current integer is 11. You want to add one. In normal CPU integers, this would roll over to 00

But, for big number, instead of rolling over and keeping a "fixed" integer width, it would allocate another bit and simulate an addition so that the number becomes the correct 100.

Try looking up how binary math can be done on paper. It's very simple and is trivial to convert to an algorithm.

于 2010-05-19T16:18:27.453 回答
2

你可以阅读源代码bignum.c...

在非常高的层次上，没有任何实现细节，bignums 是“手工”计算的，就像你以前在小学做的那样。现在，当然可以应用许多优化，但这就是它的要点。

于 2010-05-19T16:10:46.753 回答
1

Beaconaut APICalc 2于 2011 年 1 月 18 日刚刚发布，这是一个用于 bignum 算术、密码学分析和数论研究的任意精度整数计算器......

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

于 2011-01-21T07:38:48.360 回答
0

它使用 Bignum 类

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

Rdoc当然可用

于 2010-05-19T16:09:06.117 回答