Арифметика чисел в b-ичной системе счисления (Длинная арифметика)
| НЕТ ВОЙНЕ |
|
24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян. Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием. Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей. Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить. Антивоенный комитет России |
| Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению. |
| meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки. |
| Определение: |
| Длинная арифметика (англ. arbitrary-precision arithmetic, или bignum arithmetic) — это набор программных средств (структуры данных и алгоритмы), которые позволяют работать с числами гораздо больших величин, чем это позволяют стандартные типы данных. |
| Определение: |
| Классическая длинная арифметика — длинная арифметика, основная идея которой заключается в том, что число хранится в виде массива его цифр. Цифры могут использоваться из той или иной системы счисления, обычно применяются десятичная система счисления и её степени (десять тысяч, миллиард), двоичная система счисления либо любая другая. |
Представление в памяти
Один из вариантов хранения длинных чисел — массив целых чисел int, где каждый элемент — это одна цифра числа в -ичной системе счисления. Для повышения эффективности каждый элемент вектора может содержать не одну, а несколько цифр (например, работаем в системе счисления по основанию миллиард, тогда каждый элемент вектора содержит цифр):
const int base 1000 1000 1000
Цифры будут храниться в массиве в следующем порядке: сначала идут наименее значимые цифры (т.е., например, единицы, десятки, сотни, и т.д.).
Кроме того, все операции реализуются таким образом, что после выполнения любой из них лидирующие нули (т.е. лишние нули в начале числа) отсутствуют (разумеется, в предположении, что перед каждой операцией лидирующие нули также отсутствуют). Следует отметить, что в представленной реализации для числа ноль корректно поддерживаются сразу два представления: пустой вектор цифр, и вектор цифр, содержащий единственный элемент — ноль.
Операции над числами
Операции над числами производятся с помощью "школьных" алгоритмов сложения, вычитания, умножения, деления столбиком. После совершения операций следует не забывать удалять лидирующие нули, чтобы поддерживать предикат о том, что таковые отсутствуют. К ним также применимы алгоритмы быстрого умножения: Быстрое преобразование Фурье и Алгоритм Карацубы.
Приведённые ниже алгоритмы корректны в силу того, что они являются реализацией "школьных" алгоритмов действий в столбик:
Тогда сумма
Разность
Произведение
Сложение
Прибавляет к числу число и сохраняет результат в :
Алгоритм работает за , где — длины чисел и .
Алгоритм не требует дополнительной памяти.
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] base
if carry
a[i] -= base
i++
return a
Вычитание
Отнимает от числа число и сохраняет результат в :
Алгоритм работает за , где — длины чисел и .
Алгоритм не требует дополнительной памяти.
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()
//Здесь мы после выполнения вычитания удаляем лидирующие нули, чтобы поддерживать предикат о том, что таковые отсутствуют.
return a
Умножение длинного на короткое
Умножает длинное на короткое и сохраняет результат в :
Алгоритм работает за , где — длина длинного числа.
Алгоритм требует памяти, где — длина длинного числа.
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] b;
a[i] = cur mod base
carry = cur / base
i++
return a
Умножение двух длинных чисел
Умножает на и результат сохраняет в :
Алгоритм работает за , где — длины чисел и .
Алгоритм требует памяти, где — длины чисел и .
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] 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
Деление длинного на короткое
Делит длинное на короткое , частное сохраняет в , остаток в :
Алгоритм работает за , где — длина длинного числа.
Алгоритм не требует дополнительной памяти.
function getDivLongShort(a: vector<int>, b: int): vector<int>
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()
return a
