Nicola Musatti <object
...@divalsim.it> wrote in message
...
> Hai perfettamente ragione e, una volta visto, e' piuttosto ovvio. Io in
> realta' mi ero fissato (se si puo' chiamare fissazione qualcosa che mi
> impegna per qualche secondo al mese...) sull'idea di generalizzare il
> "crivello di Eratostene" intercalando i cicli sui primi gia' trovati con
> un approccio tipo diagonalizzazione. Non sono del tutto sicuro che si
> riesca, pero'.
Ci si potrebbe anche riuscire (in un modello astratto a memoria
infinita, ma con tempo di esecuzione bounded).
Il concetto-base per inquadrare questo approccio e` quello
di "stream" -- non nel senso C++ ma in quello piu` classico
meravigliosamente illustrato ad esempio nell'Abelson e
Sussman, "Structure and Interpretation of Computer
Programs".
Uno "stream" e` un "flusso" (monodirezionale) di oggetti
che e` in grado di:
-- presentarmi un "oggetto corrente"
-- avanzare al successivo
-- (solo per stream finiti): dirmi se e` finito
Si potrebbe quindi modellare in C++ come:
template <class T>
class astream: {
public:
virtual constT& current() const = 0;
virtual void next() = 0;
virtual bool finished() const = 0;
};
Ogni volta che trovo un numero primo, posso associare
ad esso un astream<int> con l'ulteriore interessante
proprieta` che i valori successivamente ritornati sono
strettamente crescenti:
class nonprimes_stream: public astream<int> {
int multiple;
int currenti;
public:
nonprimes_stream(int prime): multiple(prime) {
currenti = prime+prime;
}
const int& current() const { return currenti; }
void next() { currenti += multiple; }
bool finished() const { return false; }
};
Usero` spesso l'abbreviazione np_s nel seguito
per indicare un nonprimes_stream.
Anche la successione dei "candidati" puo` essere
ben modellata da un astream<int>, che torna uno
dopo l'altro tutti gli interi positivi.
Dato tutto questo, vogliamo un astream<int> che
torni i soli _numeri primi_ -- come?
Alla "next", otterremo un candidato e lo sottoporremo
al "crivello" di tutti i nonprimes_stream sinora generati.
Se il candidato e` _piu` piccolo_ del current di un certo
nonprimes_stream, allora il candidato e` ancora "vivo"
(e il nonprimes_stream non va alterato).
Se il candidato e` _eguale_ al current di un certo np_s,
il candidato e` "morto" (va rifiutato), e il nonprimes_stream
va fatto passare al suo elemento successivo.
Se il candidato e` _maggiore_ del current di un certo
np_s, quel np_s va fatto avanzare sinche` non si
verifica una delle due condizioni precedenti (e va
compiuta l'azione relativa: accettazione o rifiuto, e
ulteriore avanzamento o meno del np_s).
Ogni candidato va passato al vaglio di tutti i np_s
sinche`: (a) sono stati tutti usati e nessuno ha
rifiutato il candidato o (b) uno qualsiasi rifiuta il
candidato (e` interessante dimostrare che nel caso
b non siamo tenuti a completare il ciclo!).
Nel caso (a), accettiamo il candidato, lo poniamo
come current dell'astream<int> dei numeri primi,
e aggiungiamo il np_s su di lui costruito alla bag
dei np_s che stiamo usando.
Nel caso (b), passiamo al candidato successivo e
ripetiamo il ciclo.
La dimostrazione di correttezza e` interessante (e
si fa molto piu` agevolmente usando notazione piu`
astratta per gli stream).
Ancora piu` interessante e` dimostrare in che senso
questo E` in effetti una generalizzazione del crivello
di Eratostene: un c.d.E-sino-a-N per un certo N
finito si potrebbe indifferentemente implementare
con questo algoritmo _O_ pompando sino alla fine
ciascun np_s appena generato (e ricordando i
risultati in un vettore di bit...); la sequenza di operazioni
richieste ad ogni dato np_s *non cambia* (cambia
solo lo "interleaving" delle operazioni su np_s
disgiunti!).
La differenza e` che con questo ordinamento delle
operazioni non c'e` necessita` di pre-specificare N,
per cui (se avessimo infinita memoria per tenere
tutti i np_s nella nostra bag, e i nostri int fossero
ovviamente a illimitate cifre) avremmo effettivamente
soddisfatto le specifiche (stream infinito dei primi).
Da un punto di vista di correttezza (e di prestazioni
nel senso suddetto) l'ordine dei test di un candidato
rispetto ai vari np_s e` arbitrario (una "grab-bag"
e` la "struttura-dati" adeguata per tenere i np_s).
E` facile dimostrare che nessun np_s puo` essere
omesso (in quanto l'np_s centrato sul numero
primo N e` l'unico in grado di "eliminare" i vari
candidati della forma N**x per x>1... le potenze
del numero primo N).
Alex
|
