Implémentation algo: générateur pseudo aléatoire MWC
Bonjour à tous !
Pour une application de sérialisation de structures de données graphes
j'ai besoin de générer des clés pseudo-aléatoires sur 4, 6 ou 8 digitss avec 52 positions (A_Za_z)
donc de la forme 'Cafe', 'pizzas' ou 'AptiTude'.
J'ai décidé d'utiliser des générateurs de nombres pseudo-aléatoires
car cela devrait me permettre de reproduire les résultats de cette expérience lors des phases de test (même caractéristiques et même graine => même séquence de clés)
et ai tenté d'adapter les générateurs MWC (Multply-With-Carry) en JS selon mes besoins.
Le hic est que ma version bouble sur des périodes très courtes (~10k valeurs) là où,
pour 4 digits Math.pow(52, 4) permttrait d'obtenir un cycle se comptant en millions...
Pour ce qui est du code du générateur c'est à peu à cela : une version custom de l'algorithme de wikipedia... n'ayant pas complètement compris l'implémentation proposée en C++,
j'ai repris ce document au niveau des équations théoriques, ce qui donne :
Pour ce qui est du code de test il est assez simple : il est basé sur des statistiques de base sur des tirs (shots) du générateur, avec en paramètre un modulus (a) et une graine, avec stockage des couples {valeurr: rang-dans-la-série} dans un opbjet hash, avec détection et arrêt à la premère collision :
Code : Sélectionner tout - Visualiser dans une fenêtre à part
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67// a = modulus (safe prime en principe) // b = 52 (base) // r = 3 (lag = décalage) interprété ici comme nombre de digits à produire moins 1 export const createMWC = (a, b, r) => { // le tableau de travail // xi = valuers // ci = retenues (carries) const xi = new Array(r + 1) const ci = new Array (r + 1) // les indices pour extraire X[n - r] et X[n - 1] // vu qu'on ne fait pas "ramper" le tableau enconsommant les valeurs de tête // et en poussant les nouvelles en fin de tableau ! let n0 = 0 let nr = r // variables temporaires let xn = 0 let cn = 0 // API JS exposée return { // la fonction d'initalisation init (seeds) { for (let k = 0; k < (r + 1); k++) { xi[k] = seeds[k] ci[k] = 0 } }, // génération de valeurs next() { let result = new Array (r + 1) // on décale à chaque appel à la fonction n0 = (n0 + 1) % (r + 1) nr = (nr + 1) % (r + 1) // from wikipedia... xn = (a * xi[nr] + ci[n0]) % b cn = Math.floor((a * xi[nr] + ci[n0]) / b) // écrase l'ancienne valeuret place la nouvelle à la place xi[n0] = xn ci[n0] = cn // ultime twist... /* result = (n0 === 0) ? xi.slice(0) : xi.slice(n0).concat(xi.slice(0, n0)) */ // ou plus simple for(let t = 0; t < r + 1; t++) { //result[t] = xi[t] result[(t + n0) % (r + 1)] = xi[t] } return result } } }
Enfin c'est assez baqieu mais pour l'instant cela ne me permet pas de comprendre
Code : Sélectionner tout - Visualiser dans une fenêtre à part
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44const MAX_LOOPS = 10000000 const b = 52 const r = 3 const output = (arr) => { // console.log(arr) //return arr.reduce((acc, val) => b * acc + val, 0) return arr.join(':') } const shoot = (a, seeds) => { const store = {} const generator = createMWC(a, b, r) let i = 0 let result = 0 let text = seeds.join(':') let crashes = 0 generator.init(seeds) store[output(seeds)] = 0 while (i++ < MAX_LOOPS) { const generated = generator.next() const val = output(generated) text += ' ' + generated.join(':') if(store.hasOwnProperty(val)) { result = i crashes++ // console.log('#### %s', i) break } else { store[val] = i } // console.log('store[%s]: %s', val, store[val]) // console.log(' %s', generated.join(':')) } console.log('crashes: %s', crashes) return result }
les basses performances de l'algorithme, d'autant plus qu'une version boguée précédente, et un autre avec tableau "rampant",
très coûteuse en termes d'allocation mémoire (push+unshift) donnaient de meilleurs résultats.
Vu que je ne trouve pas de solution évidente par moi même j'en appelle à vos lumières
pour tenter de trouver une solution. Quelqu'un aurait il une idée ?
Répondre avec citation
Envoyé par francortes
Partager