Арифметика чисел в b-ичной системе счисления (Длинная арифметика)
| Определение: |
| Длинная арифметика (англ. arbitrary-precision arithmetic, или bignum arithmetic) — это набор программных средств (структуры данных и алгоритмы), которые позволяют работать с числами гораздо больших величин, чем это позволяют стандартные типы данных. |
| Определение: |
| Классическая длинная арифметика — длинная арифметика, основная идея которой заключается в том, что число хранится в виде массива его цифр. Цифры могут использоваться из той или иной системы счисления, обычно применяются десятичная система счисления и её степени (десять тысяч, миллиард), двоичная система счисления либо любая другая. |
Представление в памяти
Один из вариантов хранения длинных чисел — массив целых чисел int, где каждый элемент — это одна цифра числа в -ичной системе счисления. Для повышения эффективности каждый элемент вектора может содержать не одну, а несколько цифр (например, работаем в системе счисления по основанию миллиард, тогда каждый элемент вектора содержит цифр):
const int base 1000 1000 1000
Цифры будут храниться в массиве в следующем порядке: сначала идут наименее значимые цифры (т.е., например, единицы, десятки, сотни, и т.д.).
Кроме того, все операции реализуются таким образом, что после выполнения любой из них лидирующие нули (т.е. лишние нули в начале числа) отсутствуют (разумеется, в предположении, что перед каждой операцией лидирующие нули также отсутствуют). Следует отметить, что в представленной реализации для числа ноль корректно поддерживаются сразу два представления: пустой вектор цифр, и вектор цифр, содержащий единственный элемент — ноль.
Операции над числами
Операции над числами производятся с помощью "школьных" алгоритмов сложения, вычитания, умножения, деления столбиком. После совершения операций следует не забывать удалять лидирующие нули, чтобы поддерживать предикат о том, что таковые отсутствуют. К ним также применимы алгоритмы быстрого умножения: Быстрое преобразование Фурье и Алгоритм Карацубы.
Приведённые ниже алгоритмы корректны в силу того, что они являются реализацией "школьных" алгоритмов действий в столбик:
Тогда сумма
Разность
Произведение
Сложение
Прибавляет к числу число и сохраняет результат в :
Алгоритм работает за , где — длины чисел и .
Алгоритм не требует дополнительной памяти.
function getSum(a: )
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] base
if carry
a[i] -= base
i++
Вычитание
Отнимает от числа число и сохраняет результат в :
Алгоритм работает за , где — длины чисел и .
Алгоритм не требует дополнительной памяти.
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()
//Здесь мы после выполнения вычитания удаляем лидирующие нули, чтобы поддерживать предикат о том, что таковые отсутствуют.
Умножение длинного на короткое
Умножает длинное на короткое и сохраняет результат в :
Алгоритм работает за , где — длина длинного числа.
Алгоритм требует памяти, где — длина длинного числа.
carry = 0
i = 0
while i < a.size() || carry
if i == a.size()
a.push_back(0)
cur = carry + a[i] b;
a[i] = cur mod base
carry = cur / base
i++
Умножение двух длинных чисел
Умножает на и результат сохраняет в :
Алгоритм работает за , где — длины чисел и .
Алгоритм требует памяти, где — длины чисел и .
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] b[j] + carry
else
cur = c[i + j] + carry
c[i + j] = cur mod base
carry = cur / base
i++
j++
while c.size() > 1 && c.back() == 0
c.pop_back()
Деление длинного на короткое
Делит длинное на короткое , частное сохраняет в , остаток в :
Алгоритм работает за , где — длина длинного числа.
Алгоритм не требует дополнительной памяти.
carry = 0 i = a.size() - 1 while i 0 cur = a[i] + carry base a[i] = cur mod base carry = cur / base i-- while a.size() > 1 && a.back() == 0 a.pop_back()
