344
правки
Изменения
→Вычитание
К ним также применимы алгоритмы быстрого умножения: [[Быстрое преобразование Фурье | Быстрое преобразование Фурье]] и [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 Алгоритм Карацубы].
=== Сложение ===
Алгоритм не требует дополнительной памяти.
'''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] <tex>\geqslant</tex> 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() <font color=green>//Здесь мы после выполнения вычитания удаляем лидирующие нули, чтобы поддерживать предикат о том, что таковые отсутствуют.</font> '''return''' a
=== Умножение длинного на короткое ===
Алгоритм требует <tex>O(n)</tex> памяти, где <tex>n</tex> — длина длинного числа.
'''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] <tex>\cdot</tex> b; a[i] = cur '''mod''' base carry = cur / base i++ '''whilereturn''' a.size() > 1 && a.back() == 0 a.pop_back() <font color=green>//Здесь мы после выполнения деления удаляем лидирующие нули, чтобы поддерживать предикат о том, что таковые отсутствуют.</font>
=== Умножение двух длинных чисел ===
Алгоритм требует <tex>O(n \cdot m)</tex> памяти, где <tex>n, m</tex> — длины чисел <tex>a</tex> и <tex>b</tex>.
'''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] <tex>\cdot</tex> b[j] + carry '''else''' cur = c[i + j] + carry c[i + j] = cur '''mod''' base carry = cur / base i j++ j i++ '''while''' c.size() > 1 && c.back() == 0 c.pop_back() '''return''' c
=== Деление длинного на короткое ===
Алгоритм не требует дополнительной памяти.
== См. также ==
== Источники информации ==
* [http://e-maxx.ru/algo/big_integer e-maxx: Длинная арифметика]
[[Категория: Алгоритмы алгебры и теории чисел]]
[[Категория: Теория чисел]]