Python longo multiplicação

Question

Eu estou precisando de um algoritmo mais rápido do que o longo multiplicação normal do Python atual.

Eu tentei encontrar uma implementação Karatsuba decente, mas eu não posso.

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()

Como você pode ver, não é nada complicado, a poucos multiplicações. Mas tem que lidar com números com até 100.000 dígitos em menos de 2,5 s.

Eu gostaria algum trecho de uma função ou apenas um link para alguns implementação de uma função mais rápida multiplicação, ou qualquer coisa que ajuda.

Answer 1

Você poderia ter um olhar para a implementação do DecInt módulo (versão pura Python é disponível (Toom-Cook), embora o mais rápido que provavelmente será ao usar gmpy ).

Answer 2

Eu sou o autor da biblioteca DecInt (Decimal Integer), então eu vou fazer alguns comentários.

A biblioteca DecInt foi projetado especificamente para trabalhar com grandes números inteiros que precisavam ser convertidos para o formato decimal. O problema com a conversão para o formato decimal é que a maioria das bibliotecas de precisão arbitrária armazenar valores em binário. Esta é mais rápido e eficiente para a utilização de memória, mas a conversão de binário para decimal é geralmente lento. binário de Python à conversão decimal usa um O (n ^ 2) algoritmo e fica lento muito rapidamente.

DecInt utiliza uma grande radix decimal (geralmente 10 ^ 250) e armazena o número muito grande em blocos de 250 dígitos. A conversão de um número muito grande de formato decimal agora executado em O (n).

ou escola primária Naive, multiplicação tem um tempo de execução de O (n ^ 2). Python usa Karatsuba multiplicação que tem tempo de execução de O (N ^ 1,585). DecInt usa uma combinação de Karatsuba, Toom-Cook, e Nussbaumer convolução para obter um tempo de execução de O (n * ln (n)).

Embora DecInt tem muito maior sobrecarga, a combinação de S (n * ln (n)) a multiplicação e a conversão de O (n) irá eventualmente ser mais rápido do que ó do Python (n ^ 1,585) multiplicação e O (n ^ 2) conversão.

Como a maioria dos cálculos não necessitam cada resultado a ser exibido no formato decimal, quase todos os biblioteca de precisão arbitrária usa binário desde que faz os cálculos mais fácil. DecInt como alvo um nicho muito pequeno. Para número suficiente, DecInt será mais rápido para multiplicação e divisão do que Python nativa. Mas se você estiver após desempenho puro, uma biblioteca como GMPY será o mais rápido.

Estou feliz que você encontrou DecInt útil.

Answer 3

15,9 ms no meu notebook lento. É a impressão que está retardando para baixo. Convertendo para números binários para decimal é bastante lento, o que é um passo necessário de imprimi-lo. Se você precisar de saída o número que você deve tentar a DecInt ChristopheD já mencionado.

DecInt será mais lento fazendo a multiplicar, mas fazer a impressão muito mais rápido

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

Aqui está um exemplo com uma versão ligeiramente modificada do seu código. Note-se que a conversão de uma string 100000 dígito para uma longa já leva ~ 1seg neste computador

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

Eu sugiro que você começa a Sábio ferramenta matemática, que tem apenas sobre cada ferramenta matemática Python já feito rolou em um pacote. Veja se há um bom rápido arbitrária ferramenta de precisão matemática no sábio que atenda às suas necessidades.