Discussion :

[francortes]

bonsoir à tous !

histoire d'avancer un peu plus dans le développement d'une implémentation de Virtual DOM basée sur un block memory pool et évoquée dans ce post :

https://www.developpez.net/forums/d1...ecanique-vdom/

j'ai décidé de diviser le sujet en un ensemble de petites questions. Ce sera plus facile d'avancer ainsi !

Ici il sera question de générer des clés pseudo aléatoires, et de faire des hachage de chaînes de caractères projetant dans l'espace de ces clés. Trois questions à considérer :

1. Je souhaite créer un Générateur Congruentiel Linéaire (LCG) "full cycle", ou avec la plus grande période possible... qui donne des valeurs comprises entre 0 (inclus) et Math.pow(64, 4) (exclus), quelque chose de la forme : X[N] = (A * X[N - 1] + C) mod M. Comment déterminer les entiers A, C et M facilement ?

2. Comment convertir facilement le nombre produit en une clé lisible (et compatible avec un identifieur JS) de 4 digits sur /A-Za-z0-9_\$/ soit 64 valeurs possibles sur 4 positions ?

3. Seeding : l'utilisateur de la lib enregistrera ses composants et l'ensemble de la vue de l'application avec des chaines de caracteres personnelles, exemple: 'awesome-app', 'awesome-compo-login', etc... comment hasher simplement une chaine arbitraire pour produire une telle de ces clés ?

J(ai bien trouvé ceci, c'est bien expliqué, mais je ne parviens pas à l'adapter à mon cas précis, sans doute mes cours de maths théoriques sont ils trop loin dans le temps... les tests que j'ai mené collisionnent trop vite :

http://www.partow.net/programming/hashfunctions/

Merci d'avance !

[Invité]

hi,

déjà pr 1 tu prends avec pincettes parce que je suis pas une lumière de l'arithmétique
1. sur wiki https://fr.wikipedia.org/wiki/G%C3%A..._lin%C3%A9aire
i disent que pour le standard minimal est C==0, m=2^31-1, a=16807

SI tu imposes 0 à 64^4=2^24 alors (au moins) M==2^24
(vu que modulo M va décrire de 0 à ... M-1)
Sauf que ta valeur est inférieure à celle du standard donc déjà je serais un peu frileux...

Je pense (à tester) que tu peux tenter de 2^24-1, C==0 et déduire A (via "le choix du multiplicateur et de lincrement") mais vu que ca sent mauvais et que _je_ suis feignant, j'aurais tendance à prendre le standard, et ne considérer que les 23 bits de poids fort


2. ben tu fais une division base 64?, tu indexes tes "symboles" de 0 à 63 (genre 0->A, 1->B, ...63->$) (en fait comme tu ferais pour transcrire un nombre décimal en base 2, sauf que là c'est base64)

3. je sais pas faut comparer les pptés des fonctions de hash. #ifoyaka

[francortes]

j'avais commencé par faire cela avec a = 17 et c = 13, m = 2^24... ce n'est pas élégant comme tirage, mais cela a le mérite de pouvoir continer à faire des tests pour les autres parties de cette lib...


Quand je reviendrais sur la partie générateur de l'appli, je considèrerai les nombres que tu proposes. J'ai une petite boucle de tests qui détecte bien les collisions... et relire l'article que tu mets en avant, cela ne fera pas de mal non plus !

merci pour cette réponse qui m'encourage à poursuivre.

Bonne soirée ! F-E

[Invité]

hello,

un peu de nouveau.
en lisant plus précisément le passage

When c≠0, correctly chosen parameters allow a period equal to m, for all seed values. This will occur if and only if:[2]:17—19

m {\displaystyle \,m} \,m and the offset c {\displaystyle \,c} \,c are relatively prime,
a − 1 {\displaystyle \,a-1} \,a-1 is divisible by all prime factors of m {\displaystyle \,m} \,m,
a − 1 {\displaystyle \,a-1} \,a-1 is divisible by 4 if m {\displaystyle \,m} \,m is divisible by 4.

th. hull dobell theorem (lien wiki fr)
on peut choisir trivialement
m = 2^24 (pour 23 bits)
c = 3 (c de fait premier avec m)
a = 2^22+1 (car m=4*2^22) et de fait a-1 divisible par m

le lcg decrit alors la full periode m sans collision
qu'on peut vérifier par

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
 
var n = process.argv.splice(2)[0];
if(!n){
    throw 'expect ./afe 16777216 where 16777216 is the number of numbers to be generated';
}
 
var seed = 3
function Mylcg(seed, bits, [a,c,M]){
    var x_n = seed;
    return {
        next:()=>{
            var y = (a*x_n+c)%M;
            x_n = y;
            return y
        }
    }
}
//https://en.wikipedia.org/wiki/Linear_congruential_generator
var glibc = [1103515245, 12345, Math.pow(2,31)]
var aple = [16807, 0, Math.pow(2,31)-1]
var mine = [Math.pow(2,22)+1, 3, Math.pow(2,24)]
var g = Mylcg(seed, 23, mine);
var num = -1;
for(var i = 0; i<n; ++i){
    if(num == seed){
        console.log('FUCK at', i)
        throw 'failed';
    }
    num = g.next();
    if(i%100000==0){
        console.log('i : ', i)
    }
}
 
console.log('ok')

question annexe pour ma culture:
pourquoi choisis-tu un lcg et pas juste d'incrementer modulo m ?

----
edit:
effectivement a=17 marche egalement puisque a-1=16 multiple de 4. a=5 marche de même..