Арифметика произвольной точности с Ruby
Как, черт возьми, Ruby делает это? Jörg или кто-либо еще знают то, что происходит негласно?
К сожалению, я не знаю C очень хорошо так bignum.c имеет мало справки ко мне. Мне было просто довольно любопытно это, кто-то мог объяснить (без обиняков) теорию позади любого алгоритма чуда его использование.
irb(main):001:0> 999**999
368063488259223267894700840060521865838338232037353204655959621437025609300472231530103873614505175218691345257589896391130393189447969771645832382192366076536631132001776175977932178658703660778465765811830827876982014124022948671975678131724958064427949902810498973271030787716781467419524180040734398996952930832508934116945966120176735120823151959779536852290090377452502236990839453416790640456116471139751546750048602189291028640970574762600185950226138244530187489211615864021135312077912018844630780307462205252807737757672094320692373101032517459518497524015120165166724189816766397247824175394802028228160027100623998873667435799073054618906855460488351426611310634023489044291860510352301912426608488807462312126590206830413782664554260411266378866626653755763627796569082931785645600816236891168141774993267488171702172191072731069216881668294625679492696148976999868715671440874206427212056717373099639711168901197440416590226524192782842896415414611688187391232048327738965820265934093108172054875188246591760877131657895633586576611857277011782497943522945011248430439201297015119468730712364007639373910811953430309476832453230123996750235710787086641070310288725389595138936784715274150426495416196669832679980253436807864187160054589045664027158817958549374490512399055448819148487049363674611664609890030088549591992466360050042566270348330911795487647045949301286614658650071299695652245266080672989921799342509291635330827874264789587306974472327718704306352445925996155619153783913237212716010410294999877569745287353422903443387562746452522860420416689019732913798073773281533570910205207767157128174184873357050830752777900041943256738499067821488421053870869022738698816059810579221002560882999884763252161747566893835178558961142349304466506402373556318707175710866983035313122068321102457824112014969387225476259342872866363550383840720010832906695360553556647545295849966279980830561242960013654529514995113584909050813015198928283202189194615501403435553060147713139766323195743324848047347575473228198492343231496580885057330510949058490527738662697480293583612233134502078182014347192522391449087738579081585795613547198599661273567662441490401862839817822686573112998663038868314974259766039340894024308383451039874674061160538242392803580758232755749310843694194787991556647907091849600704712003371103926967137408125713631396699343733288014254084819379380555174777020843568689927348949484201042595271932630685747613835385434424807024615161848223715989797178155169951121052285149157137697718850449708843330475301440373094611119631361702936342263219382793996895988331701890693689862459020775599439506870005130750427949747071390095256759203426671803377068109744629909769176319526837824364926844730545524646494321826241925107158040561607706364484910978348669388142016838792902926158979355432483611517588605967745393958061959024834251565197963477521095821435651996730128376734574843289089682710350244222290017891280419782767803785277960834729869249991658417000499998999
4 ответа
Просто: он делает это так же , что и вы , начиная с первого класса. За исключением того, что он не вычисляет в базе 10, он вычисляет в базе 4 миллиарда (и изменение).
Подумайте об этом: с нашей системой счисления мы можем представлять только числа от 0 до 9 . Итак, как мы можем вычислить 6 + 7 без переполнения? Легко: мы делаем на самом деле переполнением! Мы не можем представить результат 6 + 7 в виде числа от 0 до 9 , но мы можем перейти к следующему месту и представьте его как два числа между 0 и 9 : 3 × 10 0 + 1 × 10 1 . Если вы хотите сложить два числа, вы добавляете их по цифрам справа и переполняете («перенос») слева. Если вы хотите умножить два числа, вам нужно умножить каждую цифру одного числа отдельно на другое число, а затем сложить промежуточные результаты.
Арифметика BigNum (это то, что обычно называется арифметикой, в которой числа больше, чем собственные машинные числа) работает в основном таким же образом. За исключением того, что база не 10, и не 2, это размер собственного машинного целого числа. Итак, на 32-битной машине это будет база 2 32 или 4 294 967 296.
В частности, в Ruby Integer на самом деле является абстрактным классом, который никогда не создается. Вместо этого у него есть два подкласса, Fixnum и Bignum , и числа автоматически перемещаются между ними в зависимости от их размера. В MRI и YARV Fixnum может содержать 31- или 63-битное целое число со знаком (один бит используется для тегирования) в зависимости от собственного размера слова машины.В JRuby Fixnum может содержать полное 64-битное целое число со знаком, даже на 32-битной машине.
Простейшая операция - сложение двух чисел. И если вы посмотрите на реализацию + или, скорее, bigadd_core в YARV bignum.c , то это не слишком плохой вариант. Я тоже не могу читать C, но вы можете ясно видеть, как он перебирает отдельные цифры.
Я не знаю деталей реализации, поэтому Я расскажу, как будет работать базовая реализация Big Number.
По сути, вместо того, чтобы полагаться на «целые числа» ЦП, он будет создавать свои собственные, используя несколько целых чисел ЦП. Чтобы сохранить произвольную точность, допустим, у вас есть 2 бита. Итак, текущее целое число - 11. Вы хотите добавить единицу. В обычных целых числах ЦП это будет равно 00
. Но для большого числа вместо перехода и сохранения «фиксированной» целочисленной ширины он выделит еще один бит и имитирует сложение, чтобы число стало правильным 100. .
Попробуйте найти, как двоичную математику можно выполнять на бумаге. Это очень просто и тривиально преобразовать в алгоритм.
Вы можете прочитать исходный код для bignum.c ...
На очень высоком уровне, не вдаваясь в какие-либо детали реализации , bignum s рассчитываются «вручную», как вы это делали в начальной школе. Конечно, есть много оптимизаций, которые можно применить, но в этом суть.