- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
def karatsuba_multiplication(x : int, y : int) -> int:
sx, sy = map(lambda x: '0' + str(x) if len(str(x)) % 2 != 0 else str(x), (x, y))
return _karatsuba_multiplication(sx, sy, max(len(sx), len(sy)))
def _prepend_nils(string : str, amount_of_nils : int) -> str:
return ('0' * amount_of_nils + string)
def _karatsuba_multiplication(x : str, y : str, n : int) -> int:
x, y = map(lambda x: _prepend_nils(x, (n - len(x))), (x, y))
if (n == 1):
return (int(x) * int(y))
mid = n // 2
a, b = int(x[:mid]), int(x[mid:])
c, d = int(y[:mid]), int(y[mid:])
p = a + b
q = c + d
ac = _karatsuba_multiplication(str(a), str(c), max(len(str(a)), len(str(c))))
bd = _karatsuba_multiplication(str(b), str(d), max(len(str(b)), len(str(d))))
pq = _karatsuba_multiplication(str(p), str(q), max(len(str(p)), len(str(q))))
adbc = pq - ac - bd
return 10**n * ac + 10**(mid + n % 2) * adbc + bd
CEO -- seo
Drug -- друг
Examine -- экзамен
Faggot -- фагот
Most -- мост
Piston -- пистон
Resin -- резина
Sewer -- север
Tort -- торт
Velvet -- вельвет
http://www.govnokod.ru/25095
Если хранить числа по 9 десятичных знаков (только тут не уверен, что норм хранить в десятичных), то около ста интов получится.
У FFT оверхед адовый, оно не окупается для мелочи.