Pagina 2 di 2
Inviato: 01 gen 1970, 01:33
da Antimateria
Publio, log<sup>12</sup>x è sublineare! Tant\'è che quando il numero da testare ha più di 20 cifre, l\'algoritmo comincia a diventare MOLTO più efficiente di uno in tempo lineare!!
Inviato: 01 gen 1970, 01:33
da pazqo
ma la dimostrazione della primalità di 2^20996011-1 usa questo fatto?
<BR>come è stata fatta?
Inviato: 01 gen 1970, 01:33
da publiosulpicio
No, usa un altro algoritmo, su
www.marsenne.org trovi tutti i dettagli.
<BR>Ma come sublineare? Io sapevo che se l\'algoritmo andasse come , ad esempio, n sarebbbe esponenziale, per una storia che la complessità è legata al numero di bit con cui si rappresente l\'imput, che è circa logaritmico... e quindi quando si parla di tempo lineare si parla di tempi che crescono come logn (e potenze varie), non come n... almeno così ho sentito dire... va bhè, mi informerò