et je ne vois pas de forte raison à cela, on pourrait permuter
chaque élément avec n'importe quel autre (et non pas avec un des
éléments précédents).
Pour avoir une distribution aléatoire. Si à chaque fois tu
échanges un élément avec n'importe quel autre, tu vas avoir n^n
différents mélanges. Or, il y a exactement n! ordres possible.
Au moins que n! est facteur de n^n (ce qui n'est pas possible),
il y aurait certains ordres qui ressortent plus que d'autres.
On peut appliquer le même raisonnement à rand() % n; qui ne retourne un
nombre (pseudo-)aléatoire entre [0, n[, que si (RAND_MAX + 1) est un
multiple de n. Dans le cas extrème ou n vaut RAND_MAX, 0 a deux fois
plus de chance d'être tiré qu'un nombre parmi 1 à RAND_MAX - 1.
et je ne vois pas de forte raison à cela, on pourrait permuter
chaque élément avec n'importe quel autre (et non pas avec un des
éléments précédents).
Pour avoir une distribution aléatoire. Si à chaque fois tu
échanges un élément avec n'importe quel autre, tu vas avoir n^n
différents mélanges. Or, il y a exactement n! ordres possible.
Au moins que n! est facteur de n^n (ce qui n'est pas possible),
il y aurait certains ordres qui ressortent plus que d'autres.
On peut appliquer le même raisonnement à rand() % n; qui ne retourne un
nombre (pseudo-)aléatoire entre [0, n[, que si (RAND_MAX + 1) est un
multiple de n. Dans le cas extrème ou n vaut RAND_MAX, 0 a deux fois
plus de chance d'être tiré qu'un nombre parmi 1 à RAND_MAX - 1.
et je ne vois pas de forte raison à cela, on pourrait permuter
chaque élément avec n'importe quel autre (et non pas avec un des
éléments précédents).
Pour avoir une distribution aléatoire. Si à chaque fois tu
échanges un élément avec n'importe quel autre, tu vas avoir n^n
différents mélanges. Or, il y a exactement n! ordres possible.
Au moins que n! est facteur de n^n (ce qui n'est pas possible),
il y aurait certains ordres qui ressortent plus que d'autres.
On peut appliquer le même raisonnement à rand() % n; qui ne retourne un
nombre (pseudo-)aléatoire entre [0, n[, que si (RAND_MAX + 1) est un
multiple de n. Dans le cas extrème ou n vaut RAND_MAX, 0 a deux fois
plus de chance d'être tiré qu'un nombre parmi 1 à RAND_MAX - 1.
random_shuffle(myvector.begin(), myvector.end(),
pointer_to_unary_function<int, int>(myrandom));
Pourquoi ?
Il s'en suit que l'idiome plus ou moins classique serait :
struct MyRandom {
ptrdiff_t operator()( ptrdiff_t i ){
return rand() % i ;
}
};
random_shuffle( v.begin(), v.end(), MyRandom() );
Sinon, on s'en passerait du typedef en général. Même avec la
fonction,
random_shuffle( v.begin(), v.end(), myRandom ) ;
suffit largement, et est plus idiomatique.
C'est probablement lié à l'histoire.
[...] Est-ce que le contrat a toujours été tel ?
Une dernière remarque : rand() n'est pas un bon choix ici comme
fonction de génération aléatoire.
Selon la norme, rand() renvoie une valeur entre 0 et RAND_MAX,
et RAND_MAX n'est pas forcément supérieur à 32767.
Alors, pour peut que le tableau devient un peu grand...
random_shuffle(myvector.begin(), myvector.end(),
pointer_to_unary_function<int, int>(myrandom));
Pourquoi ?
Il s'en suit que l'idiome plus ou moins classique serait :
struct MyRandom {
ptrdiff_t operator()( ptrdiff_t i ){
return rand() % i ;
}
};
random_shuffle( v.begin(), v.end(), MyRandom() );
Sinon, on s'en passerait du typedef en général. Même avec la
fonction,
random_shuffle( v.begin(), v.end(), myRandom ) ;
suffit largement, et est plus idiomatique.
C'est probablement lié à l'histoire.
[...] Est-ce que le contrat a toujours été tel ?
Une dernière remarque : rand() n'est pas un bon choix ici comme
fonction de génération aléatoire.
Selon la norme, rand() renvoie une valeur entre 0 et RAND_MAX,
et RAND_MAX n'est pas forcément supérieur à 32767.
Alors, pour peut que le tableau devient un peu grand...
random_shuffle(myvector.begin(), myvector.end(),
pointer_to_unary_function<int, int>(myrandom));
Pourquoi ?
Il s'en suit que l'idiome plus ou moins classique serait :
struct MyRandom {
ptrdiff_t operator()( ptrdiff_t i ){
return rand() % i ;
}
};
random_shuffle( v.begin(), v.end(), MyRandom() );
Sinon, on s'en passerait du typedef en général. Même avec la
fonction,
random_shuffle( v.begin(), v.end(), myRandom ) ;
suffit largement, et est plus idiomatique.
C'est probablement lié à l'histoire.
[...] Est-ce que le contrat a toujours été tel ?
Une dernière remarque : rand() n'est pas un bon choix ici comme
fonction de génération aléatoire.
Selon la norme, rand() renvoie une valeur entre 0 et RAND_MAX,
et RAND_MAX n'est pas forcément supérieur à 32767.
Alors, pour peut que le tableau devient un peu grand...
James Kanze a écrit :
> Sinon, on s'en passerait du typedef en général. Même avec la
> fonction,
> random_shuffle( v.begin(), v.end(), myRandom ) ;
> suffit largement, et est plus idiomatique.
oui, la lecture initiale du proto de random_shuffle m'a
"troublé" et ma première écriture ne compilait pas avec "cela"
(avec quelque chose qui avait cette intention mais où j'avais
plus sûrement tapé une ânerie).
> C'est probablement lié à l'histoire.
> [...] Est-ce que le contrat a toujours été tel ?
certes.
> Selon la norme, rand() renvoie une valeur entre 0 et RAND_MAX,
> et RAND_MAX n'est pas forcément supérieur à 32767.
oui, surprenant de ne pas trouver de fonction travaillant sur
LONG_MAX (sur 31 bits) et LLONG_MAX (63 bits), j'ai mal lu ou
cela n'existe pas ?
> Alors, pour peut que le tableau devient un peu grand...
un vector est compatible avec des indexes 64 bits ?
(dans vector, ce n'est pas l'argument que je ne trouve pas
mais les types internes, dont la définition de
difference_type).
James Kanze a écrit :
> Sinon, on s'en passerait du typedef en général. Même avec la
> fonction,
> random_shuffle( v.begin(), v.end(), myRandom ) ;
> suffit largement, et est plus idiomatique.
oui, la lecture initiale du proto de random_shuffle m'a
"troublé" et ma première écriture ne compilait pas avec "cela"
(avec quelque chose qui avait cette intention mais où j'avais
plus sûrement tapé une ânerie).
> C'est probablement lié à l'histoire.
> [...] Est-ce que le contrat a toujours été tel ?
certes.
> Selon la norme, rand() renvoie une valeur entre 0 et RAND_MAX,
> et RAND_MAX n'est pas forcément supérieur à 32767.
oui, surprenant de ne pas trouver de fonction travaillant sur
LONG_MAX (sur 31 bits) et LLONG_MAX (63 bits), j'ai mal lu ou
cela n'existe pas ?
> Alors, pour peut que le tableau devient un peu grand...
un vector est compatible avec des indexes 64 bits ?
(dans vector, ce n'est pas l'argument que je ne trouve pas
mais les types internes, dont la définition de
difference_type).
James Kanze a écrit :
> Sinon, on s'en passerait du typedef en général. Même avec la
> fonction,
> random_shuffle( v.begin(), v.end(), myRandom ) ;
> suffit largement, et est plus idiomatique.
oui, la lecture initiale du proto de random_shuffle m'a
"troublé" et ma première écriture ne compilait pas avec "cela"
(avec quelque chose qui avait cette intention mais où j'avais
plus sûrement tapé une ânerie).
> C'est probablement lié à l'histoire.
> [...] Est-ce que le contrat a toujours été tel ?
certes.
> Selon la norme, rand() renvoie une valeur entre 0 et RAND_MAX,
> et RAND_MAX n'est pas forcément supérieur à 32767.
oui, surprenant de ne pas trouver de fonction travaillant sur
LONG_MAX (sur 31 bits) et LLONG_MAX (63 bits), j'ai mal lu ou
cela n'existe pas ?
> Alors, pour peut que le tableau devient un peu grand...
un vector est compatible avec des indexes 64 bits ?
(dans vector, ce n'est pas l'argument que je ne trouve pas
mais les types internes, dont la définition de
difference_type).
James Kanze a écrit :
>> 2 remarques:
>> - ce n'est pas la taille du vector qui est transmis à myrandom mais
>> l'indice courant; ainsi lors du parcours des éléments du vector,
>> l'élement i est échangé avec un des éléments de rang 0 à i (non N)
>> -- et je ne vois pas de forte raison à cela, on pourrait permuter
>> chaque élément avec n'importe quel autre (et non pas avec un des
>> éléments précédents).
> Pour avoir une distribution aléatoire. Si à chaque fois tu
> échanges un élément avec n'importe quel autre, tu vas avoir n^n
> différents mélanges. Or, il y a exactement n! ordres possible.
> Au moins que n! est facteur de n^n (ce qui n'est pas possible),
> il y aurait certains ordres qui ressortent plus que d'autres.
On peut appliquer le même raisonnement à rand() % n; qui ne
retourne un nombre (pseudo-)aléatoire entre [0, n[, que si
(RAND_MAX + 1) est un multiple de n. Dans le cas extrème ou n
vaut RAND_MAX, 0 a deux fois plus de chance d'être tiré qu'un
nombre parmi 1 à RAND_MAX - 1.
James Kanze a écrit :
>> 2 remarques:
>> - ce n'est pas la taille du vector qui est transmis à myrandom mais
>> l'indice courant; ainsi lors du parcours des éléments du vector,
>> l'élement i est échangé avec un des éléments de rang 0 à i (non N)
>> -- et je ne vois pas de forte raison à cela, on pourrait permuter
>> chaque élément avec n'importe quel autre (et non pas avec un des
>> éléments précédents).
> Pour avoir une distribution aléatoire. Si à chaque fois tu
> échanges un élément avec n'importe quel autre, tu vas avoir n^n
> différents mélanges. Or, il y a exactement n! ordres possible.
> Au moins que n! est facteur de n^n (ce qui n'est pas possible),
> il y aurait certains ordres qui ressortent plus que d'autres.
On peut appliquer le même raisonnement à rand() % n; qui ne
retourne un nombre (pseudo-)aléatoire entre [0, n[, que si
(RAND_MAX + 1) est un multiple de n. Dans le cas extrème ou n
vaut RAND_MAX, 0 a deux fois plus de chance d'être tiré qu'un
nombre parmi 1 à RAND_MAX - 1.
James Kanze a écrit :
>> 2 remarques:
>> - ce n'est pas la taille du vector qui est transmis à myrandom mais
>> l'indice courant; ainsi lors du parcours des éléments du vector,
>> l'élement i est échangé avec un des éléments de rang 0 à i (non N)
>> -- et je ne vois pas de forte raison à cela, on pourrait permuter
>> chaque élément avec n'importe quel autre (et non pas avec un des
>> éléments précédents).
> Pour avoir une distribution aléatoire. Si à chaque fois tu
> échanges un élément avec n'importe quel autre, tu vas avoir n^n
> différents mélanges. Or, il y a exactement n! ordres possible.
> Au moins que n! est facteur de n^n (ce qui n'est pas possible),
> il y aurait certains ordres qui ressortent plus que d'autres.
On peut appliquer le même raisonnement à rand() % n; qui ne
retourne un nombre (pseudo-)aléatoire entre [0, n[, que si
(RAND_MAX + 1) est un multiple de n. Dans le cas extrème ou n
vaut RAND_MAX, 0 a deux fois plus de chance d'être tiré qu'un
nombre parmi 1 à RAND_MAX - 1.
Richard Delorme a écrit :
>>> et je ne vois pas de forte raison à cela, on pourrait
>>> permuter chaque élément avec n'importe quel autre (et
>>> non pas avec un des éléments précédents).
>> Pour avoir une distribution aléatoire. Si à chaque fois tu
>> échanges un élément avec n'importe quel autre, tu vas avoir
>> n^n différents mélanges. Or, il y a exactement n! ordres
>> possible. Au moins que n! est facteur de n^n (ce qui n'est
>> pas possible), il y aurait certains ordres qui ressortent
>> plus que d'autres.
> On peut appliquer le même raisonnement à rand() % n; qui ne
> retourne un nombre (pseudo-)aléatoire entre [0, n[, que si
> (RAND_MAX + 1) est un multiple de n. Dans le cas extrème ou
> n vaut RAND_MAX, 0 a deux fois plus de chance d'être tiré
> qu'un nombre parmi 1 à RAND_MAX - 1.
c'est un des biais de la méthode.
un autre est la génération d'un "petit" nombre aléatoire
(inférieure à 8 ou 16) ici un modulo appliqué sur la sortie de
rand() est très biaisé;
une meilleure distribution serait de générer 32 ou 64 bits de
random, de compter les bits à '1' et d'appliquer le modulo sur
ce nombre.
Richard Delorme a écrit :
>>> et je ne vois pas de forte raison à cela, on pourrait
>>> permuter chaque élément avec n'importe quel autre (et
>>> non pas avec un des éléments précédents).
>> Pour avoir une distribution aléatoire. Si à chaque fois tu
>> échanges un élément avec n'importe quel autre, tu vas avoir
>> n^n différents mélanges. Or, il y a exactement n! ordres
>> possible. Au moins que n! est facteur de n^n (ce qui n'est
>> pas possible), il y aurait certains ordres qui ressortent
>> plus que d'autres.
> On peut appliquer le même raisonnement à rand() % n; qui ne
> retourne un nombre (pseudo-)aléatoire entre [0, n[, que si
> (RAND_MAX + 1) est un multiple de n. Dans le cas extrème ou
> n vaut RAND_MAX, 0 a deux fois plus de chance d'être tiré
> qu'un nombre parmi 1 à RAND_MAX - 1.
c'est un des biais de la méthode.
un autre est la génération d'un "petit" nombre aléatoire
(inférieure à 8 ou 16) ici un modulo appliqué sur la sortie de
rand() est très biaisé;
une meilleure distribution serait de générer 32 ou 64 bits de
random, de compter les bits à '1' et d'appliquer le modulo sur
ce nombre.
Richard Delorme a écrit :
>>> et je ne vois pas de forte raison à cela, on pourrait
>>> permuter chaque élément avec n'importe quel autre (et
>>> non pas avec un des éléments précédents).
>> Pour avoir une distribution aléatoire. Si à chaque fois tu
>> échanges un élément avec n'importe quel autre, tu vas avoir
>> n^n différents mélanges. Or, il y a exactement n! ordres
>> possible. Au moins que n! est facteur de n^n (ce qui n'est
>> pas possible), il y aurait certains ordres qui ressortent
>> plus que d'autres.
> On peut appliquer le même raisonnement à rand() % n; qui ne
> retourne un nombre (pseudo-)aléatoire entre [0, n[, que si
> (RAND_MAX + 1) est un multiple de n. Dans le cas extrème ou
> n vaut RAND_MAX, 0 a deux fois plus de chance d'être tiré
> qu'un nombre parmi 1 à RAND_MAX - 1.
c'est un des biais de la méthode.
un autre est la génération d'un "petit" nombre aléatoire
(inférieure à 8 ou 16) ici un modulo appliqué sur la sortie de
rand() est très biaisé;
une meilleure distribution serait de générer 32 ou 64 bits de
random, de compter les bits à '1' et d'appliquer le modulo sur
ce nombre.
C'est probablement lié à l'histoire.
[...] Est-ce que le contrat a toujours été tel ?certes.
Certes ? Tu as vérifié dans les versions anciennes
(pré-standard) de la STL ?
(dans vector, ce n'est pas l'argument que je ne trouve pas
mais les types internes, dont la définition de
difference_type).
Il les reprend de l'allocator.
C'est probablement lié à l'histoire.
[...] Est-ce que le contrat a toujours été tel ?
certes.
Certes ? Tu as vérifié dans les versions anciennes
(pré-standard) de la STL ?
(dans vector, ce n'est pas l'argument que je ne trouve pas
mais les types internes, dont la définition de
difference_type).
Il les reprend de l'allocator.
C'est probablement lié à l'histoire.
[...] Est-ce que le contrat a toujours été tel ?certes.
Certes ? Tu as vérifié dans les versions anciennes
(pré-standard) de la STL ?
(dans vector, ce n'est pas l'argument que je ne trouve pas
mais les types internes, dont la définition de
difference_type).
Il les reprend de l'allocator.
Richard Delorme a écrit :et je ne vois pas de forte raison à cela, on pourrait permuter
chaque élément avec n'importe quel autre (et non pas avec un des
éléments précédents).
Pour avoir une distribution aléatoire. Si à chaque fois tu
échanges un élément avec n'importe quel autre, tu vas avoir n^n
différents mélanges. Or, il y a exactement n! ordres possible.
Au moins que n! est facteur de n^n (ce qui n'est pas possible),
il y aurait certains ordres qui ressortent plus que d'autres.
On peut appliquer le même raisonnement à rand() % n; qui ne retourne
un nombre (pseudo-)aléatoire entre [0, n[, que si (RAND_MAX + 1) est
un multiple de n. Dans le cas extrème ou n vaut RAND_MAX, 0 a deux
fois plus de chance d'être tiré qu'un nombre parmi 1 à RAND_MAX - 1.
c'est un des biais de la méthode.
un autre est la génération d'un "petit" nombre aléatoire (inférieure
à 8 ou 16) ici un modulo appliqué sur la sortie de rand() est très
biaisé;
une meilleure distribution serait de générer 32 ou 64 bits
de random, de compter les bits à '1' et d'appliquer le modulo sur
ce nombre.
Richard Delorme a écrit :
et je ne vois pas de forte raison à cela, on pourrait permuter
chaque élément avec n'importe quel autre (et non pas avec un des
éléments précédents).
Pour avoir une distribution aléatoire. Si à chaque fois tu
échanges un élément avec n'importe quel autre, tu vas avoir n^n
différents mélanges. Or, il y a exactement n! ordres possible.
Au moins que n! est facteur de n^n (ce qui n'est pas possible),
il y aurait certains ordres qui ressortent plus que d'autres.
On peut appliquer le même raisonnement à rand() % n; qui ne retourne
un nombre (pseudo-)aléatoire entre [0, n[, que si (RAND_MAX + 1) est
un multiple de n. Dans le cas extrème ou n vaut RAND_MAX, 0 a deux
fois plus de chance d'être tiré qu'un nombre parmi 1 à RAND_MAX - 1.
c'est un des biais de la méthode.
un autre est la génération d'un "petit" nombre aléatoire (inférieure
à 8 ou 16) ici un modulo appliqué sur la sortie de rand() est très
biaisé;
une meilleure distribution serait de générer 32 ou 64 bits
de random, de compter les bits à '1' et d'appliquer le modulo sur
ce nombre.
Richard Delorme a écrit :et je ne vois pas de forte raison à cela, on pourrait permuter
chaque élément avec n'importe quel autre (et non pas avec un des
éléments précédents).
Pour avoir une distribution aléatoire. Si à chaque fois tu
échanges un élément avec n'importe quel autre, tu vas avoir n^n
différents mélanges. Or, il y a exactement n! ordres possible.
Au moins que n! est facteur de n^n (ce qui n'est pas possible),
il y aurait certains ordres qui ressortent plus que d'autres.
On peut appliquer le même raisonnement à rand() % n; qui ne retourne
un nombre (pseudo-)aléatoire entre [0, n[, que si (RAND_MAX + 1) est
un multiple de n. Dans le cas extrème ou n vaut RAND_MAX, 0 a deux
fois plus de chance d'être tiré qu'un nombre parmi 1 à RAND_MAX - 1.
c'est un des biais de la méthode.
un autre est la génération d'un "petit" nombre aléatoire (inférieure
à 8 ou 16) ici un modulo appliqué sur la sortie de rand() est très
biaisé;
une meilleure distribution serait de générer 32 ou 64 bits
de random, de compter les bits à '1' et d'appliquer le modulo sur
ce nombre.
un autre est la génération d'un "petit" nombre aléatoire (inférieure
à 8 ou 16) ici un modulo appliqué sur la sortie de rand() est très
biaisé;
Ceci n'arrive que sur les générateurs de mauvaise qualité (qui
malheureusement existent). Pour éviter ce problème, on préconise
généralement d'utiliser la formule : n * rand() / (RAND_MAX + 1.0).
une meilleure distribution serait de générer 32 ou 64 bits
de random, de compter les bits à '1' et d'appliquer le modulo sur
ce nombre.
Je ne pense pas. Le nombre de 1 parmi n bits aléatoires suit une
distribution binomiale (les valeurs centrales autour de n/2 sont plus
probables) or il vaut mieux une distribution uniforme.
un autre est la génération d'un "petit" nombre aléatoire (inférieure
à 8 ou 16) ici un modulo appliqué sur la sortie de rand() est très
biaisé;
Ceci n'arrive que sur les générateurs de mauvaise qualité (qui
malheureusement existent). Pour éviter ce problème, on préconise
généralement d'utiliser la formule : n * rand() / (RAND_MAX + 1.0).
une meilleure distribution serait de générer 32 ou 64 bits
de random, de compter les bits à '1' et d'appliquer le modulo sur
ce nombre.
Je ne pense pas. Le nombre de 1 parmi n bits aléatoires suit une
distribution binomiale (les valeurs centrales autour de n/2 sont plus
probables) or il vaut mieux une distribution uniforme.
un autre est la génération d'un "petit" nombre aléatoire (inférieure
à 8 ou 16) ici un modulo appliqué sur la sortie de rand() est très
biaisé;
Ceci n'arrive que sur les générateurs de mauvaise qualité (qui
malheureusement existent). Pour éviter ce problème, on préconise
généralement d'utiliser la formule : n * rand() / (RAND_MAX + 1.0).
une meilleure distribution serait de générer 32 ou 64 bits
de random, de compter les bits à '1' et d'appliquer le modulo sur
ce nombre.
Je ne pense pas. Le nombre de 1 parmi n bits aléatoires suit une
distribution binomiale (les valeurs centrales autour de n/2 sont plus
probables) or il vaut mieux une distribution uniforme.
Richard Delorme a écrit :un autre est la génération d'un "petit" nombre aléatoire (inférieure
à 8 ou 16) ici un modulo appliqué sur la sortie de rand() est très
biaisé;
Ceci n'arrive que sur les générateurs de mauvaise qualité (qui
malheureusement existent). Pour éviter ce problème, on préconise
généralement d'utiliser la formule : n * rand() / (RAND_MAX + 1.0).
cela dépend du "rand()".
pour un générateur produisant des mots 32 bits (eg Mersenne Twister),
on calcule bien: (int)((double) m * (double) n / (double) ULONG_MAX);
où 'm' est le mot généré.
mais pour un générateur produisant des octets, cela n'est pas valide.
une meilleure distribution serait de générer 32 ou 64 bits
de random, de compter les bits à '1' et d'appliquer le modulo sur
ce nombre.
Je ne pense pas. Le nombre de 1 parmi n bits aléatoires suit une
distribution binomiale (les valeurs centrales autour de n/2 sont plus
probables) or il vaut mieux une distribution uniforme.
les valeurs centrales sont plus probables, mais sont entre-elles
équiprobables;
lorsque (cas extrême) n vaut 1 ou 2, les sommes
(de bits à '1') paires ou impaires sont uniformes; tandis que
les nombres pairs et impairs sur 0..RAND_MAX seront beaucoup
moins uniformément généré
Richard Delorme a écrit :
un autre est la génération d'un "petit" nombre aléatoire (inférieure
à 8 ou 16) ici un modulo appliqué sur la sortie de rand() est très
biaisé;
Ceci n'arrive que sur les générateurs de mauvaise qualité (qui
malheureusement existent). Pour éviter ce problème, on préconise
généralement d'utiliser la formule : n * rand() / (RAND_MAX + 1.0).
cela dépend du "rand()".
pour un générateur produisant des mots 32 bits (eg Mersenne Twister),
on calcule bien: (int)((double) m * (double) n / (double) ULONG_MAX);
où 'm' est le mot généré.
mais pour un générateur produisant des octets, cela n'est pas valide.
une meilleure distribution serait de générer 32 ou 64 bits
de random, de compter les bits à '1' et d'appliquer le modulo sur
ce nombre.
Je ne pense pas. Le nombre de 1 parmi n bits aléatoires suit une
distribution binomiale (les valeurs centrales autour de n/2 sont plus
probables) or il vaut mieux une distribution uniforme.
les valeurs centrales sont plus probables, mais sont entre-elles
équiprobables;
lorsque (cas extrême) n vaut 1 ou 2, les sommes
(de bits à '1') paires ou impaires sont uniformes; tandis que
les nombres pairs et impairs sur 0..RAND_MAX seront beaucoup
moins uniformément généré
Richard Delorme a écrit :un autre est la génération d'un "petit" nombre aléatoire (inférieure
à 8 ou 16) ici un modulo appliqué sur la sortie de rand() est très
biaisé;
Ceci n'arrive que sur les générateurs de mauvaise qualité (qui
malheureusement existent). Pour éviter ce problème, on préconise
généralement d'utiliser la formule : n * rand() / (RAND_MAX + 1.0).
cela dépend du "rand()".
pour un générateur produisant des mots 32 bits (eg Mersenne Twister),
on calcule bien: (int)((double) m * (double) n / (double) ULONG_MAX);
où 'm' est le mot généré.
mais pour un générateur produisant des octets, cela n'est pas valide.
une meilleure distribution serait de générer 32 ou 64 bits
de random, de compter les bits à '1' et d'appliquer le modulo sur
ce nombre.
Je ne pense pas. Le nombre de 1 parmi n bits aléatoires suit une
distribution binomiale (les valeurs centrales autour de n/2 sont plus
probables) or il vaut mieux une distribution uniforme.
les valeurs centrales sont plus probables, mais sont entre-elles
équiprobables;
lorsque (cas extrême) n vaut 1 ou 2, les sommes
(de bits à '1') paires ou impaires sont uniformes; tandis que
les nombres pairs et impairs sur 0..RAND_MAX seront beaucoup
moins uniformément généré
Sylvain SF a écrit :
> Richard Delorme a écrit :
>>>> et je ne vois pas de forte raison à cela, on pourrait
>>>> permuter chaque élément avec n'importe quel autre (et
>>>> non pas avec un des éléments précédents).
>>> Pour avoir une distribution aléatoire. Si à chaque fois tu
>>> échanges un élément avec n'importe quel autre, tu vas
>>> avoir n^n différents mélanges. Or, il y a exactement n!
>>> ordres possible. Au moins que n! est facteur de n^n (ce
>>> qui n'est pas possible), il y aurait certains ordres qui
>>> ressortent plus que d'autres.
>> On peut appliquer le même raisonnement à rand() % n; qui ne
>> retourne un nombre (pseudo-)aléatoire entre [0, n[, que si
>> (RAND_MAX + 1) est un multiple de n. Dans le cas extrème ou
>> n vaut RAND_MAX, 0 a deux fois plus de chance d'être tiré
>> qu'un nombre parmi 1 à RAND_MAX - 1.
> c'est un des biais de la méthode.
Oui, mais on peut faire sans biais.
> un autre est la génération d'un "petit" nombre aléatoire
> (inférieure à 8 ou 16) ici un modulo appliqué sur la sortie
> de rand() est très biaisé;
Ceci n'arrive que sur les générateurs de mauvaise qualité (qui
malheureusement existent). Pour éviter ce problème, on
préconise généralement d'utiliser la formule : n * rand() /
(RAND_MAX + 1.0).
Sylvain SF a écrit :
> Richard Delorme a écrit :
>>>> et je ne vois pas de forte raison à cela, on pourrait
>>>> permuter chaque élément avec n'importe quel autre (et
>>>> non pas avec un des éléments précédents).
>>> Pour avoir une distribution aléatoire. Si à chaque fois tu
>>> échanges un élément avec n'importe quel autre, tu vas
>>> avoir n^n différents mélanges. Or, il y a exactement n!
>>> ordres possible. Au moins que n! est facteur de n^n (ce
>>> qui n'est pas possible), il y aurait certains ordres qui
>>> ressortent plus que d'autres.
>> On peut appliquer le même raisonnement à rand() % n; qui ne
>> retourne un nombre (pseudo-)aléatoire entre [0, n[, que si
>> (RAND_MAX + 1) est un multiple de n. Dans le cas extrème ou
>> n vaut RAND_MAX, 0 a deux fois plus de chance d'être tiré
>> qu'un nombre parmi 1 à RAND_MAX - 1.
> c'est un des biais de la méthode.
Oui, mais on peut faire sans biais.
> un autre est la génération d'un "petit" nombre aléatoire
> (inférieure à 8 ou 16) ici un modulo appliqué sur la sortie
> de rand() est très biaisé;
Ceci n'arrive que sur les générateurs de mauvaise qualité (qui
malheureusement existent). Pour éviter ce problème, on
préconise généralement d'utiliser la formule : n * rand() /
(RAND_MAX + 1.0).
Sylvain SF a écrit :
> Richard Delorme a écrit :
>>>> et je ne vois pas de forte raison à cela, on pourrait
>>>> permuter chaque élément avec n'importe quel autre (et
>>>> non pas avec un des éléments précédents).
>>> Pour avoir une distribution aléatoire. Si à chaque fois tu
>>> échanges un élément avec n'importe quel autre, tu vas
>>> avoir n^n différents mélanges. Or, il y a exactement n!
>>> ordres possible. Au moins que n! est facteur de n^n (ce
>>> qui n'est pas possible), il y aurait certains ordres qui
>>> ressortent plus que d'autres.
>> On peut appliquer le même raisonnement à rand() % n; qui ne
>> retourne un nombre (pseudo-)aléatoire entre [0, n[, que si
>> (RAND_MAX + 1) est un multiple de n. Dans le cas extrème ou
>> n vaut RAND_MAX, 0 a deux fois plus de chance d'être tiré
>> qu'un nombre parmi 1 à RAND_MAX - 1.
> c'est un des biais de la méthode.
Oui, mais on peut faire sans biais.
> un autre est la génération d'un "petit" nombre aléatoire
> (inférieure à 8 ou 16) ici un modulo appliqué sur la sortie
> de rand() est très biaisé;
Ceci n'arrive que sur les générateurs de mauvaise qualité (qui
malheureusement existent). Pour éviter ce problème, on
préconise généralement d'utiliser la formule : n * rand() /
(RAND_MAX + 1.0).
