344
правки
Изменения
→Вычитание
Алгоритм не требует дополнительной памяти.
'''function''' getDifferencegetSub(a: '''vector<int>''', b: '''vector<int>'''): '''vector<int>'''
carry = 0
i = 0
Алгоритм требует <tex>O(n)</tex> памяти, где <tex>n</tex> — длина длинного числа.
'''function''' getCompLongShort(a: '''vector<int>''', b: '''int'''): '''vector<int>'''
carry = 0
i = 0
Алгоритм требует <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: Длинная арифметика]
[[Категория: Алгоритмы алгебры и теории чисел]]
[[Категория: Теория чисел]]
