Quali complessità sono operazioni sui BigInteger di Java 7?

Question

Quali sono i metodi complessità multiply, divide e pow in BigInteger attualmente? Non v'è alcuna menzione della complessità computazionale nella documentazione (né altrove).

Answer 1

Se si guarda il codice per BigInteger (fornito con JDK), mi sembra che multiply(..) ha O (n ^ 2) (in realtà il metodo è multiplyToLen(..)). Il codice per gli altri metodi è un po 'più complesso, ma si può vedere voi stessi.

. Nota: questo è per Java 6. suppongo che non differirà in Java 7

Answer 2

C'è un nuovo "migliore" di classe BigInteger che non viene utilizzato dal JDK sole per conservateism e la mancanza di test di regressione utili (enormi insiemi di dati). Il ragazzo che ha fatto gli algoritmi migliori potrebbe aver discusso la vecchia BigInteger nei commenti.

Qui si va http://futureboy.us/temp/BigInteger.java

Answer 3

misurarla. Fare operazioni con linearmente crescente operandi e disegnare le volte su un diagramma. Non dimenticare di riscaldare la JVM (diverse corse) per ottenere risultati dei benchmark validi.

Se le operazioni sono O lineare (n), O quadratica (n ^ 2), polinomiale o esponenziale dovrebbe essere ovvio.

EDIT: mentre si può dare algoritmi limiti teorici, essi non possono essere tali utili nella pratica. Prima di tutto, la complessità non dà il fattore. Alcuni algoritmi lineari o subquadratic non sono semplicemente utili perché mangiano molto tempo e risorse che non sono adeguati per il problema a disposizione (ad esempio Coppersmith-Winograd moltiplicazione matriciale). Allora la vostra calcolo può avere tutte kludges si può rilevare solo da esperimento. Ci sono preparano algoritmi che non fanno nulla per risolvere il problema, ma per accelerare il vero risolutore (matrice condizionata). Ci sono implementazioni non ottimali. Con lunghezze superiori, la velocità può scendere drasticamente (cache mancante, la memoria in movimento, ecc). Quindi, ai fini pratici, vi consiglio di fare sperimentazione.

La cosa migliore è quello di raddoppiare ogni volta che la lunghezza dell'input e confrontare i tempi. E sì, è do scoprire se un algoritmo ha n ^ 1.5 o n ^ 1.8 complessità. semplicemente quadrupla la lunghezza di input ed è necessario solo la metà il tempo per 1,5 invece di 2. È possibile ottenere ancora una volta quasi la metà del tempo per 1.8 se si moltiplica la lunghezza 256 volte.