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

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

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

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

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

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

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

  const int base [math]\,=\,[/math] 1000 [math]\cdot[/math] 1000 [math]\cdot[/math] 1000

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

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

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

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

Сложение

Алгоритм работает за [math]O(max(n, m))[/math], где [math]n, m[/math] — длины чисел [math]a[/math] и [math]b[/math].

Алгоритм требует [math]O(n + m)[/math] памяти, где [math]n, m[/math] — длины чисел [math]a[/math] и [math]b[/math].

   //Прибавляет к числу 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++

Вычитание

Алгоритм работает за [math]O(max(n, m))[/math], где [math]n, m[/math] — длины чисел [math]a[/math] и [math]b[/math].

   //Отнимает от числа 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()
   //Здесь мы после выполнения вычитания удаляем лидирующие нули, чтобы поддерживать предикат о том, что таковые отсутствуют.

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

Алгоритм работает за [math]O(n)[/math], где [math]n[/math] — длина длинного числа.

   //Умножает длинное 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()
   //Здесь мы после выполнения деления удаляем лидирующие нули, чтобы поддерживать предикат о том, что таковые отсутствуют.

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

Алгоритм работает за [math]O(n \cdot m)[/math], где [math]n, m[/math] — длины чисел [math]a[/math] и [math]b[/math].

   //Умножает 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()

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

Алгоритм работает за [math]O(n)[/math], где [math]n[/math] — длина длинного числа.

   //Делит длинное a на короткое b (b < base), частное сохраняет в a, остаток в carry:
   carry = 0
   i = a.size()-1
   while i [math]\geqslant[/math] 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()

См. также

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

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

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