使用 Ruby 进行任意精度算术
Ruby 到底是怎么做到这一点的呢？ Jörg 或其他人知道幕后发生的事情吗？
不幸的是，我不太了解 C，所以 bignum。 c 对我帮助不大。我只是有点好奇有人可以（用简单的英语）解释其使用的任何奇迹算法背后的理论。
irb(main):001:0> 999**999
How the heck does Ruby do this? Does Jörg or anyone else know what's happening behind the scenes?
Unfortunately I don't know C very well so bignum.c is of little help to me. I was just kind of curious it someone could explain (in plain English) the theory behind whatever miracle algorithm its using.
irb(main):001:0> 999**999
368063488259223267894700840060521865838338232037353204655959621437025609300472231530103873614505175218691345257589896391130393189447969771645832382192366076536631132001776175977932178658703660778465765811830827876982014124022948671975678131724958064427949902810498973271030787716781467419524180040734398996952930832508934116945966120176735120823151959779536852290090377452502236990839453416790640456116471139751546750048602189291028640970574762600185950226138244530187489211615864021135312077912018844630780307462205252807737757672094320692373101032517459518497524015120165166724189816766397247824175394802028228160027100623998873667435799073054618906855460488351426611310634023489044291860510352301912426608488807462312126590206830413782664554260411266378866626653755763627796569082931785645600816236891168141774993267488171702172191072731069216881668294625679492696148976999868715671440874206427212056717373099639711168901197440416590226524192782842896415414611688187391232048327738965820265934093108172054875188246591760877131657895633586576611857277011782497943522945011248430439201297015119468730712364007639373910811953430309476832453230123996750235710787086641070310288725389595138936784715274150426495416196669832679980253436807864187160054589045664027158817958549374490512399055448819148487049363674611664609890030088549591992466360050042566270348330911795487647045949301286614658650071299695652245266080672989921799342509291635330827874264789587306974472327718704306352445925996155619153783913237212716010410294999877569745287353422903443387562746452522860420416689019732913798073773281533570910205207767157128174184873357050830752777900041943256738499067821488421053870869022738698816059810579221002560882999884763252161747566893835178558961142349304466506402373556318707175710866983035313122068321102457824112014969387225476259342872866363550383840720010832906695360553556647545295849966279980830561242960013654529514995113584909050813015198928283202189194615501403435553060147713139766323195743324848047347575473228198492343231496580885057330510949058490527738662697480293583612233134502078182014347192522391449087738579081585795613547198599661273567662441490401862839817822686573112998663038868314974259766039340894024308383451039874674061160538242392803580758232755749310843694194787991556647907091849600704712003371103926967137408125713631396699343733288014254084819379380555174777020843568689927348949484201042595271932630685747613835385434424807024615161848223715989797178155169951121052285149157137697718850449708843330475301440373094611119631361702936342263219382793996895988331701890693689862459020775599439506870005130750427949747071390095256759203426671803377068109744629909769176319526837824364926844730545524646494321826241925107158040561607706364484910978348669388142016838792902926158979355432483611517588605967745393958061959024834251565197963477521095821435651996730128376734574843289089682710350244222290017891280419782767803785277960834729869249991658417000499998999
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
很简单：从一年级开始，它就和你一样做。除了它不以 10 为基数进行计算外，它以 40 亿为基数进行计算（以及变化）。
想一想：在我们的数字系统中，我们只能表示从
0到9的数字。那么，我们如何计算6+7而不溢出呢？简单：我们确实实际上溢出了！我们无法将6+7的结果表示为0和9之间的数字，但我们可以溢出到下一个位置并将其表示为0和9之间的两个数字：3×100 + 1×10 1。如果您想将两个数字相加，请从右侧按数字顺序将它们相加，然后向左侧溢出（“进位”）。如果要将两个数字相乘，则必须将一个数字的每一位数字分别与另一个数字相乘，然后将中间结果相加。BigNum 算术（通常称为这种数字大于本机数字的算术）的工作原理基本相同。除了基数不是 10，也不是 2，它是本机机器整数的大小。因此，在 32 位机器上，它将是基数 232 或 4 294 967 296。
具体来说，在 Ruby 中，
Integer实际上是一个从未实例化的抽象类。相反，它有两个子类：Fixnum和Bignum，数字会根据其大小在它们之间自动迁移。在 MRI 和 YARV 中，Fixnum 可以保存 31 或 63 位有符号整数（一位用于标记），具体取决于机器的本机字大小。在 JRuby 中，Fixnum 可以保存完整的 64 位有符号整数，即使在 32 位机器上也是如此。最简单的操作是将两个数字相加。如果您查看 YARV 的 bignum.c，遵循起来还不错。我也看不懂 C，但你可以清楚地看到它如何循环各个数字。
Simple: it does it the same way you do, ever since first grade. Except it doesn't compute in base 10, it computes in base 4 billion (and change).
Think about it: with our number system, we can only represent numbers from
0to9. So, how can we compute6+7without overflowing? Easy: we do actually overflow! We cannot represent the result of6+7as a number between0and9, but we can overflow to the next place and represent it as two numbers between0and9: 3×100 + 1×101. If you want to add two numbers, you add them digit-wise from the right and overflow ("carry") to the left. If you want to multiply two numbers, you have to multiply every digit of one number individually with the other number, then add up the intermediate results.BigNum arithmetic (this is what this kind of arithmetic where the numbers are bigger than the native machine numbers is usually called) works basically the same way. Except that the base is not 10, and its not 2, either – it's the size of a native machine integer. So, on a 32 bit machine, it would be base 232 or 4 294 967 296.
Specifically, in Ruby
Integeris actually an abstract class that is never instianted. Instead, it has two subclasses,FixnumandBignum, and numbers automagically migrate between them, depending on their size. In MRI and YARV, Fixnum can hold a 31 or 63 bit signed integer (one bit is used for tagging) depending on the native word size of the machine. In JRuby, a Fixnum can hold a full 64 bit signed integer, even on an 32 bit machine.The simplest operation is adding two numbers. And if you look at the implementation of
+or ratherbigadd_corein YARV's bignum.c, it's not too bad to follow. I can't read C either, but you can cleary see how it loops over the individual digits.您可以阅读
bignum.c...在非常高的层面上，无需深入了解任何实现细节，
bignum都是“手动”计算的就像你以前在小学时做的那样。现在，当然有许多可以应用的优化，但这就是它的要点。You could read the source for
bignum.c...At a very high level, without going into any implementation details,
bignums are calculated "by hand" like you used to do in grade school. Now, there are certainly many optimizations that can be applied, but that's the gist of it.我不知道实现细节，因此我将介绍基本的大数实现如何工作。
基本上，它不会依赖 CPU“整数”，而是使用多个 CPU 整数创建自己的整数。为了存储任意精度，假设您有 2 位。所以当前的整数是11。你想加一。在普通的 CPU 整数中，这会翻转到 00
但是，对于大数字，它不会翻转并保持“固定”整数宽度，而是分配另一位并模拟加法，以便数字变为正确的 100。
尝试查看了解如何在纸上完成二进制数学。它非常简单，转换成算法也很简单。
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.
Beaconaut APICalc 2于2011年1月18日刚刚发布，是一款用于bignum算术、密码学分析和数论研究的任意精度整数计算器......
http://www.beaconaut.com/forums/default.aspx?g=posts&t= 13
Beaconaut APICalc 2 just released on Jan.18, 2011, which is an arbitrary-precision integer calculator for bignum arithmetic, cryptography analysis and number theory research......
http://www.beaconaut.com/forums/default.aspx?g=posts&t=13
它使用 Bignum 类
Rdoc 当然可用
It uses the Bignum class
Rdoc is available of course