durante le ultime prove ho pure scoperto di non potermi fidare più del compilatore GCC che uso, eppure è il 13.2.0 , non è l'ultima (sub)versione ma pensavo andasse bene, invece su input >16,2 milioni il .exe compilato esce con un errore incomprensibile e lo fa apparentemente a caso (me ne sono accorto variando l'intervallo del bitset)
Hai provato a dichiarare il bitset
static (o equivalentemente come variabile globale) come ti ho suggerito in precedenza?
Intanto ho aggiornato il programma apportando alcune correzioni e modifiche:
C++:
#include <iostream>
#include <bitset>
#include <cstdint>
#include <vector>
using namespace std;
void espandi_e_applica_crivello(vector<uint32_t> &v, uint32_t &last)
{
static const uint32_t N = 51'130'563;
static bitset<N + 1> b;
uint32_t first = last + 2;
uint64_t n, q;
uint32_t dim = N + (v.size() == 1);
last += 2 * dim;
if(v.size() == 1)
{
for(uint32_t i = 0; ; ++i)
{
if(!b[i])
{
n = 2 * i + first;
if((q = n * n) > last)
{
break;
}
for(uint32_t j = (q - first) / 2; j < dim; b.set(j), j += n);
}
}
}
else
{
b.reset();
for(uint32_t i = 1, j; (q = (n = v[i]) * v[i]) <= last ; ++i)
{
if(q < first)
{
uint32_t r = first % n;
j = r ? (r % 2 ? (n - r) / 2 : n - r / 2) : 0;
}
else
{
j = (q - first) / 2;
}
for(; j < dim; b.set(j), j += n);
}
}
for(uint32_t i = 0; i < dim; ++i)
{
if(!b[i])
{
v.push_back(2 * i + first);
}
}
}
uint32_t next_prime_number(const uint32_t n)
{
if(n < 2)
{
return 2;
}
static vector<uint32_t> v = {2};
static uint32_t last = 1;
while(n >= v.back() && last != UINT32_MAX)
{
espandi_e_applica_crivello(v, last);
}
cout << "\n " << v.size() << " NUMERI PRIMI <= " << last << " (" << (double)v.size() / last * 100 << "%)\n";
if(n >= v.back())
{
return 0;
}
uint32_t i_dx = v.size() - 1;
for(uint32_t i_sx = 0, i; i_dx != i_sx + 1; (n < v[i = (i_sx + i_dx) / 2] ? i_dx : i_sx) = i);
return v[i_dx];
}
int main()
{
uint32_t n = 318'912'486;
uint32_t p = next_prime_number(n);
cout << "\n NEXT PRIME(" << n << ") = " << p << endl;
}
- giusto per ricapitolare, il programma implementa la funzione
next_prime_number(n) sfruttando un crivello di Eratostene espandibile. Il risultato viene ricercato nell'ambito dei 32 bit, e se non esiste, la funzione ritorna
0 (come nel caso di
next_prime_number(UINT32_MAX) );
- per la precisione i numeri primi trovati ad ogni espansione del crivello vengono salvati in un vettore
v e la funzione
espandi_e_applica_crivello() viene richiamata finché
n risulta maggiore o uguale all'ultimo elemento del suddetto vettore (e ovviamente fino a quando l'ultimo valore vagliato
last risulta inferiore a
UINT32_MAX , che come sappiamo è pari a 2^32-1) ;
- la risposta viene ricercata all'interno di
v mediante una ricerca binaria (o almeno credo che si chiami così, l'algoritmo l'ho scritto ragionando sul momento);
- se il crivello viene applicato almeno una volta, oltre alla risposta il programma stampa anche una statistica circa il numero di primi minori o uguali al massimo valore vagliato;
- infine penso sia doveroso spiegare perché ho fissato
N = 51.130.563 e la dimensione del bitset a
N+1 
! Al fine di coprire tutti gli interi a 32 bit è essenziale che l'ultimo valore vagliato dall'ultima chiamata a
espandi_e_applica_crivello() sia proprio uguale a
UINT32_MAX . I valori da vagliare sono i numeri dispari che potenzialmente vanno da 3 a 2^32-1, per un totale quindi di ((2^32-1)-1)/2=2.147.483.647 valori. Il problema è che il suddetto valore è un numero primo, e quindi non può essere scomposto in parti uguali. Quindi ho preso in considerazione il valore precedente 2147483646=2×3^2×7×11×31×151×331 e ho fissato
N combinando i precedenti fattori al fine di ottenere un valore prossimo ai 50 milioni (che era il valore a cui avevo settato
N nella precedente versione del programma), e per la precisione ho impostato N=3×11×31×151×331=51.130.563 (restano fuori i fattori 2×3×7=42). A questo punto considerando che
2.147.483.647=42×51.130.563+1=51.130.564+41×51.130.563
ho settato la dimensione del bitset a 51.130.564, andando poi nella prima espansione a considerare tutti i 51.130.564 elementi, mentre nelle potenziali 41 espansioni successive alla prima vado a considerare solo i primi 51.130.563 elementi del bitset.
Ovviamente se riscontrate qualche errore fatemi sapere.
invece di rispariare RAM la sprecavo!
