Арифметика чисел в b-ичной системе счисления (Длинная арифметика)

Определение:

Длинная арифметика (англ. arbitrary-precision arithmetic, или bignum arithmetic) — это набор программных средств (структуры данных и алгоритмы), которые позволяют работать с числами гораздо больших величин, чем это позволяют стандартные типы данных.

Классическая длинная арифметика

Основная идея "классической длинной арифметики"заключается в том, что число хранится в виде массива его цифр. Цифры могут использоваться из той или иной системы счисления, обычно применяются десятичная система счисления и её степени (десять тысяч, миллиард), двоичная система счисления либо любая другая.

Представление в памяти

Один из вариантов хранения длинных чисел можно реализовать в виде массива целых чисел, где каждый элемент — это одна цифра числа в b-й системе счисления.

Цифры будут храниться в массиве в таком порядке, что сначала идут наименее значимые цифры (т.е., например, единицы, десятки, сотни, и т.д.).

Кроме того, все операции будут реализованы таким образом, что после выполнения любой из них лидирующие нули (т.е. лишние нули в начале числа) отсутствуют (разумеется, в предположении, что перед каждой операцией лидирующие нули также отсутствуют). Следует отметить, что в представленной реализации для числа ноль корректно поддерживаются сразу два представления: пустой вектор цифр, и вектор цифр, содержащий единственный элемент — ноль.

Сложение, вычитание, умножение, деление на короткое, деление на длинное

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

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

Подбор значения очередной цифры в алгоритме деления в столбик

Подбор следующей цифры [math]k \in [0, b)[/math] частного можно производить с помощью стандартного алгоритма двоичного поиска за [math]\ln(b)[/math].

Но также существуют и более быстрые алгоритмы. Довольно интересный способ состоит в высказывании догадки (qGuess) по первым цифрам делителя и делимого. Понятно, что этих нескольких цифр недостаточно для гарантированно правильного результата, однако неплохое приближение все же получится. Пусть очередной шаг представляет собой деление некоторого [math]U = (u_0, u_1, \cdots, u_n)[/math] на [math]B = (b_0, b_1, \cdots, b_{n-1})[/math]. Если [math]b_{n-1} \geqslant [/math] BASE [math]/ 2[/math] (где BASE — основание системы счисления), то можно доказать следующие факты:

• 1. Если положить qGuess [math] = (u_n \cdot[/math][math] [/math] BASE [math]+\ u_{n-1}) / b_{n-1}[/math] , то qGuess[math]-2 \leqslant q \leqslant[/math] qGuess.

Иначе говоря, вычисленная таким способом “догадка” будет не меньше искомого частного, но может быть больше на [math]1[/math] или [math]2[/math].

• 2. Если же дополнительно выполняется неравенство qGuess[math] \cdot b_{n-2} \gt [/math] BASE [math]\cdot r +\ u_{n-2}[/math] , где [math]r[/math] – остаток при нахождении qGuess и qGuess [math]≠[/math] BASE, то qGuess [math]-1 \leqslant q \leqslant[/math] qGuess, причем вероятность события qGuess[math] = q + 1[/math] приблизительно равна [math]2 / [/math] BASE.

Таким образом, если [math]b_{n-1} \geqslant [/math] BASE[math]/2[/math], то можно вычислить qGuess [math] = (u_n \cdot[/math][math]\ [/math]BASE [math] + u_{n-1}) / b_{n-1}[/math] и уменьшать на единицу до тех пор, пока не станут выполняться условия. Получившееся значение будет либо правильным частным [math]q[/math], либо, с вероятностью [math]2/[/math]BASE, на единицу большим числом.

Что делать, если [math]b_{n-1}[/math] слишком мало, чтобы пользоваться таким способом? Например, можно домножить делитель и делимое на одно и то же число scale [math] = [/math] BASE[math] / ( b_{n-1} +1 )[/math]. В случае, если основание системы счисления является степенью двойки, scale можно выбрать соответствующей степенью двойки. При этом несколько изменится способ вычисления остатка, а частное останется прежним. Такое домножение иногда называют нормализацией числа. На тот случай, если qGuess получилось все же на единицу большим [math]q[/math], будем использовать вычитание, которое вместо отрицательного числа даст дополнение до следующей степени основания. Если такое произошло, то последний перенос будет равен [math]-1[/math]. Это сигнал, что необходимо прибавить одно B назад. Заметим, что в конце сложения будет лишний перенос на единицу, о котором нужно забыть (он компенсирует последний перенос [math](-1)[/math]).

http://forum.sources.ru/index.php?showtopic=210512&hl=

Источники информации

• e-maxx: Длинная арифметика

См. также

• Системы счисления
• Разложение на множители (факторизация)