344
правки
Изменения
→Вычитание
==Представление в памяти==
Один из вариантов хранения длинных чисел — массив целых чисел <tex>'''int</tex>''', где каждый элемент — это одна цифра числа в ''<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>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: Длинная арифметика]
[[Категория: Алгоритмы алгебры и теории чисел]]
[[Категория: Теория чисел]]