domande su un particolare algoritmo

1. Suppongo che tu abbia ragione, l'autore vuole ottenere una maggiore flessibilità.
2. È piuttosto una questione di gusti. Se sei abituato a un po 'di aritmetica, il & anche la forma è leggibile. L'uso di 0x1 indica questo. L'autore avrebbe potuto usare 0b1 o 01 o 1. Ma se si confondono spesso i bit, alla fine si inizia a utilizzare hex in quanto basato su 2. BTW, non pensare che si tratti di un'ottimizzazione. Le operazioni con costanti sono molto facili da ottimizzare e i compilatori lo faranno. Per esempio. (n * 32) sarà tradotto in (n < < 5).

3. Devi solo controllare tutti i numeri che sono inferiori o uguali alla radice del numero candidato. Ma l'algoritmo controlla solo i numeri del modulo 6k - 1 e 6k + 1. Almeno questo è quello che l'autore dice nel commento. Ma il k dal commento non è il lungo k dal codice. Invece il k lungo assume valori del modulo 6 * i. Sulla base di ciò vengono calcolati i possibili fattori primi. Ora se 6i - 1 è un fattore primo, devi assicurarti che k arriva fino a (incluso) 6i. Ad esempio, supponiamo che il tuo (lungo) Math.sqrt (n) possa essere scritto come 6 * i - 1. Ma è calcolato come k-1, quindi k deve eseguire fino a 6i, che è < em> (long) Math.sqrt (n) + 1 .

   Un'alternativa senza +1 è quindi:

   public static boolean isP2(long n) { 
       if (n==2 || n==3 || n==5) return true;
       if ((n&0x1)==0 || n%3==0 || n<2 || n%5==0) return false; 
       long root=(long)Math.sqrt(n);
       // we check just numbers of the form 6*i+1 and 6*i-1 
       for (long k=6;k<=root;k+=6) { 
           if (n%(k+5)==0) return false; 
           if (n%(k+1)==0) return false; 
       } 
       return true; 
   }
   

4. La complessità è O (sqrt (n)), che è in realtà la stessa di O (sqrt (n) / 6). Ma dato che 6 è una costante, possiamo ignorarla in Big-O-Notation. Lo stesso vale per O (sqrt (n / 6)), è solo più difficile da vedere. Il motivo è

   sqrt (n / 6) = (n / 6) ^ 0.5 = n ^ 0.5 / 6 ^ 0.5

   E 6 ^ 0.5 è solo un'altra costante. Comunque O (n) è decisamente sbagliato.

1. Sì, non c'è altra ragione per cui possa capire il motivo per cui avrebbero scelto long over int.

2. È lo stesso, ma è uno degli sviluppatori di cose intelligenti (specialmente con uno sfondo C incorporato) per eliminare alcuni cicli della CPU tra l'applicazione di una maschera su un lungo e applicando modulo. Probabilmente lo sviluppatore pensava che il bytecode jitted che andava verso la CPU avrebbe portato il trucco, rendendo così il suo algoritmo 0,000 ... 00005% più veloce (si noti che il trucco non è nemmeno nel loop) a scapito del fatto che le persone continuano a farlo sempre .

3. Sia la leggibilità, sia lo sviluppatore hanno pensato che dal momento che + viene valutato da destra a sinistra, forzando la costante più a destra ad essere lunga (1L) - dato che il risultato è lungo - potrebbe essere più veloce. Il bytecode generato spinge probabilmente 1 nello stack (fino a 1L o int con 1), valuta sqrt, pop-cast-push lo sqrt, quindi esegue un ladd (aggiunta lunga). È improbabile che vi sia un reale guadagno, specialmente dal momento che, ancora una volta, non si è nel ciclo, e poiché di solito il jitter è intelligente.

4. La complessità big-O è O (sqrt (n)) o O (n ^ (1/2)) - una costante moltiplicativa su n è irrilevante in teoria. Dire che O (n) non è sbagliato (big-O è un limite superiore), ma non è nemmeno molto utile, perché O (sqrt (n)) è uno stimatore molto migliore (si tenta di stimare il limite superiore come vicino al tempo di esecuzione il più possibile, a una costante).

modifica: dire che O (n) è davvero sbagliato, data la definizione di big-O .

Potrebbe essere semplicemente che il set di numeri primi che puoi inserire in un numero intero è molto più piccolo del set di numeri primi che puoi inserire in un lungo.

Non c'è molto valore nell'ottimizzare il set di numeri primi che si adattano a un numero intero, mentre vale la pena farlo per il set che si inserirà in un lungo.