Newsgroup: it.comp.lang.c
Titolo: Calcolo lunghezza sequenze

Ho scritto un programma (in C) che riceve in ingresso un numero usato 
per generare una sequenza di numeri tramite semplici operazioni (come un 
generatore di numeri pseudo-casuali).
 
Tutte le sequenze generate sono formate da una parte aperiodica iniziale 
e da una parte periodica, come questa sequenza d'esempio:
	24 8 7 21 16 11 9 21 16 11 9 21 16 ...
in cui si notano 3 numeri iniziali che non usciranno più e 4 numeri che 
si ripeteranno sempre.
 
Assegnando opportuni parametri all'algoritmo, le sequenze possono essere 
estremamente lunghe. A me interessa trovare un metodo per determinare la 
lunghezza delle due sequenze che potrebbero arrivare (per i parametri 
che uso) fino a qualche decina di milioni di numeri.
 
Non avendo idea, a priori, della lunghezza che potrei ottenere, il 
metodo che uso attualmente consiste nel memorizzare un certo numero di 
numeri e andare a ritroso fino a trovare l'ultimo numero uscito.
La richiesta di memoria, però, è molto alta e con 4 GB di RAM arrivo 
intorno ai 70 milioni di numeri.
 
Potrei anche evitare di memorizzare i numeri e calcolare tutte le volte 
la sequenza fino a che non trovo una ripetizione, ma il tempo 
d'esecuzione sarebbe proibitivo.
 
Vi viene in mente un metodo migliore?
 
Grazie
Cristiano

 Cristiano
 
 
Ciao,
Roberto.
 
 
-- 
 
questo articolo e` stato inviato via web dal servizio gratuito 
http://www.newsland.it/news
 segnala gli abusi ad 
ab...@newsland.it
 
 
 

 darlo per scontato.
 
 
Dandolo invece per buono, se sai in che intervallo sono generati i numeri,
ad esempio se la funzione restituisce un unsigned long int e magari sul
tuo sistema e' di 32 bits, sai che i numeri da memorizzare sono MAX
2pow32.
 
Puoi allocare un grande array di 2pow 32 word di 32 bits (16 Giga RAM),
inizializzarlo tutto a 0 e usare i valori generati come indice per:
1) controllare se la posizione e' ancora 0.
2) se a 0 la setto al Numero-di-Passo-attuale-partendo-da-1 altrimenti
mi fermo perche' l' indice che sto usando e' ripetuto e generera' una
sequenza periodica.
 
Questo approccio ha in vantaggio di essere partizionabile, cioe' se non
disponi di una macchina da 16 Giga RAM puoi metterne in LAN 5 o piu'
e incaricarle di gestire intervalli di indici diversi, cosi' che se la
macchina generatrice non gestisce la porzione di array con indice generato
compie una RPC verso la macchina che gestisce quel range.
 
Come hai visto, i valori dell' array verranno settati a
Numero-di-Passo-attuale-partendo-da-1
perche 0 e' in valore Posizione-Mai-Vistitata. Questo ci da il servizio
immediato di dividere la parte aperiodica da quella periodica. Se avessimo
settato solo a 1 saremmo rimasti con il  problema.


 Vi viene in mente un metodo migliore?
 
io sincermanete non ho capito ne quello che hai ne quello che vuoi.
 
Ciao Jack
-- 
Yoda of Borg am I! Assimilated shall you be! Futile resistance is, hmm?

 darlo per scontato.
 
Saltando i criteri per la scelta dei parametri, l'algoritmo è molto 
semplice:
 
1) scegliere 2 numeri interi e e n
2) scegliere x, un seme da r bit
3) y = x^e (mod n)
4) x = gli r bit più significativi di y
5) torna a 3.
 
Si tratta del generatore Micali-Schnorr (usato in crittografia).
 
A me interessa conoscere principalmente la lunghezza di quella che ho 
chiamato "parte aperiodica iniziale".
 
Dalle prove fatte, sembra che nessun numero appartenente alla SAI 
(sequenza aperiodica iniziale) sia presente all'interno della sequenza 
periodica. Il problema è che devo capire dove comincia la sequenza 
periodica.
 
Ciao e grazie
Cristiano

 settato solo a 1 saremmo rimasti con il  problema.
 
Non credo che sia fattibile, anche perché posso contare solo su 1 PC e 1 
portatile (6 giga in tutto) e, in teoria, può uscire qualunque numero 
tra 0 e n-1. Con n da 74 bit, la cosa è inattuabile.
 
Ciao
Cristiano

 Si tratta del generatore Micali-Schnorr (usato in crittografia).
 
Dimenticavo... Se interessa, qui c'è una buona descrizione:
http://www.cacr.math.uwaterloo.ca/hac/
 
capitolo 5, algoritmo 5.37.
 
Cristiano

 Cristiano
 
 
Cambio discorso, visto che non ti so' aiutare e divago: ma la proprieta'
che ti fa scegliere tale generatore e' proprio la lunghezza della parte
aperiodica? Hai bisogno di numeri non ripetuti? Puoi considerare un cambio
di tecnologia, che so'... un cifrario in modalita' CRT (Counter, cioe' che
cripta un contatore che incrementa solamente) per avere numeri unici?


 cripta un contatore che incrementa solamente) per avere numeri unici?
 
Non posso risponderti come vorrei perché sarei paurosamente OT (molto 
più di adesso); posso però brevemente dirti che ha senso usare un 
generatore come questo (ovviamente solo in ambito crittografico) perché 
è molto più veloce di tutti quelli dello stesso tipo (potendo prendere 
molti bit per l'uscita) ed è l'unico ad essere incraccabile a patto che 
sia vera una cosa che è facilmente verificabile (e che risulta vera). 
Non so quanto possa essere comprensibile ciò che ho detto, ma significa 
che questo generatore è l'unico ad essere sicuro anche se uso per 
l'uscita un gran numero di bit di x^e (mod n).
Tutti gli altri generatori (come il CRT) non hanno una base matematica 
che ne attesti la "robustezza", seppure sulla base di un'ipotesi non 
dimostrata (come l'intrattabilità della fattorizzazione di n).
 
Ciao e grazie per la collaborazione :-)
Cristiano