Все дело в адекватном хранении и алгоритмах, которые рассматривают числа как меньшие части. Предположим, у вас есть компилятор, в котором int может быть только от 0 до 99, и вы хотите обрабатывать числа до 999999 (здесь мы будем думать только о положительных числах, чтобы упростить его).
Вы делаете это, давая каждому число три int s и используя те же правила, которые вы (должны были) выучить, еще в начальной школе для сложения, вычитания и других основных операций.
В библиотеке произвольной точности не существует фиксированного ограничения на количество базовых типов, используемых для представления наших чисел, только то, что может вместить память.
Дополнение например: 123456 + 78:
12 34 56
78
-- -- --
12 35 34
Работа от наименее значимого конца:
- начальный перенос = 0.
- 56 + 78 + 0 переносов = 134 = 34 с 1 переносом
- 34 + 00 + 1 перенос = 35 = 35 с 0 переносом
- 12 + 00 + 0 переносить = 12 = 12 с 0 переносить
Это, собственно, то, как сложение обычно работает на уровне битов внутри вашего процессора.
Вычитание аналогично (используется вычитание базового типа и заимствование вместо переноса), умножение может быть выполнено с повторными сложениями (очень медленными) или перекрестными продуктами (быстрее), а деление сложнее, но может быть выполнено путем сдвига и вычитания из числа участвующих (длинное деление вы бы выучили в детстве).
Я на самом деле написал библиотеки для такого рода вещей, используя максимальные степени десяти, которые можно вписать в целое число в квадрате (чтобы предотвратить переполнение при умножении двух int с, таких как 16-битный int ограничено от 0 до 99 для генерации 9 801 (<32 768) в квадрате или 32-битное <code>int с использованием от 0 до 9 999 для генерации 99 980 001 (<2 147 483 648)), что значительно облегчило алгоритмы. </p>
Некоторые хитрости, на которые стоит обратить внимание.
1 / При добавлении или умножении чисел предварительно выделите максимальное необходимое пространство, а затем уменьшите его, если вы обнаружите, что это слишком много. Например, добавление двух 100-значных цифр (где цифра int) никогда не даст вам более 101 цифры. Умножение 12-значного числа на 3-значное число никогда не приведет к созданию более 15 цифр (добавьте число цифр).
2 / Для дополнительной скорости нормализуйте (уменьшите объем памяти, необходимый для) чисел, только если это абсолютно необходимо - моя библиотека провела это как отдельный вызов, чтобы пользователь мог выбирать между скоростью и проблемами хранения.
3 / Сложение положительного и отрицательного числа является вычитанием, а вычитание отрицательного числа аналогично добавлению эквивалентного положительного числа. Вы можете сохранить немного кода, вызвав методы add и subtract друг к другу после корректировки знаков.
4 / Избегайте вычитания больших чисел из маленьких, так как вы неизменно получаете такие числа, как:
10
11-
-- -- -- --
99 99 99 99 (and you still have a borrow).
Вместо этого вычтите 10 из 11, затем отрицайте это:
11
10-
--
1 (then negate to get -1).
Вот комментарии (превращенные в текст) из одной из библиотек, для которых я должен был это сделать. К сожалению, сам код защищен авторским правом, но вы можете выбрать достаточно информации для выполнения четырех основных операций. Далее предположим, что -a и -b представляют отрицательные числа, а a и b - ноль или положительные числа.
Для сложение , если знаки отличаются, используйте вычитание отрицания:
-a + b becomes b - a
a + -b becomes a - b
Для вычитания , если знаки отличаются, используйте добавление отрицания:
a - -b becomes a + b
-a - b becomes -(a + b)
Также специальная обработка, обеспечивающая вычитание небольших чисел из больших:
small - big becomes -(big - small)
Умножение использует начальную математику следующим образом:
475(a) x 32(b) = 475 x (30 + 2)
= 475 x 30 + 475 x 2
= 4750 x 3 + 475 x 2
= 4750 + 4750 + 4750 + 475 + 475
Способ, которым это достигается, заключается в извлечении каждой из 32 цифр по одной за раз (в обратном направлении) с последующим использованием add для вычисления значения, которое будет добавлено к результату (изначально нулевое).
Операции
ShiftLeft и ShiftRight используются для быстрого умножения или деления LongInt на значение переноса (10 для «реальной» математики). В приведенном выше примере мы добавляем 475 к нулю 2 раза (последняя цифра 32), чтобы получить 950 (результат = 0 + 950 = 950).
Затем мы оставили левый сдвиг 475, чтобы получить 4750, и правый сдвиг 32, чтобы получить 3. Добавьте 4750 к нулю 3 раза, чтобы получить 14250, затем добавьте к результату 950, чтобы получить 15200.
Сдвиг влево 4750, чтобы получить 47500, сдвиг вправо 3, чтобы получить 0. Поскольку сдвиг вправо 32 теперь равен нулю, мы закончили и, фактически, 475 x 32 равны 15200.
Деление также сложно, но основано на ранней арифметике (метод "gazinta" для "идет в"). Рассмотрим следующее длинное деление для 12345 / 27:
457
+-------
27 | 12345 27 is larger than 1 or 12 so we first use 123.
108 27 goes into 123 4 times, 4 x 27 = 108, 123 - 108 = 15.
---
154 Bring down 4.
135 27 goes into 154 5 times, 5 x 27 = 135, 154 - 135 = 19.
---
195 Bring down 5.
189 27 goes into 195 7 times, 7 x 27 = 189, 195 - 189 = 6.
---
6 Nothing more to bring down, so stop.
Следовательно, 12345 / 27 равно 457 с остатком 6. Проверка:
457 x 27 + 6
= 12339 + 6
= 12345
Это реализуется с помощью переменной просадки (изначально равной нулю), чтобы сбить сегменты 12345 по одному, пока она не станет больше или равна 27.
Затем мы просто вычитаем 27 из этого, пока не опустимся ниже 27 - число вычитаний - это сегмент, добавленный к верхней строке.
Когда больше нет сегментов, которые нужно сбить, у нас есть результат.
Имейте в виду, что это довольно простые алгоритмы. Есть намного лучшие способы сделать сложную арифметику, если ваши числа будут особенно большими. Вы можете посмотреть что-то вроде Многофункциональная арифметическая библиотека GNU - это значительно лучше и быстрее, чем мои собственные библиотеки.
Он имеет довольно прискорбную ошибку в том, что он просто выйдет, если у него не хватит памяти (на мой взгляд, довольно фатальный недостаток для библиотеки общего назначения), но если вы посмотрите на это, то довольно хорошо это делает.
Если вы не можете использовать его по причинам лицензирования (или если вы не хотите, чтобы ваше приложение просто выходило без видимой причины), вы можете по крайней мере получить оттуда алгоритмы для интеграции в свой собственный код.
Я также обнаружил, что тела в MPIR (ветвь GMP) более поддаются обсуждению потенциальных изменений - они кажутся более дружественными для разработчиков.