Арифметика произвольной точности с Ruby

Как, черт возьми, Руби это делает? Знает ли Йорг или кто-либо еще, что происходит за кулисами?

К сожалению, я не очень хорошо знаю C, поэтому bignum.c мне мало помогает. Мне было просто любопытно, может ли кто-нибудь объяснить (на простом английском языке) теорию, лежащую в основе любого чудодейственного алгоритма, который он использует.

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

368063488259223267894700840060521865838338232037353204655959621437025609300472231530103873614505175218691345257589896391130393189447969771645832382192366076536631132001776175977932178658703660778465765811830827876982014124022948671975678131724958064427949902810498973271030787716781467419524180040734398996952930832508934116945966120176735120823151959779536852290090377452502236990839453416790640456116471139751546750048602189291028640970574762600185950226138244530187489211615864021135312077912018844630780307462205252807737757672094320692373101032517459518497524015120165166724189816766397247824175394802028228160027100623998873667435799073054618906855460488351426611310634023489044291860510352301912426608488807462312126590206830413782664554260411266378866626653755763627796569082931785645600816236891168141774993267488171702172191072731069216881668294625679492696148976999868715671440874206427212056717373099639711168901197440416590226524192782842896415414611688187391232048327738965820265934093108172054875188246591760877131657895633586576611857277011782497943522945011248430439201297015119468730712364007639373910811953430309476832453230123996750235710787086641070310288725389595138936784715274150426495416196669832679980253436807864187160054589045664027158817958549374490512399055448819148487049363674611664609890030088549591992466360050042566270348330911795487647045949301286614658650071299695652245266080672989921799342509291635330827874264789587306974472327718704306352445925996155619153783913237212716010410294999877569745287353422903443387562746452522860420416689019732913798073773281533570910205207767157128174184873357050830752777900041943256738499067821488421053870869022738698816059810579221002560882999884763252161747566893835178558961142349304466506402373556318707175710866983035313122068321102457824112014969387225476259342872866363550383840720010832906695360553556647545295849966279980830561242960013654529514995113584909050813015198928283202189194615501403435553060147713139766323195743324848047347575473228198492343231496580885057330510949058490527738662697480293583612233134502078182014347192522391449087738579081585795613547198599661273567662441490401862839817822686573112998663038868314974259766039340894024308383451039874674061160538242392803580758232755749310843694194787991556647907091849600704712003371103926967137408125713631396699343733288014254084819379380555174777020843568689927348949484201042595271932630685747613835385434424807024615161848223715989797178155169951121052285149157137697718850449708843330475301440373094611119631361702936342263219382793996895988331701890693689862459020775599439506870005130750427949747071390095256759203426671803377068109744629909769176319526837824364926844730545524646494321826241925107158040561607706364484910978348669388142016838792902926158979355432483611517588605967745393958061959024834251565197963477521095821435651996730128376734574843289089682710350244222290017891280419782767803785277960834729869249991658417000499998999


ruby math bignum arbitrary-precision
person maček    schedule 19.05.2010    source источник

Ответы (5)


arrow_upward
18
arrow_downward

Просто: он делает это так же, как вы, с первого класса. За исключением того, что он не вычисляет по основанию 10, он вычисляет по основанию 4 миллиарда (и изменение).

Подумайте об этом: в нашей системе счисления мы можем представлять только числа от 0 до 9. Итак, как мы можем вычислить 6+7 без переполнения? Легко: мы на самом деле переполняем! Мы не можем представить результат 6+7 как число между 0 и 9, но мы можем перейти к следующему месту и представить его как два числа между 0 и 9: 310< суп>0 + 1101. Если вы хотите добавить два числа, вы добавляете их по цифрам справа и переполняете («переносите») слева. Если вы хотите умножить два числа, вы должны умножить каждую цифру одного числа отдельно на другое число, а затем сложить промежуточные результаты.

Арифметика BigNum (именно так обычно называется такая арифметика, где числа больше, чем нативные машинные числа) работает в основном таким же образом. За исключением того, что база не 10 и не 2, либо это размер машинного целого числа. Таким образом, на 32-битной машине это будет основание 232 или 4294967296.

В частности, в Ruby Integer на самом деле является абстрактным классом, который никогда не создается. Вместо этого у него есть два подкласса, Fixnum и Bignum, и числа автоматически мигрируют между ними в зависимости от их размера. В MRI и YARV Fixnum может содержать 31- или 63-битное целое число со знаком (один бит используется для маркировки) в зависимости от собственного размера слова машины. В JRuby Fixnum может содержать полное 64-битное целое число со знаком даже на 32-битной машине.

Самая простая операция — сложение двух чисел. И если вы посмотрите на реализацию + или, скорее, bigadd_core в bignum YARV .c, не так уж плохо слишком следовать. Я тоже не могу читать C, но вы можете ясно видеть, как он зацикливается на отдельных цифрах.

person Jörg W Mittag    schedule 19.05.2010
comment
У вас такой хороший способ объяснить вещи. Спасибо за всю вашу помощь :) - person maček; 19.05.2010

arrow_upward
2
arrow_downward

Вы можете прочитать источник для bignum.c< /а>...

На очень высоком уровне, не вдаваясь в какие-либо детали реализации, bignum вычисляются "вручную", как вы делали это в начальной школе. Безусловно, можно применить множество оптимизаций, но в этом суть.

person Mark Rushakoff    schedule 19.05.2010
comment
К сожалению, я не очень хорошо знаю C. Мне было просто любопытно, может ли кто-нибудь объяснить (на простом английском языке) теорию, лежащую в основе любого чудодейственного алгоритма, который он использует. - person maček; 19.05.2010
comment
@macek: этот чудо-алгоритм тот же самый, который ты выучил в первом классе. Ну, ладно, можно делать всевозможные сумасшедшие оптимизации, но по сути это одно и то же. Подумайте об этом: вы можете умножить 23*45, даже если наша система счисления переходит от 0 к 9, просто используя множество чисел. То же самое можно сделать и на компьютере, за исключением системы счисления от 0 до 4294967296. - person Jörg W Mittag; 19.05.2010

arrow_upward
2
arrow_downward

Я не знаю подробностей реализации, поэтому расскажу, как будет работать базовая реализация Big Number.

По сути, вместо того, чтобы полагаться на «целые числа» ЦП, он будет создавать свои собственные, используя несколько целых чисел ЦП. Чтобы сохранить произвольную точность, скажем, у вас есть 2 бита. Итак, текущее целое число равно 11. Вы хотите добавить единицу. В обычных целых числах ЦП это будет равно 00.

Но для большого числа вместо того, чтобы переворачиваться и сохранять «фиксированную» целочисленную ширину, он выделяет еще один бит и имитирует сложение, чтобы число стало правильным 100.

Попробуйте посмотреть, как можно выполнить двоичную математику на бумаге. Это очень просто и тривиально преобразовать в алгоритм.

person Earlz    schedule 19.05.2010

arrow_upward
1
arrow_downward

Beaconaut APICalc 2, выпущенный 18 января 2011 года, представляет собой целочисленный калькулятор произвольной точности для арифметики больших чисел, криптографического анализа и исследований в области теории чисел......

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

person TuringBombe    schedule 21.01.2011

arrow_upward
0
arrow_downward

Он использует класс Bignum

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

Rdoc, конечно, доступен

person Gareth    schedule 19.05.2010