Pitone lungo moltiplicazione

Question

Ho bisogno di un algoritmo più veloce rispetto alla normale corrente lungo la moltiplicazione Python.

Ho cercato di trovare un'implementazione decente Karatsuba, ma non ci riesco.

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

Come si vede, si tratta di niente di complicato, a pochi moltiplicazioni. Ma deve gestire i numeri con un massimo di 100000 cifre in meno di 2,5 sec.

Vorrei un po frammento di una funzione o semplicemente un link ad alcune implementazione di una funzione di moltiplicazione più veloce, o qualsiasi cosa che aiuta.

Answer 1

Si potrebbe avere uno sguardo alla realizzazione del DecInt modulo (versione puro Python è disponibili (Toom-Cook), anche se il più veloce sarà probabilmente quando si utilizza gmpy ).

Answer 2

Sono l'autore del DecInt (decimale intero) biblioteca in modo farò un paio di osservazioni.

La biblioteca DecInt è stato specificamente progettato per lavorare con grandi numeri interi che dovevano essere convertiti in formato decimale. Il problema con la conversione in formato decimale è che la maggior parte dei valori librerie memorizzare precisione arbitraria in binario. Questo è il più veloce e più efficace per collocare memoria, ma la conversione da binario a decimale è in genere lento. binario di Python a decimale conversione utilizza un algoritmo di O (n ^ 2) e diventa lento molto rapidamente.

DecInt utilizza una grande radice decimale (di solito 10 ^ 250) e memorizza il numero molto elevato in blocchi di 250 caratteri. Conversione di un numero molto grande di formato decimale ora viene eseguito in O (n).

Naive, o grado di scuola, la moltiplicazione ha un tempo di esecuzione di O (n ^ 2). Pitone utilizza Karatsuba moltiplicazione che è tempo di O (n ^ 1.585) in esecuzione. DecInt utilizza una combinazione di Karatsuba, Toom-Cook, e Nussbaumer convoluzione per ottenere un tempo di esecuzione di O (n * ln (n)).

Anche se DecInt ha molto elevato sovraccarico, la combinazione di O (n * ln (n)) moltiplicazione e O (n) conversione alla fine sarà più veloce di O Python (n ^ 1.585) moltiplicazione e O (n ^ 2) conversione.

Dal momento che la maggior parte dei calcoli non richiedono ogni risultato da visualizzare in formato decimale, quasi ogni libreria di precisione arbitraria utilizza binario dato che rende i calcoli più facile. DecInt rivolge una piccola nicchia. Per i grandi numeri sufficienti, DecInt sarà più veloce per la moltiplicazione e la divisione di Python nativo. Ma se siete dopo la prestazione pura, una libreria come GMPY sarà il più veloce.

Sono contento che hai trovato DecInt utile.

Answer 3

15.9 ms sul mio notebook lento. E 'la stampa che sta rallentando giù. Conversione in numeri binari in decimale è abbastanza lento, che è un passaggio obbligatorio di stamparlo. Se è necessario per emettere il numero che si dovrebbe provare il DecInt ChristopheD menzionato già.

DecInt sarà più lento facendo la si moltiplicano, ma rendere la stampa più veloce

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

Ecco un esempio con una versione leggermente modificata del codice. Si noti che la conversione di una stringa di cifre 100000 per un lungo già prende ~ 1 sec su questo computer

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

Vi suggerisco di ottenere il Sage strumento di matematica , che ha quasi ogni strumento di matematica Python mai fatto laminati in un unico pacchetto. Vedere se c'è un bel strumento arbitrario di precisione matematica veloce nella Sage che soddisfi le vostre esigenze.