DjangoBB LoFi version

Полная версия: Перемножить два гигантских числа. Преобразование Фурье/метод Карацюбы

Начало » Центр помощи » Перемножить два гигантских числа. Преобразование Фурье/метод Карацюбы

nika-designer

Дек. 10, 2014 10:14:41

Нужно каким-то образом перемножить два длинных числа, по размеру превосходящих вместимость любого типа данных, с помощью быстрого преобразования Фурье или метода Карацюбы. Может, кто делал? Если нет, то может, идеи есть?

botinag

Дек. 10, 2014 12:24:30

есть идея поискать в гугле для вашего Карацубы
… или для Фурье

Alen

Дек. 10, 2014 12:38:04

https://pypi.python.org/pypi/gmpy2/2.0.4

>>> from gmpy2 import mpz
>>> mpz('100000000000000000000') * mpz('1000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000')
mpz(1000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000L)