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

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

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

Основная идея заключается в том, что число хранится в виде массива его цифр.

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

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

Один из вариантов хранения длинных чисел можно реализовать в виде массива целых чисел, где каждый элемент — это одна цифра числа в 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} \ge[/math] BASE [math]/2[/math] (BASE — основание системы счисления), то можно доказать следующие факты:

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

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

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

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

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

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