Длинное умножение 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()

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

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

Answer 1

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

Answer 2

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

Библиотека 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 3

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

Вот пример с немного измененной версией вашего кода.Обратите внимание, что преобразование строки из 100 000 цифр в длинную на этом компьютере уже занимает ~ 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 4

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