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 :

Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
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
        }
      }
    }
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
1
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
 
    const 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
    }
Enfin c'est assez baqieu mais pour l'instant cela ne me permet pas de comprendre
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 ?