Python длинное умножение

Question

Мне нужен алгоритм быстрее, чем текущее нормальное длинное умножение Python.

Я пытался найти достойную реализацию Карацубы, но не могу.

def main():
    a=long(raw_input())
    if(a<0):
        a=a*-1
        a=((a*(a+1)/2)-1)
        print(-a)
    else:
        a=(a*(a+1))/2
        print(a)
main()

Как видите, ничего сложного, только несколько умножений. Но он должен обрабатывать числа до 100000 цифр менее чем за 2,5 секунды.

Я хотел бы получить фрагмент функции или просто ссылку на реализацию более быстрой функции умножения или что-нибудь полезное.

Answer 1

Я являюсь автором библиотеки DecInt (Десятичное целое), поэтому сделаю несколько комментариев.

Библиотека DecInt была специально разработана для работы с очень большими целыми числами, которые нужно было преобразовать в десятичный формат. Проблема с преобразованием в десятичный формат состоит в том, что большинство библиотек произвольной точности хранят значения в двоичном формате. Это самый быстрый и самый эффективный способ использования памяти, но преобразование из двоичного в десятичное обычно выполняется медленно. Преобразование двоичного числа в десятичное в Python использует алгоритм O (n ^ 2) и очень медленно работает.

DecInt использует большое десятичное число (обычно 10 ^ 250) и хранит очень большое число в блоках по 250 цифр. Преобразование очень большого числа в десятичный формат теперь выполняется в O (n).

Наивное, или начальное, умножение имеет время выполнения O (n ^ 2). Python использует умножение Карацубы со временем выполнения O (n ^ 1.585). DecInt использует комбинацию свертки Карацубы, Тоум-Кука и Нуссбаумера, чтобы получить время пробега O (n * ln (n)).

Даже несмотря на то, что DecInt имеет гораздо более высокие издержки, комбинация умножения O (n * ln (n)) и преобразования O (n) в конечном итоге будет быстрее, чем умножение O (n ^ 1.585) в Python и O (n ^ 2) преобразование.

Поскольку для большинства вычислений не требуется отображать каждый результат в десятичном формате, почти каждая библиотека с произвольной точностью использует двоичный код, поскольку это облегчает вычисления. DecInt предназначается для очень маленькой ниши. Для достаточно больших чисел DecInt будет быстрее для умножения и деления, чем родной Python. Но если вы стремитесь к чистой производительности, библиотека, подобная GMPY, будет самой быстрой.

Я рад, что вы нашли DecInt полезным.

Answer 2

15,9 мс на моем медленном ноутбуке. Это печать, которая замедляет вас. Преобразование двоичных чисел в десятичные довольно медленное, что является обязательным этапом его распечатки. Если вам нужно вывести число, вы должны попробовать уже упомянутый DecInt ChristopheD.

DecInt будет медленнее выполнять умножение, но сделает печать намного быстрее

In [34]: a=2**333000

In [35]: len(str(a))
Out[35]: 100243

In [36]: b=2**333001

In [37]: len(str(b))
Out[37]: 100244

In [38]: timeit c=a*b
10 loops, best of 3: 15.9 ms per loop

Вот пример со слегка измененной версией вашего кода. Обратите внимание, что преобразование строки длиной 100000 цифр в длинную уже занимает ~ 1сек на этом компьютере

In [1]: def f(a):
   ...:     if(a<0):
   ...:         a=a*-1
   ...:         a=((a*(a+1)/2)-1)
   ...:     else:
   ...:         a=(a*(a+1))/2
   ...:     return a
   ...: 

In [2]: a=3**200000

In [3]: len(str(a))
Out[3]: 95425

In [4]: timeit f(a)
10 loops, best of 3: 417 ms per loop

Answer 3

Вы можете взглянуть на реализацию модуля DecInt (доступна чистая версия Python (Toom-Cook), хотя самая быстрая, вероятно, будет при использовании gmpy ).

Answer 4

Я предлагаю вам получить Sage math tool , в котором есть почти все математические инструменты Python, когда-либо сделанные в одном пакете. Посмотрите, есть ли в Sage хороший быстрый математический инструмент произвольной точности, который отвечает вашим потребностям.