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

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

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

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

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

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

Один из вариантов хранения длинных чисел — массив целых чисел [math]int[/math], где каждый элемент — это одна цифра числа в b-ичной системе счисления. Цифры будут храниться в массиве в следующем порядке: сначала идут наименее значимые цифры (т.е., например, единицы, десятки, сотни, и т.д.).

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

Операции над числами

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

Сложение

   //Прибавляет к числу a число b и сохраняет результат в a:
    carry = 0
    i = 0
    while i < max(a.size(),b.size()) || carry
      if i == a.size()
        a.push_back (0)
      a[i] += carry + (i < b.size() ? b[i] : 0)
      carry = a[i] [math]\geqslant[/math] base
      if carry
        a[i] -= base
      i++

Вычитание

   //Отнимает от числа a число b (a [math]\geqslant[/math] b) и сохраняет результат в a:
    carry = 0
    i = 0
    while i < b.size() || carry
      a[i] -= carry + (i < b.size() ? b[i] : 0)
      carry = a[i] < 0
      if carry
        a[i] += base
      i++
    while a.size() > 1 && a.back() == 0
      a.pop_back()
   //Здесь мы после выполнения вычитания удаляем лидирующие нули, чтобы поддерживать предикат о том, что таковые отсутствуют.

Умножение длинного на короткое

   //Умножает длинное a на короткое b (b < base) и сохраняет результат в a:
    carry = 0
    i = 0
    while i < a.size() || carry
      if i == a.size()
        a.push_back (0)
      long long cur = carry + a[i] [math]\cdot[/math] 1ll [math]\cdot[/math] b;
      a[i] = cur mod base
      carry = cur / base
      i++
    while a.size() > 1 && a.back() == 0
      a.pop_back()
   //Здесь мы после выполнения деления удаляем лидирующие нули, чтобы поддерживать предикат о том, что таковые отсутствуют.

Умножение двух длинных чисел

   //Умножает a на b и результат сохраняет в c:
    carry = 0
    i = 0
    while i < a.size()
      j = 0
      while (j < b.size() || carry)
        long long cur = c[i+j] + a[i] [math]\cdot[/math] 1ll [math]\cdot[/math] (j < (int)b.size() ? b[j] : 0) + carry
        c[i+j] = cur mod base
        carry = cur / base
        i++
      j++
    while c.size() > 1 && c.back() == 0
      c.pop_back()

Деление длинного на короткое

   //Делит длинное a на короткое b (b < base), частное сохраняет в a, остаток в carry:
   carry = 0
   i = a.size()-1
   while i \geqslant 0
     long long cur = a[i] + carry [math]\cdot[/math] 1ll [math]\cdot[/math] base
        a[i] = cur mod base
        carry = cur / base
     i--
   while a.size() > 1 && a.back() == 0
     a.pop_back()

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

Подбор следующей цифры [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, \ldots, b_{n-1})[/math]. Если [math]b_{n-1} \geqslant [/math][math]\frac{BASE}{2}[/math] (где BASE — основание системы счисления), то можно доказать следующие факты:

• 1. Если положить qGuess [math] = \frac{ (u_n \cdot BASE + \ 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]\frac{2}{BASE}[/math].

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

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

Источник

См. также

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

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

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