- Messaggi
- 24,532
- Reazioni
- 12,379
- Punteggio
- 254
eh sì, le ottimizzazioni sul linguaggio le lascio a te, il C++ non lo conosco per cui il codice è arrangiato in base alle scarne info che ho, preferisco concentrarmi sull'algoritmo. Abbiamo postato quasi in contemporanea, credo a distanza di un paio di secondi, non avevo letto il tuo ultimo post e mi riferivo al precedenteIn realtà il bitset va bene. L'espansione riguarda i nuoviN
valori da sottoporre al crivello, doveN
è una costante.
...
Come detto nel precedente post,
Vero! e all'inizio è così che avevo fatto ed è andato tutto bene fino ad una certa dimensione, poi perde una manciata di primi : ho fatto un po' di controlli con Mathematica online (https://www.wolframalpha.com/input/?i=calculator) e quando iniziavo con i=p^2 su intervalli grandi (a memoria con estremo superiore >16 milioni) perde per strada 4 numeri primi, segno che è "scappato" qualcosa, probabilmente ho fatto un errore di codifica che non vedo solo io, magari ci riprovo perché con i=p^2 tagliavo un bel po' di marcature inutili.Però non tieni conto del fatto che, considerando per esempioi=13
, è inutile partire 13*3, perché 13*3, 13*5, 13*7, 13*9 e 13*11 sono già stati cancellati in precedenza. Quindi tanto vale partire dai^2
.
Per la cronaca, con Mahtematica il controllo sulla quantità di numeri primi la fai mettendo come input PrimePi[n]
la cosa mi ha infastidito parecchio e se ho tempo vorrei capire dove diavolo sta l'intoppo che mi ha portato a perdere primi iniziando a setacciare dal quadrati del primo in analisi
deformazione mentale:, quando sono in gioco numeri grandi non lo faccio mai:Inoltre a questo punto quello che tu chiamilimiteCrivello
diventa inutile, in quanto la condizione per terminare direttamente il ciclo più esterno diventai*i>dim-1
(i nomi delle variabili si riferiscono al codice da te postato).
in questo caso porta inefficienza perché la moltiplicazione i*i del ciclo potrebbe essere eseguita (decine di) migliaia/milioni di volte --> conviene usare la funzione di libreria radice quadrata che esegue al più qualche centinaio di istruzioni una sola volta (bisogna usare un funzione che abbia una precisione in cifre maggiore degli interi in gioco);
in generale i*i>n può portare errori runtime/overflow quando i si avvicina al massimo intero rappresentabile, per es. se usi un (u)int a 32 bit hai un limite massimo di (4)2 milardi e spiccioli: eleva al quadrato un numero "piccolo" come 100 000 e vai fuori range!
In questo caso particolare non succederebbe per la dimensione relativamente piccola del bitset che volevo usare, però in generale può succedere.
Ho un sacco di problemi di connessione, non so se potrò ricollegarmi più tardi