Просмотр исходного текста страницы Арифметика чисел в b-ичной системе счисления (Длинная арифметика)

{{Определение
|definition=
'''Длинная арифметика''' (англ. ''arbitrary-precision arithmetic'', или ''bignum arithmetic'') — это набор программных средств (структуры данных и алгоритмы), которые позволяют работать с числами гораздо больших величин, чем это позволяют стандартные типы данных.
}}
{{Определение
|definition=
'''Классическая длинная арифметика''' — длинная арифметика, основная идея которой заключается в том, что число хранится в виде массива его цифр. Цифры могут использоваться из той или иной системы счисления, обычно применяются десятичная система счисления и её степени (десять тысяч, миллиард), двоичная система счисления либо любая другая.
}}
==Представление в памяти==

Один из вариантов хранения длинных чисел — массив целых чисел '''int''', где каждый элемент — это одна цифра числа в <tex>b</tex>-ичной системе счисления.
Для повышения эффективности каждый элемент вектора может содержать не одну, а несколько цифр (например, работаем в системе счисления по основанию миллиард, тогда каждый элемент вектора содержит <tex>9</tex> цифр): 
   '''const''' '''int''' base <tex>\,=\,</tex> 1000 <tex>\cdot</tex> 1000 <tex>\cdot</tex> 1000

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

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

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

Операции над числами производятся с помощью "школьных" алгоритмов сложения, вычитания, умножения, деления столбиком.
После совершения операций следует не забывать удалять лидирующие нули, чтобы поддерживать предикат о том, что таковые отсутствуют.
К ним также применимы алгоритмы быстрого умножения: [[Быстрое преобразование Фурье | Быстрое преобразование Фурье]] и [https://ru.wikipedia.org/wiki/%D0%A3%D0%BC%D0%BD%D0%BE%D0%B6%D0%B5%D0%BD%D0%B8%D0%B5_%D0%9A%D0%B0%D1%80%D0%B0%D1%86%D1%83%D0%B1%D1%8B Алгоритм Карацубы].

Приведённые ниже алгоритмы корректны в силу того, что они являются реализацией "школьных" алгоритмов действий в столбик:

<tex>A = abc = 100 \cdot a + 10 \cdot b + c </tex>

<tex>B = de = 10 \cdot d + e </tex>

Тогда сумма <tex>A + B = abc + de = (100 \cdot a + 10 \cdot b + c) + (10 \cdot d + e) = 100 \cdot a + 10 \cdot (b + d) + (c + e) </tex>

Разность <tex>A - B = abc - de = (100 \cdot a + 10 \cdot b + c) - (10 \cdot d + e) = 100 \cdot a + 10 \cdot (b - d) + (c - e) </tex>

Произведение <tex>A \cdot B = abc \cdot de = (100 \cdot a + 10 \cdot b + c) \cdot (10 \cdot d + e) = 100 \cdot a \cdot 10 \cdot d + 10 \cdot b \cdot 10 \cdot d + c \cdot 10 \cdot d + 100 \cdot a \cdot e + 10 \cdot b \cdot e + c \cdot e = 1000 \cdot a \cdot d + 100 \cdot (a \cdot e + b \cdot d) + 10 \cdot (b \cdot e + c \cdot d) + c \cdot e</tex>

=== Сложение ===
Прибавляет к числу <tex>a</tex> число <tex>b</tex> и сохраняет результат в <tex>a</tex> :

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

Алгоритм не требует дополнительной памяти.

     '''function''' getSum(a: '''vector<int>''', b: '''vector<int>'''): '''vector<int>'''
         carry = 0
         i = 0
         '''while''' i < max(a.size(),b.size()) || carry
             '''if''' i == a.size()
                 a.push_back(0)
             '''if''' i < b.size()
                 a[i] += carry + b[i]
             '''else'''
                 a[i] += carry
             carry = a[i] <tex>\geqslant</tex> base
             '''if''' carry
                 a[i] -= base
             i++
         '''return''' a

=== Вычитание ===
Отнимает от числа <tex>a</tex> число <tex>b\,(a \geqslant b)</tex>  и сохраняет результат в <tex> a</tex>:

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

Алгоритм не требует дополнительной памяти.
     '''function''' getSub(a: '''vector<int>''', b: '''vector<int>'''): '''vector<int>'''
         carry = 0
         i = 0
         '''while''' i < b.size() || carry
             '''if''' i < b.size()
                 a[i] -= carry + b[i]
             '''else'''
                 a[i] -= carry
             carry = a[i] < 0
             '''if''' carry
                 a[i] += base
             i++
         '''while''' a.size() > 1 && a.back() == 0
             a.pop_back()
         <font color=green>//Здесь мы после выполнения вычитания удаляем лидирующие нули, чтобы поддерживать предикат о том, что таковые отсутствуют.</font>
         '''return''' a

=== Умножение длинного на короткое ===
Умножает длинное <tex>a</tex> на короткое <tex>b\, (b < base)</tex> и сохраняет результат в <tex>a</tex> :

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

Алгоритм требует <tex>O(n)</tex> памяти, где <tex>n</tex> — длина длинного числа.

     '''function''' getCompLongShort(a: '''vector<int>''', b: '''int'''): '''vector<int>'''
         carry = 0
         i = 0
         '''while''' i < a.size() || carry
             '''if''' i == a.size()
                 a.push_back(0)
             cur = carry + a[i] <tex>\cdot</tex> b;
             a[i] = cur '''mod''' base
             carry = cur / base
             i++
         '''return''' a

=== Умножение двух длинных чисел ===
Умножает <tex>a</tex> на <tex>b</tex> и результат сохраняет в <tex>c</tex> :

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

Алгоритм требует <tex>O(n \cdot m)</tex> памяти, где <tex>n, m</tex> — длины чисел <tex>a</tex> и <tex>b</tex>.

     '''function''' getCompLongLong(a: '''vector<int>''', b: '''vector<int>'''): '''vector<int>'''
         carry = 0
         i = 0
         '''while''' i < a.size()
             j = 0
             '''while''' (j < b.size() || carry)
                 '''if''' j < b.size()
                     cur = c[i + j] + a[i] <tex>\cdot</tex> b[j] + carry
                 '''else'''
                     cur = c[i + j] + carry
                 c[i + j] = cur '''mod''' base
                 carry = cur / base
                 j++
             i++
         '''while''' c.size() > 1 && c.back() == 0
             c.pop_back()
         '''return''' c

=== Деление длинного на короткое  ===
Делит длинное <tex>a</tex> на короткое <tex>b\, (b < base)</tex>, частное сохраняет в <tex>a</tex>, остаток в <tex>carry</tex> :

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

Алгоритм не требует дополнительной памяти.
    
     '''function''' getDivLongShort(a: '''vector<int>''', b: '''int'''): '''vector<int>'''
         carry = 0
         i = a.size() - 1
         '''while''' i <tex>\geqslant</tex> 0
             cur = a[i] + carry <tex>\cdot</tex> base
             a[i] = cur '''mod''' base
             carry = cur / base
             i--
         '''while''' a.size() > 1 && a.back() == 0
             a.pop_back()
         '''return''' a

== См. также ==
*[[Системы счисления | Системы счисления]]
*[[Разложение на множители (факторизация) | Разложение на множители (факторизация)]]


== Источники информации ==
* [http://e-maxx.ru/algo/big_integer e-maxx: Длинная арифметика]


[[Категория: Алгоритмы алгебры и теории чисел]]
[[Категория: Теория чисел]]