Арифметика чисел в b-ичной системе счисления (Длинная арифметика) — различия между версиями
Senya (обсуждение | вклад) м (Метки: правка с мобильного устройства, правка из мобильной версии) |
Senya (обсуждение | вклад) (Добавлены операции - псевдокод) (Метки: правка с мобильного устройства, правка из мобильной версии) |
||
Строка 3: | Строка 3: | ||
Длинная арифметика (англ. ''arbitrary-precision arithmetic'', или ''bignum arithmetic'') — это набор программных средств (структуры данных и алгоритмы), которые позволяют работать с числами гораздо больших величин, чем это позволяют стандартные типы данных. | Длинная арифметика (англ. ''arbitrary-precision arithmetic'', или ''bignum arithmetic'') — это набор программных средств (структуры данных и алгоритмы), которые позволяют работать с числами гораздо больших величин, чем это позволяют стандартные типы данных. | ||
}} | }} | ||
− | + | {{Определение | |
− | = | + | |definition= |
− | + | Классическая длинная арифметика — длинная арифметика, основная идея которой заключается в том, что число хранится в виде массива его цифр. Цифры могут использоваться из той или иной системы счисления, обычно применяются десятичная система счисления и её степени (десять тысяч, миллиард), двоичная система счисления либо любая другая. | |
− | Цифры могут использоваться из той или иной системы счисления, обычно применяются десятичная система счисления и её степени (десять тысяч, миллиард), двоичная система счисления либо любая другая. | + | }} |
− | |||
==Представление в памяти== | ==Представление в памяти== | ||
− | Один из вариантов хранения длинных чисел — массив целых чисел, где каждый элемент — это одна цифра числа в ''b''-ичной системе счисления. | + | Один из вариантов хранения длинных чисел — массив целых чисел <tex>int</tex>, где каждый элемент — это одна цифра числа в ''b''-ичной системе счисления. |
Цифры будут храниться в массиве в следующем порядке: сначала идут наименее значимые цифры (т.е., например, единицы, десятки, сотни, и т.д.). | Цифры будут храниться в массиве в следующем порядке: сначала идут наименее значимые цифры (т.е., например, единицы, десятки, сотни, и т.д.). | ||
Кроме того, все операции реализуются таким образом, что после выполнения любой из них лидирующие нули (т.е. лишние нули в начале числа) отсутствуют (разумеется, в предположении, что перед каждой операцией лидирующие нули также отсутствуют). Следует отметить, что в представленной реализации для числа ноль корректно поддерживаются сразу два представления: пустой вектор цифр, и вектор цифр, содержащий единственный элемент — ноль. | Кроме того, все операции реализуются таким образом, что после выполнения любой из них лидирующие нули (т.е. лишние нули в начале числа) отсутствуют (разумеется, в предположении, что перед каждой операцией лидирующие нули также отсутствуют). Следует отметить, что в представленной реализации для числа ноль корректно поддерживаются сразу два представления: пустой вектор цифр, и вектор цифр, содержащий единственный элемент — ноль. | ||
− | == | + | ==Операции над числами== |
Операции над числами производятся с помощью "школьных" алгоритмов сложения, вычитания, умножения, деления столбиком. | Операции над числами производятся с помощью "школьных" алгоритмов сложения, вычитания, умножения, деления столбиком. | ||
После совершения операций следует не забывать удалять лидирующие нули, чтобы поддерживать предикат о том, что таковые отсутствуют. | После совершения операций следует не забывать удалять лидирующие нули, чтобы поддерживать предикат о том, что таковые отсутствуют. | ||
+ | К ним также применимы алгоритмы быстрого умножения: Быстрое преобразование Фурье и Алгоритм Карацубы. | ||
+ | |||
+ | === Сложение === | ||
+ | <font color=green>//Прибавляет к числу a число b и сохраняет результат в a:</font> | ||
+ | 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] <tex>\geqslant</tex> base | ||
+ | '''if''' carry | ||
+ | a[i] -= base | ||
+ | i++ | ||
+ | === Вычитание === | ||
+ | <font color=green>//Отнимает от числа a число b (a \ge b) и сохраняет результат в a:</font> | ||
+ | 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() | ||
+ | <font color=green>//Здесь мы после выполнения вычитания удаляем лидирующие нули, чтобы поддерживать предикат о том, что таковые отсутствуют.</font> | ||
+ | === Умножение длинного на короткое === | ||
+ | <font color=green>//Умножает длинное a на короткое b (b < {\rm base}) и сохраняет результат в a:</font> | ||
+ | carry = 0 | ||
+ | i = 0 | ||
+ | '''while''' i < a.size() || carry | ||
+ | '''if''' i == a.size() | ||
+ | a.push_back (0) | ||
+ | '''long long''' cur = carry + a[i] <tex>\cdot</tex> 1ll <tex>\cdot</tex> b; | ||
+ | a[i] = cur '''mod''' base | ||
+ | carry = cur / base | ||
+ | i++ | ||
+ | '''while''' a.size() > 1 && a.back() == 0 | ||
+ | a.pop_back() | ||
+ | <font color=green>//Здесь мы после выполнения деления удаляем лидирующие нули, чтобы поддерживать предикат о том, что таковые отсутствуют.</font> | ||
+ | |||
+ | === Умножение двух длинных чисел === | ||
+ | <font color=green>//Умножает a на b и результат сохраняет в c:</font> | ||
+ | carry = 0 | ||
+ | i = 0 | ||
+ | '''while''' i < a.size() | ||
+ | j = 0 | ||
+ | '''while''' (j < b.size() || carry) | ||
+ | '''long long''' cur = c[i+j] + a[i] <tex>\cdot</tex> 1ll <tex>\cdot</tex> (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() | ||
+ | |||
+ | === Деление длинного на короткое === | ||
+ | <font color=green>//Делит длинное a на короткое b (b < {\rm base}), частное сохраняет в a, остаток в carry:</font> | ||
+ | carry = 0 | ||
+ | i = a.size()-1 | ||
+ | '''while''' i \geqslant 0 | ||
+ | '''long long''' cur = a[i] + carry <tex>\cdot</tex> 1ll <tex>\cdot</tex> base | ||
+ | a[i] = cur '''mod''' base | ||
+ | carry = cur / base | ||
+ | i-- | ||
+ | '''while''' a.size() > 1 && a.back() == 0 | ||
+ | a.pop_back() | ||
+ | |||
==Подбор значения очередной цифры в алгоритме деления в столбик== | ==Подбор значения очередной цифры в алгоритме деления в столбик== | ||
Строка 41: | Строка 109: | ||
Заметим, что в конце сложения будет лишний перенос на единицу, о котором нужно забыть (он компенсирует последний перенос <tex>(-1)</tex>). | Заметим, что в конце сложения будет лишний перенос на единицу, о котором нужно забыть (он компенсирует последний перенос <tex>(-1)</tex>). | ||
− | http://forum.sources.ru/index.php?showtopic=210512&hl= | + | [http://forum.sources.ru/index.php?showtopic=210512&hl= Источник] |
== Источники информации == | == Источники информации == |
Версия 00:33, 12 мая 2018
Определение: |
Длинная арифметика (англ. arbitrary-precision arithmetic, или bignum arithmetic) — это набор программных средств (структуры данных и алгоритмы), которые позволяют работать с числами гораздо больших величин, чем это позволяют стандартные типы данных. |
Определение: |
Классическая длинная арифметика — длинная арифметика, основная идея которой заключается в том, что число хранится в виде массива его цифр. Цифры могут использоваться из той или иной системы счисления, обычно применяются десятичная система счисления и её степени (десять тысяч, миллиард), двоичная система счисления либо любая другая. |
Содержание
Представление в памяти
Один из вариантов хранения длинных чисел — массив целых чисел
, где каждый элемент — это одна цифра числа в 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]
base
if carry
a[i] -= base
i++
Вычитание
//Отнимает от числа a число b (a \ge 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 < {\rm 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]1ll 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]1ll (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 < {\rm base}), частное сохраняет в a, остаток в carry: carry = 0 i = a.size()-1 while i \geqslant 0 long long cur = a[i] + carry1ll base a[i] = cur mod base carry = cur / base i-- while a.size() > 1 && a.back() == 0 a.pop_back()
Подбор значения очередной цифры в алгоритме деления в столбик
Подбор следующей цифры
частного можно производить с помощью стандартного алгоритма двоичного поиска за .Но также существуют и более быстрые алгоритмы. Довольно интересный способ состоит в высказывании догадки (qGuess) по первым цифрам делителя и делимого. Понятно, что этих нескольких цифр недостаточно для гарантированно правильного результата, однако неплохое приближение все же получится. Пусть очередной шаг представляет собой деление некоторого
на . Если BASE (где BASE — основание системы счисления), то можно доказать следующие факты:- 1. Если положить qGuess BASE , то qGuess qGuess.
Иначе говоря, вычисленная таким способом “догадка” будет не меньше искомого частного, но может быть больше на
или .- 2. Если же дополнительно выполняется неравенство qGuess BASE , где – остаток при нахождении qGuess и qGuess BASE, то qGuess qGuess, причем вероятность события qGuess приблизительно равна BASE.
Таким образом, если
BASE , то можно вычислить qGuess BASE и уменьшать на единицу до тех пор, пока не станут выполняться условия. Получившееся значение будет либо правильным частным , либо, с вероятностью BASE, на единицу большим числом.Что делать, если
слишком мало, чтобы пользоваться таким способом? Например, можно домножить делитель и делимое на одно и то же число scale BASE . В случае, если основание системы счисления является степенью двойки, scale можно выбрать соответствующей степенью двойки. При этом несколько изменится способ вычисления остатка, а частное останется прежним. Такое домножение иногда называют нормализацией числа. На тот случай, если qGuess получилось все же на единицу большим , будем использовать вычитание, которое вместо отрицательного числа даст дополнение до следующей степени основания. Если такое произошло, то последний перенос будет равен . Это сигнал, что необходимо прибавить одно B назад. Заметим, что в конце сложения будет лишний перенос на единицу, о котором нужно забыть (он компенсирует последний перенос ).