Я хотел знать, как реализованы BigInt и другие подобные материалы. Я попытался проверить исходный код JAVA, но для меня все было греческим и латинским. Не могли бы вы объяснить мне алго в словах - никакого кода, так что я понимаю, что я фактически использую, когда я что-то использую из JAVA API. рассматривает
Как работают BigNums?
Ответ 1
Концептуально, так же, как вы производите произвольный размер арифметики вручную. У вас есть что-то вроде массива значений и алгоритмов для различных операций, которые работают с массивом.
Предположим, вы хотите добавить 100 в 901. Вы начинаете с двух чисел в виде массивов:
[0, 1, 0, 0]
[0, 9, 0, 1]
Когда вы добавляете, алгоритм добавления начинается справа, берет 0+1, давая 1, 0+0, давая 0, и - теперь сложная часть - 9+1 дает 10, но теперь нам нужно нести, поэтому мы добавим 1 к следующему столбцу и поместим (9+1)%10 в третий столбец.
Когда ваши цифры растут достаточно большими - больше 9999 в этом примере - тогда вам нужно как-то выделить больше места.
Это, конечно, несколько упрощается, если вы сохраняете числа в обратном порядке.
Реальные реализации используют полные слова, поэтому модуль действительно является некоторой большой степенью двух, но концепция одинаков.
В Кнуте есть очень хороший раздел.