344
правки
Изменения
Добавлены операции - псевдокод
Длинная арифметика (англ. ''arbitrary-precision arithmetic'', или ''bignum arithmetic'') — это набор программных средств (структуры данных и алгоритмы), которые позволяют работать с числами гораздо больших величин, чем это позволяют стандартные типы данных.
}}
{{Определение|definition==Классическая длинная арифметика==Основная — длинная арифметика, основная идея "классической длинной арифметики" которой заключается в том, что число хранится в виде массива его цифр.Цифры могут использоваться из той или иной системы счисления, обычно применяются десятичная система счисления и её степени (десять тысяч, миллиард), двоичная система счисления либо любая другая.}}
==Представление в памяти==
Один из вариантов хранения длинных чисел — массив целых чисел<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()
==Подбор значения очередной цифры в алгоритме деления в столбик==
Заметим, что в конце сложения будет лишний перенос на единицу, о котором нужно забыть (он компенсирует последний перенос <tex>(-1)</tex>).
[http://forum.sources.ru/index.php?showtopic=210512&hl=Источник]
== Источники информации ==
