344
правки
Изменения
Нет описания правки
==Представление в памяти==
Один из вариантов хранения длинных чисел — массив целых чисел '''int''', где каждый элемент — это одна цифра числа в ''<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</tex> число <tex>b\,(a \geqslant b)</tex> и сохраняет результат в <tex> a</tex>:
Алгоритм работает за <tex>O(max(n, m))</tex>, где <tex>n, m</tex> — длины чисел <tex>a</tex> и <tex>b</tex>.
=== Умножение длинного на короткое ===
Умножает длинное <tex>a</tex> на короткое <tex>b \, (b < base)</tex> и сохраняет результат в <tex>a</tex> :
Алгоритм работает за <tex>O(n)</tex>, где <tex>n</tex> — длина длинного числа.
=== Деление длинного на короткое ===
Делит длинное <tex>a</tex> на короткое <tex>b \, (b < base)</tex>, частное сохраняет в <tex>a</tex>, остаток в <tex>carry</tex> :
Алгоритм работает за <tex>O(n)</tex>, где <tex>n</tex> — длина длинного числа.
