Ответ 1
Все дело в адекватном хранении и алгоритмах для обработки чисел как небольших частей. Предположим, что у вас есть компилятор, в котором int может быть только от 0 до 99, и вы хотите обрабатывать номера до 999999 (мы будем беспокоиться только о положительных числах здесь, чтобы это было просто).
Вы делаете это, задавая каждый номер три int и используя те же правила, которые вы (должны были) получить в начальной школе для сложения, вычитания и других основных операций.
В произвольной библиотеке точности нет фиксированного ограничения на количество базовых типов, используемых для представления наших чисел, только то, что может содержать память.
Дополнение, например: 123456 + 78:
12 34 56
78
-- -- --
12 35 34
Работа с наименее значимым концом:
- начальный перенос = 0.
- 56 + 78 + 0 carry = 134 = 34 с 1 переносом
- 34 + 00 + 1 carry = 35 = 35 с 0 переносить
- 12 + 00 + 0 carry = 12 = 12 с 0 переносить
Это, по сути, то, как дополнение обычно работает на уровне бит внутри вашего процессора.
Вычитание аналогично (с использованием вычитания базового типа и заимствования вместо переноса), умножение может быть выполнено с повторными добавлениями (очень медленными) или кросс-продуктами (быстрее), а деление сложнее, но может быть выполнено сдвигом и вычитанием из числа вовлеченных (длинное разделение, которое вы узнали бы в детстве).
Я на самом деле писал библиотеки, чтобы делать подобные вещи, используя максимальные значения десяти, которые могут быть помещены в целое число при квадрате (чтобы предотвратить переполнение при объединении двух int вместе, например, 16-разрядный int ограничивается 0 до 99, чтобы генерировать 9,801 (< 32,768) при квадрате или 32-бит int с использованием от 0 до 9999 для генерации 99 980 001 (< 2,147,483,648)), что значительно облегчило алгоритмы.
Некоторые трюки, на которые следует обратить внимание.
1/При добавлении или умножении чисел предварительно назначьте необходимое пространство, а затем уменьшите его, если найдете его слишком много. Например, добавление двух цифр "цифра" (цифра - int) никогда не даст вам более 101 цифры. Умножьте 12-значное число на 3-значное число никогда не будет генерировать более 15 цифр (добавьте количество цифр).
2/Для дополнительной скорости нормализуйте (уменьшите требуемую память) цифры только в том случае, если это абсолютно необходимо - в моей библиотеке это было как отдельный вызов, поэтому пользователь может решить проблему между скоростью и хранением.
3/Добавление положительного и отрицательного числа является вычитанием, а вычитание отрицательного числа совпадает с добавлением эквивалентного положительного. Вы можете сэкономить немало кода, если методы добавления и вычитания вызовут друг друга после настройки значков.
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), более поддаются обсуждению потенциальных изменений - они кажутся более дружественной для разработчиков связью.