Как работают реализации BigNums?

Question

Я хотел знать, как реализованы BigInt и другие подобные вещи. Я попытался проверить исходный код JAVA, но для меня это был греческий и латинский языки. Можете ли вы объяснить мне алгоритм на словах - без кода, чтобы я понимал, что я на самом деле использую, когда я использую что-то из JAVA API. С уважением

Answer 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 в этом примере - тогда вам придется как-то выделить больше места.

Это, конечно, несколько упрощается, если вы храните числа в обратном порядке.

В реальных реализациях используются полные слова, поэтому модуль на самом деле является большой степенью двойки, но концепция та же.

В Кнуте есть очень хороший раздел по этому вопросу.