Ruby的任意精度算法 [英] Arbitrary precision arithmetic with Ruby
问题描述
Ruby如何做到这一点?约尔格或其他任何人都知道幕后发生了什么吗?
How the heck does Ruby do this? Does Jörg or anyone else know what's happening behind the scenes?
不幸的是，我不太了解C，所以
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
3680634882592232678947008400605218658383382320373532046559596214370256093004722315301038736145051752186913452575898963911303931894479697716458323821923660765366311320017761759779321786587036607784657658118308278769820141240229486719756781317249580644279499028104989732710307877167814674195241800407343989969529308325089341169459661201767351208231519597795368522900903774525022369908394534167906404561164711397515467500486021892910286409705747626001859502261382445301874892116158640211353120779120188446307803074622052528077377576720943206923731010325174595184975240151201651667241898167663972478241753948020282281600271006239988736674357990730546189068554604883514266113106340234890442918605103523019124266084888074623121265902068304137826645542604112663788666266537557636277965690829317856456008162368911681417749932674881717021721910727310692168816682946256794926961489769998687156714408742064272120567173730996397111689011974404165902265241927828428964154146116881873912320483277389658202659340 9310817205487518824659176087713165789563358657661185727701178249794352294501124843043920129701511946873071236400763937391081195343030947683245323012399675023571078708664107031028872538959513893678471527415042649541619666983267998025343680786418716005458904566402715881795854937449051239905544881914848704936367461166460989003008854959199246636005004256627034833091179548764704594930128661465865007129969565224526608067298992179934250929163533082787426478958730697447232771870430635244592599615561915378391323721271601041029499987756974528735342290344338756274645252286042041668901973291379807377328153357091020520776715712817418487335705083075277790004194325673849906782148842105387086902273869881605981057922100256088299988476325216174756689383517855896114234930446650640237355631870717571086698303531312206832110245782411201496938722547625934287286636355038384072001083290669536055355664754529584996627998083056124296001365452951499511358490905081301519892828320218919461550140343555306014771313976 6323195743324848047347575473228198492343231496580885057330510949058490527738662697480293583612233134502078182014347192522391449087738579081585795613547198599661273567662441490401862839817822686573112998663038868314974259766039340894024308383451039874674061160538242392803580758232755749310843694194787991556647907091849600704712003371103926967137408125713631396699343733288014254084819379380555174777020843568689927348949484201042595271932630685747613835385434424807024615161848223715989797178155169951121052285149157137697718850449708843330475301440373094611119631361702936342263219382793996895988331701890693689862459020775599439506870005130750427949747071390095256759203426671803377068109744629909769176319526837824364926844730545524646494321826241925107158040561607706364484910978348669388142016838792902926158979355432483611517588605967745393958061959024834251565197963477521095821435651996730128376734574843289089682710350244222290017891280419782767803785277960834729869249991658417000499998999
368063488259223267894700840060521865838338232037353204655959621437025609300472231530103873614505175218691345257589896391130393189447969771645832382192366076536631132001776175977932178658703660778465765811830827876982014124022948671975678131724958064427949902810498973271030787716781467419524180040734398996952930832508934116945966120176735120823151959779536852290090377452502236990839453416790640456116471139751546750048602189291028640970574762600185950226138244530187489211615864021135312077912018844630780307462205252807737757672094320692373101032517459518497524015120165166724189816766397247824175394802028228160027100623998873667435799073054618906855460488351426611310634023489044291860510352301912426608488807462312126590206830413782664554260411266378866626653755763627796569082931785645600816236891168141774993267488171702172191072731069216881668294625679492696148976999868715671440874206427212056717373099639711168901197440416590226524192782842896415414611688187391232048327738965820265934093108172054875188246591760877131657895633586576611857277011782497943522945011248430439201297015119468730712364007639373910811953430309476832453230123996750235710787086641070310288725389595138936784715274150426495416196669832679980253436807864187160054589045664027158817958549374490512399055448819148487049363674611664609890030088549591992466360050042566270348330911795487647045949301286614658650071299695652245266080672989921799342509291635330827874264789587306974472327718704306352445925996155619153783913237212716010410294999877569745287353422903443387562746452522860420416689019732913798073773281533570910205207767157128174184873357050830752777900041943256738499067821488421053870869022738698816059810579221002560882999884763252161747566893835178558961142349304466506402373556318707175710866983035313122068321102457824112014969387225476259342872866363550383840720010832906695360553556647545295849966279980830561242960013654529514995113584909050813015198928283202189194615501403435553060147713139766323195743324848047347575473228198492343231496580885057330510949058490527738662697480293583612233134502078182014347192522391449087738579081585795613547198599661273567662441490401862839817822686573112998663038868314974259766039340894024308383451039874674061160538242392803580758232755749310843694194787991556647907091849600704712003371103926967137408125713631396699343733288014254084819379380555174777020843568689927348949484201042595271932630685747613835385434424807024615161848223715989797178155169951121052285149157137697718850449708843330475301440373094611119631361702936342263219382793996895988331701890693689862459020775599439506870005130750427949747071390095256759203426671803377068109744629909769176319526837824364926844730545524646494321826241925107158040561607706364484910978348669388142016838792902926158979355432483611517588605967745393958061959024834251565197963477521095821435651996730128376734574843289089682710350244222290017891280419782767803785277960834729869249991658417000499998999
推荐答案
简单:从一年级开始，它就和您一样.除了不以10为基数计算之外，它以40亿为基数(并且有变化).
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).
考虑一下:使用我们的数字系统，我们只能表示从0到9的数字.那么，如何计算6+7而不会溢出?容易:我们做实际上溢出了！我们不能将6+7的结果表示为0和9之间的数字，但是我们可以溢出到下一个位置，并将其表示为之间的两个数字0和9:3× 10 0 + 1× 10 1 .如果要添加两个数字，请从右侧按数字方式添加它们，并向左溢出(进位").如果要将两个数字相乘，则必须将一个数字的每个数字分别与另一个数字相乘，然后将中间结果相加.
Think about it: with our number system, we can only represent numbers from 0 to 9. So, how can we compute 6+7 without overflowing? Easy: we do actually overflow! We cannot represent the result of 6+7 as a number between 0 and 9, but we can overflow to the next place and represent it as two numbers between 0 and 9: 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算术(这是通常称为数字大于本机编号的算术)的工作原理基本相同.除了基数不是10，也不是2之外， –它是本机整数的大小.因此，在32位计算机上，它将以2 32 或4 294 967 296为基础.
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.
具体地说，在Ruby中，Integer实际上是一个永远不会被抽象的抽象类.相反，它具有两个子类Fixnum和Bignum，并且数字根据它们的大小自动在它们之间迁移.在MRI和YARV中，Fixnum可以容纳31或63位带符号整数(用于标记的位为1位)，具体取决于机器的原始字长.在JRuby中，即使在32位计算机上，Fixnum也可以容纳完整的64位带符号整数.
Specifically, in Ruby Integer is actually an abstract class that is never instianted. Instead, it has two subclasses, Fixnum and Bignum, 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 rather bigadd_core in 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.
这篇关于Ruby的任意精度算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
