rand - Page 3

Pollux :
Je te remercie et je t'autorise à relire mon message
Bon, je réexplique : si on prend n=64 au lieu de n=56, on perd log2(64/56)=0.2 bits d'entropie. Et on a 32 bits, donc ça va vraiment pas être la mort de perdre 0.2 bits

Personnellement, je trouve qu'une perte de qualité est une perte de qualité, donc je n'en veux pas. Et je veux une distribution uniforme, ce que ce que tu proposes n'est pas.

Cela dit, il y a une erreur dans le code dont je me suis rendue compte bien après l'avoir codée: la valeur du port peut aussi valoir 0 (il passe d'abord à 0, puis au prochain tick seulement à la valeur initiale). Donc pour une distribution vraiment uniforme, il faut mettre:

  unsigned long randnum=255-(unsigned char)(peekIO(0x600017)-1);
  if (!AMS_1xx || *(unsigned short *)0x32==(('R'<<8)+'O'))
    randnum+=(*((volatile unsigned long*)(_rom_call_addr(4FC))))*((HW_VERSION == 2)?53:79);
  srand(randnum);

Je vais corriger ça dans Backgammon, et le randomize que je vais mettre dans TIGCCLIB en remplacement de la blague qu'il y a actuellement ressemblera beaucoup à cela.

Kevin, ça faisait longtemps que je ne t'avais pas entendu dire un truc aussi génial (c'est un peu comme les optimisations en taille qui gagnent 2 octets sur un programme tout en faisant perdre 30% de vitesse au jeu )

PS: Si je veux mettre ma routine dans TIGCCLIB en remplacement du randomize actuel, c'est à la demande de Zeljko (mais je trouve qu'il a raison: le randomize actuel est inutilisable en pratique).

Je ne dis pas qu'il ne faut pas remplacer le randomize, parce que ce serait une très bonne idée. Mais :
1) ça ne change qqch qu'à partir de quelle version d'AMS ?
2) ça ne sert strictement à _rien_ de vouloir gagner 0.2/32 = 1/160 < 1% de données aléatoires d'initialisation en plus, alors que la routine va grossir de plusieurs dizaines d'octets (probablement pas mal : test du hardware, multiplication par un 'long')

Pollux :

Je ne vois pas ce qu'il y a de drôle dans ce que je dis. Mon algorithme(*) est mathématiquement correct (distribution équiprobable, application surjective sur l'anneau Z/2³²Z entier), avec ton "amélioration", il ne l'est pas (application non-surjective sur HW2, surjective mais avec une distribution inéquitable sur HW1). Et le mien est aussi "logiquement" correct: mon timer(*) est exactement le nombre de ticks modulo 2³² (la combinaison de 0x600017 et FiftyMsecTick n'est pas choisie au hasard).

(*) = avec ma correction du message ./61 (qui fait juste un subq.b #1 de plus, rien de dramatique).

Pollux :
1) ça ne change qqch qu'à partir de quelle version d'AMS ?

2.00 (ou PedroM).

2) ça ne sert strictement à _rien_ de vouloir gagner 0.2/32 = 1/160 < 1% de données aléatoires d'initialisation en plus, alors que la routine va grossir de plusieurs dizaines d'octets (probablement pas mal : test du hardware, multiplication par un 'long')

Je ne suis pas d'accord.

Et enfin, ton calcul est faux. Avec ton "optimisation", sur HW2, on perd (2³²-2²⁶*53)/2³²=0,17..., c'est-à-dire plus de 17%, des nombres aléatoires possibles!

Je ne sais pas comment marche la routine rand de tigcc, mais est-ce qu'elle vérifie ceci :

2.4.1 When "random", it must be capable of generating a uniformly random integer in the range 1 <= x <= n, for any value 1 <= n <= 32767. Any method can be used for this (for instance, using the host computer's clock time in milliseconds). The uniformity of randomness should be optimised for low values of n (say, up to 100 or so) and it is especially important to avoid regular patterns appearing in remainders after division (most crudely, being alternately odd and even).
2.4.2 The generator is switched into "predictable" state with a seed value. On any two occasions when the same seed is sown, identical sequences of values must result (for an indefinite period) until the generator is switched back into "random" mode. The generator should cope well with very low seed values, such as 10, and should not depend on the seed containing many non-zero bits.

?

Oui, à condition de remplacer le randomize par ma routine. (Le randomize actuel ne vérifie pas du tout les critères d'uniformité. Celui de Pollux non plus, d'ailleurs, donc encore une raison de le rejeter: ce n'est pas conforme au standard C. ) TIGCCLIB utilise l'algorithme standard qu'on trouve un peu partout (multiplication par 0x41C64E6D et addition de 12345, le tout modulo 2³²). Le long entier est stocké dans le seed, mais seuls les 16 bits du milieu sont retournés à chaque fois parce que rand retourne un int (donc short).

Kevin Kofler
:

Pollux :

Je ne vois pas ce qu'il y a de drôle dans ce que je dis. Mon algorithme(*) est mathématiquement correct (distribution équiprobable, application surjective sur l'anneau Z/2³²Z entier)

Mais oui, bien sûr
Tu sais qu'il faut 20 jours avant de décrire tout ça? Tu sais que s'il y a un reset entre temps ta jolie théorie tombe à l'eau? Et tu sais que à moins de l'utiliser 20 jours après au 50è de milliseconde près, ça n'arrivera _jamais_? (je suis même prêt à prendre les paris ). Et tu sais aussi que le générateur aléatoire que vous utilisez est très perfectible, et que ce serait certainement une meilleure idée d'améliorer ça plutôt que de rajouter un cinquième de bit dans le générateur aléatoire? (notamment, j'ai de bonnes raisons de penser que random()&1 n'est pas si aléatoire que ça)

2) ça ne sert strictement à _rien_ de vouloir gagner 0.2/32 = 1/160 < 1% de données aléatoires d'initialisation en plus, alors que la routine va grossir de plusieurs dizaines d'octets (probablement pas mal : test du hardware, multiplication par un 'long')

Je ne suis pas d'accord.

Et enfin, ton calcul est faux. Avec ton "optimisation", sur HW2, on perd (2^32-2^26*53)/2^32=0,17..., c'est-à-dire plus de 17%, des nombres aléatoires possibles!

Tu parles en nombres de seeds possibles, je parle en shannon. Une clé 1025 bits n'est pas 2 fois meilleure qu'une clé 1024 bit

Oui, à condition de remplacer le randomize par ma routine. (Le randomize actuel ne vérifie pas du tout les critères d'uniformité. Celui de Pollux non plus, d'ailleurs, donc encore une raison de le rejeter: ce n'est pas conforme au standard C. )

Relis. Le standard C ne demande pas que la seed (32 bits) soit choisi uniformément, ce n'est obligatoire que pour un nombre aléatoire généré (15 bits). Ca n'a vraiment rien à voir Et très sincèrement, une plateforme utilisant un long (de 31 bits) n'aurait aucun handicap de ce point de vue-là


Enfin bon, je n'aurai certainement pas le courage d'aller forker cette routine pour que GTC utilise la version la plus raisonnable, parce que je sais parfaitement que ça te fera un "argument" de plus contre GTC sur le forum TICT et que je serai obligé de passer des heures à me (re-)justifier, chose dont j'ai vraiment marre... Surtout si toi et XDanger vous relayez

it is especially important to avoid regular patterns appearing in remainders after division (most crudely, being alternately odd and even).

j'ai de bonnes raisons de penser que random()&1 n'est pas si aléatoire que ça

?

La modification de la seed est :

multiplication par 0x41C64E6D et addition de 12345, le tout modulo 2^32

puis on divise par 2^8

Si tu considères la seed modulo 2^8, c'est une multiplication par 0x6D et addition de 57. Bref, périodicité de 256. C'est vraiment autrement plus grave que le fait que la seed soit initialement sur 31 bits (j'arrondis à l'inférieur pour faire plaisir à Kevin) et pas sur 32 bits.

Pollux
:

Kevin Kofler
:

Pollux :

Je ne vois pas ce qu'il y a de drôle dans ce que je dis. Mon algorithme(*) est mathématiquement correct (distribution équiprobable, application surjective sur l'anneau Z/2³²Z entier)

Mais oui, bien sûr
Tu sais qu'il faut 20 jours avant de décrire tout ça? Tu sais que s'il y a un reset entre temps ta jolie théorie tombe à l'eau? Et tu sais que à moins de l'utiliser 20 jours après au 50è de milliseconde près, ça n'arrivera _jamais_? (je suis même prêt à prendre les paris ).

Tout ceci n'a rien à voir avec l'uniformité ou non de la distribution. Et mes calculatrices tournent facilement 20 jours sans reset.

Et tu sais aussi que le générateur aléatoire que vous utilisez est très perfectible, et que ce serait certainement une meilleure idée d'améliorer ça plutôt que de rajouter un cinquième de bit dans le générateur aléatoire? (notamment, j'ai de bonnes raisons de penser que random()&1 n'est pas si aléatoire que ça)

* On utilise le même algorithme que pratiquement tout le monde. (Va lire les sources de newlib et semblables...)
* Va voir ma réponse à Lily plus en bas.

Et enfin, ton calcul est faux. Avec ton "optimisation", sur HW2, on perd (2^32-2^26*53)/2^32=0,17..., c'est-à-dire plus de 17%, des nombres aléatoires possibles!

Tu parles en nombres de seeds possibles, je parle en shannon.

Et je parle en ce qui compte, toi tu nous sors une théorie qui n'a rien à voir. Ce qui est intéressant pour un jeu comme Backgammon, c'est le nombre de parties différentes possible, pas les pertes de bits.

Une clé 1025 bits n'est pas 2 fois meilleure qu'une clé 1024 bit

Si, il faut 2 fois plus de temps pour la cracker!

Oui, à condition de remplacer le randomize par ma routine. (Le randomize actuel ne vérifie pas du tout les critères d'uniformité. Celui de Pollux non plus, d'ailleurs, donc encore une raison de le rejeter: ce n'est pas conforme au standard C. )

Relis. Le standard C ne demande pas que la seed (32 bits) soit choisi uniformément, ce n'est obligatoire que pour un nombre aléatoire généré (15 bits). Ca n'a vraiment rien à voir

Démontre-moi (mathématiquement) que ton seed satisfait cette condition... Je pense que tu n'y arriveras pas, parce que c'est vraisemblablement faux. (Uniforme veut bien dire uniforme, et pas uniforme ±10% ou un truc du style.)

Et très sincèrement, une plateforme utilisant un long (de 31 bits) n'aurait aucun handicap de ce point de vue-là

Où est le rapport?

Lily
:

it is especially important to avoid regular patterns appearing in remainders after division (most crudely, being alternately odd and even).

j'ai de bonnes raisons de penser que random()&1 n'est pas si aléatoire que ça

?

N'oublie pas que les derniers 8 bits du seed sont jetés quand le résultat est retourné (tout comme les premiers). (Le seed, lui, les garde évidemment.)

Et puis d'ailleurs, tant qu'on est dans les défauts de cette algorithme, on n'utilise pas les 9 bits de poids fort de la seed...

[edit : cross post]

Pollux :
La modification de la seed est :

multiplication par 0x41C64E6D et addition de 12345, le tout modulo 2^32

puis on divise par 2^8
Si tu considères la seed modulo 2^8, c'est une multiplication par 0x6D et addition de 57. Bref, périodicité de 256. C'est vraiment autrement plus grave que le fait que la seed soit initialement sur 31 bits (j'arrondis à l'inférieur pour faire plaisir à Kevin) et pas sur 32 bits.

Plusieurs erreurs:
1. On divise un modulo 2³² par 2⁸, il reste 2²⁴ comme modulo, pas 2⁸.
2. Même cela n'est pas valable parce que le nombre par lequel on multiplie et le nombre qu'on ajoute ne sont pas divisibles par 2⁸. Tu ne peux simplifier mod(a*x+b,2³²)/2⁸ en mod((a/2⁸)*x+b/2⁸,2²⁴) que si a et b sont divisibles par 8. Tu ne peux pas faire ça avec des divisions euclidiennes à reste non nul.
3. Pour illustrer mon 2., un petit contre-exemple:
12345=0x3039
0x41C64E*0x3+0x30=0xC5531A
(0x41C64E6D*0x3+0x3039)>>8=0xC5531B

Pollux
: Et puis d'ailleurs, tant qu'on est dans les défauts de cette algorithme, on n'utilise pas les 9 bits de poids fort de la seed...

Ah oui, ce sont 9 bits qui sont jetés à gauche et pas 8 parce que le standard veut que ce soit <=32767. Ce n'est pas un défaut.

Kevin Kofler
:

Pollux
:

Kevin Kofler
:

Pollux :

Je ne vois pas ce qu'il y a de drôle dans ce que je dis. Mon algorithme(*) est mathématiquement correct (distribution équiprobable, application surjective sur l'anneau Z/2³²Z entier)

Mais oui, bien sûr
Tu sais qu'il faut 20 jours avant de décrire tout ça? Tu sais que s'il y a un reset entre temps ta jolie théorie tombe à l'eau? Et tu sais que à moins de l'utiliser 20 jours après au 50è de milliseconde près, ça n'arrivera _jamais_? (je suis même prêt à prendre les paris ).

Tout ceci n'a rien à voir avec l'uniformité ou non de la distribution.

Carrément pas : ça veut dire que seule la quasi-injectivité importe, pas la quasi-surjectivité (et donc, il vaudrait mieux prendre 128 pour que ça marche parfaitement bien sur HW2). Mais les deux sont évidemment liées.

Et mes calculatrices tournent facilement 20 jours sans reset.

Sauf que tu ne les lances pas périodiquement tous les 20 jours avec une précision extrême, donc tu es sûr que tu ne joueras pas à la même partie de Backgammon...

Et tu sais aussi que le générateur aléatoire que vous utilisez est très perfectible, et que ce serait certainement une meilleure idée d'améliorer ça plutôt que de rajouter un cinquième de bit dans le générateur aléatoire? (notamment, j'ai de bonnes raisons de penser que random()&1 n'est pas si aléatoire que ça)

* On utilise le même algorithme que pratiquement tout le monde. (Va lire les sources de newlib et semblables...)

* Va voir ma réponse à Lily plus en bas.

Et enfin, ton calcul est faux. Avec ton "optimisation", sur HW2, on perd (2^32-2^26*53)/2^32=0,17..., c'est-à-dire plus de 17%, des nombres aléatoires possibles!

Tu parles en nombres de seeds possibles, je parle en shannon.

Et je parle en ce qui compte, toi tu nous sors une théorie qui n'a rien à voir. Ce qui est intéressant pour un jeu comme Backgammon, c'est le nombre de parties différentes possible, pas les pertes de bits.

Une clé 1025 bits n'est pas 2 fois meilleure qu'une clé 1024 bit

Si, il faut 2 fois plus de temps pour la cracker!

On a quand même des algorithmes non exponentiels pour ça : O(exp((64/9.n)^(1/3).ln(n)^(2/3)))
Le quotient entre n=1025 et n=1024 n'est que de 3%, donc arrête de pipoter. Et si tu pipotes pour un truc aussi classique que la factorisation de nombres premiers, alors je ne sais que trop quoi penser quant à ta crédibilité dans cette affaire

Oui, à condition de remplacer le randomize par ma routine. (Le randomize actuel ne vérifie pas du tout les critères d'uniformité. Celui de Pollux non plus, d'ailleurs, donc encore une raison de le rejeter: ce n'est pas conforme au standard C. )

Relis. Le standard C ne demande pas que la seed (32 bits) soit choisi uniformément, ce n'est obligatoire que pour un nombre aléatoire généré (15 bits). Ca n'a vraiment rien à voir

Démontre-moi (mathématiquement) que ton seed satisfait cette condition... Je pense que tu n'y arriveras pas, parce que c'est vraisemblablement faux. (Uniforme veut bien dire uniforme, et pas uniforme ±10% ou un truc du style.)

C'est évident qu'un seed "uniforme +/- 10%" va, si on le hashe correctement pour avoir une valeur 16 bits, être pris complètement uniformément (+/- 10%/2^16 soit 0.000015. En pratique, on a besoin de plus de 16 bits pour ne pas avoir de cycles, mais tu vois l'idée.

Et très sincèrement, une plateforme utilisant un long (de 31 bits) n'aurait aucun handicap de ce point de vue-là

Où est le rapport?

Le rapport, c'est que ma méthode a une image de cardinal un peu plus de 2^31 et pas exactement 2^32. Donc c'est comme si j'utilisais un signed long et pas un unsigned. Pourtant le standard n'interdis pas d'utiliser un signed long pour ça...

Lily
:

it is especially important to avoid regular patterns appearing in remainders after division (most crudely, being alternately odd and even).

j'ai de bonnes raisons de penser que random()&1 n'est pas si aléatoire que ça

?

N'oublie pas que les derniers 8 bits du seed sont jetés quand le résultat est retourné (tout comme les premiers). (Le seed, lui, les garde évidemment.)

Oui, les bits de poids faibles, et?

Kevin Kofler
:

Pollux :
La modification de la seed est :

multiplication par 0x41C64E6D et addition de 12345, le tout modulo 2^32

puis on divise par 2^8
Si tu considères la seed modulo 2^8, c'est une multiplication par 0x6D et addition de 57. Bref, périodicité de 256. C'est vraiment autrement plus grave que le fait que la seed soit initialement sur 31 bits (j'arrondis à l'inférieur pour faire plaisir à Kevin) et pas sur 32 bits.

Plusieurs erreurs:
1. On divise un modulo 2³² par 2⁸, il reste 2²⁴ comme modulo, pas 2⁸.
2. Même cela n'est pas valable parce que le nombre par lequel on multiplie et le nombre qu'on ajoute ne sont pas divisibles par 2⁸. Tu ne peux simplifier mod(a*x+b,2³²)/2⁸ en mod((a/2⁸)*x+b/2⁸,2²⁴) que si a et b sont divisibles par 8. Tu ne peux pas faire ça avec des divisions euclidiennes à reste non nul.

Tu es gentil, mais tu vas encore essayer de relire mon message : tu prends modulo 2^8 (hum, en fait c'est modulo 2^9 parce qu'il faut aussi un bit pour la valeur du rand()&1), je ne te parle pas de diviser par 2^8...

3. Pour illustrer mon 2., un petit contre-exemple:
12345=0x3039
0x41C64E*0x3+0x30=0xC5531A (0x41C64E6D*0x3+0x3039)>>8=0xC5531B

Et prends-moi pour un con...

Pollux
: Et puis d'ailleurs, tant qu'on est dans les défauts de cette algorithme, on n'utilise pas les 9 bits de poids fort de la seed...

Ah oui, ce sont 9 bits qui sont jetés à gauche et pas 8 parce que le standard veut que ce soit <=32767. Ce n'est pas un défaut.[/cite]
??? Ca veut dire que la seed n'a que 2^23 valeurs possibles, c'est un gros gros défaut (plus exactement, on peut quotienter par 0x800000.Z sans changer la valeur finale)

Martial Demolins :
lol t'aime pas gacher des pixels de texte pour rien toi

J'essaye juste de limiter les dégâts des bêtises de Kevin. Il prétend avoir une méthode ultime, et qui est telle que si on modifie un bit de la source, elle donne de mauvais résultats; je lui montre que c'est parfaitement faux, que ce n'est pas la peine de gâcher des octets pour ça, et que de toute façon la fonction rand() a bien plus de défauts qu'il ne pourrait le soupçonner.

Pollux
: Carrément pas : ça veut dire que seule la quasi-injectivité importe, pas la quasi-surjectivité (et donc, il vaudrait mieux prendre 128 pour que ça marche parfaitement bien sur HW2).

Non...

Sauf que tu ne les lances pas périodiquement tous les 20 jours avec une précision extrême, donc tu es sûr que tu ne joueras pas à la même partie de Backgammon...

... parce que cet argument n'est pas valable, tu réduis le nombre de parties possibles de 17% et c'est un fait indéniable.

* On utilise le même algorithme que pratiquement tout le monde. (Va lire les sources de newlib et semblables...)

D'ailleurs, il se trouve même en "EXAMPLE" dans le standard C. C'est à la lettre le même que dans TIGCCLIB (à part que celui de TIGCCLIB est en assembleur 68k). Il y a même la division par 65536 et le modulo par 32768. C'est de là que toutes les implémentations le recopient.

Une clé 1025 bits n'est pas 2 fois meilleure qu'une clé 1024 bit

Si, il faut 2 fois plus de temps pour la cracker!

On a quand même des algorithmes non exponentiels pour ça : O(exp((64/9.n)^(1/3).ln(n)^(2/3))) Le quotient entre n=1025 et n=1024 n'est que de 3%, donc arrête de pipoter. Et si tu pipotes pour un truc aussi classique que la factorisation de nombres premiers, alors je ne sais que trop quoi penser quant à ta crédibilité dans cette affaire

1. C'est quand-même exponentiel en principe.
2. Qui t'a dit que je parlais de clés asymétriques à clé publique connue? Si on parle de clés symétriques, ou de clés asymétriques à clé publique inconnue (ce qui revient à peu près au même), ton argument ne vaut plus rien.

Démontre-moi (mathématiquement) que ton seed satisfait cette condition... Je pense que tu n'y arriveras pas, parce que c'est vraisemblablement faux. (Uniforme veut bien dire uniforme, et pas uniforme ±10% ou un truc du style.)

C'est évident qu'un seed "uniforme +/- 10%" va, si on le hashe correctement pour avoir une valeur 16 bits, être pris complètement uniformément (+/- 10%/2^16 soit 0.000015. En pratique, on a besoin de plus de 16 bits pour ne pas avoir de cycles, mais tu vois l'idée.

1. Je te parle de "uniforme ±10%" après tous les calculs.
2. Si le standard dit "uniforme", ça veut dire ce que ça veut dire. C'est-à-dire que même "uniforme ±10^-1000000%" ne convient pas, parce que ce n'est pas uniforme!!!

Et très sincèrement, une plateforme utilisant un long (de 31 bits) n'aurait aucun handicap de ce point de vue-là

Où est le rapport?

Le rapport, c'est que ma méthode a une image de cardinal un peu plus de 2^31 et pas exactement 2^32. Donc c'est comme si j'utilisais un signed long et pas un unsigned. Pourtant le standard n'interdis pas d'utiliser un signed long pour ça...

Le problème est que ta distribution de seeds n'est pas équiprobable. Il y a des seeds qui ne sont pas utilisés et d'autres qui sont utilisés en double (enfin, pour être précis, c'est soit l'un soit l'autre en fonction de la version matérielle). Si on fait ça sur 31 bits en équiprobable, c'est autre chose!

Lily
:

it is especially important to avoid regular patterns appearing in remainders after division (most crudely, being alternately odd and even).

j'ai de bonnes raisons de penser que random()&1 n'est pas si aléatoire que ça

?

N'oublie pas que les derniers 8 bits du seed sont jetés quand le résultat est retourné (tout comme les premiers). (Le seed, lui, les garde évidemment.)

Oui, les bits de poids faibles, et?

Et ça réduit de loin le problème de la période.

Pollux :
Tu es gentil, mais tu vas encore essayer de relire mon message : tu prends modulo 2^8 (hum, en fait c'est modulo 2^9 parce qu'il faut aussi un bit pour la valeur du rand()&1), je ne te parle pas de diviser par 2^8...

Ah, tu parles du dernier bit... Ben, on fait notre possible pour qu'il soit varié. Il me semble bien que la période soit la plus longue possible pour une application affine en modulo. Et c'est pour ça que si tu prends un random(2), il va prendre le premier bit (non-jeté), pas le dernier.

Ah oui, ce sont 9 bits qui sont jetés à gauche et pas 8 parce que le standard veut que ce soit <=32767. Ce n'est pas un défaut.

??? Ca veut dire que la seed n'a que 2^23 valeurs possibles, c'est un gros gros défaut (plus exactement, on peut quotienter par 0x800000.Z sans changer la valeur finale)

En tout cas, ça fait en sorte que ton idée d'"optimisation" du calcul du seed jette même plus de 17% des seeds possibles!

Kevin Kofler
:

Pollux
: Carrément pas : ça veut dire que seule la quasi-injectivité importe, pas la quasi-surjectivité (et donc, il vaudrait mieux prendre 128 pour que ça marche parfaitement bien sur HW2).

Non...

Sauf que tu ne les lances pas périodiquement tous les 20 jours avec une précision extrême, donc tu es sûr que tu ne joueras pas à la même partie de Backgammon...

... parce que cet argument n'est pas valable, tu réduis le nombre de parties possibles de 17% et c'est un fait indéniable.

Ca ne veut rien dire du tout. cf plus bas.

* On utilise le même algorithme que pratiquement tout le monde. (Va lire les sources de newlib et semblables...)

D'ailleurs, il se trouve même en "EXAMPLE" dans le standard C. C'est à la lettre le même que dans TIGCCLIB (à part que celui de TIGCCLIB est en assembleur 68k). Il y a même la division par 65536 et le modulo par 32768. C'est de là que toutes les implémentations le recopient.

Eh ben c loin d'être un modèle d'efficacité. Et en tout cas c'est tellement inefficace que tes considérations sur 0.25 bits en plus ou en moins ne veulent rien dire.

Une clé 1025 bits n'est pas 2 fois meilleure qu'une clé 1024 bit

Si, il faut 2 fois plus de temps pour la cracker!

On a quand même des algorithmes non exponentiels pour ça : O(exp((64/9.n)^(1/3).ln(n)^(2/3))) Le quotient entre n=1025 et n=1024 n'est que de 3%, donc arrête de pipoter. Et si tu pipotes pour un truc aussi classique que la factorisation de nombres premiers, alors je ne sais que trop quoi penser quant à ta crédibilité dans cette affaire

1. C'est quand-même exponentiel en principe. 2. Qui t'a dit que je parlais de clés asymétriques à clé publique connue? Si on parle de clés symétriques, ou de clés asymétriques à clé publique inconnue (ce qui revient à peu près au même), ton argument ne vaut plus rien.

1. sub-exponentiel. Super-polynômial, peut-être; mais il y a une différence fondamentale, c'est que la limite de u(n+1)/u(n) est 1 et pas une constante >1 comme pour un algo exponentiel. D'où ton erreur
2. Ne sois pas de mauvaise fois. Primo tu as dis qu'il _fallait_ 2 fois plus de temps, ce qui laisse supposer que tu considérais tous les cas ou à la limite que tu te restreignais aux cas les plus courants. Or, 1024 bits, c'est typiquement une clé d'un algo à clé publique; et c'est même le nb de bits de la clé de TI [en fait, c'est un tout petit peu plus].

Démontre-moi (mathématiquement) que ton seed satisfait cette condition... Je pense que tu n'y arriveras pas, parce que c'est vraisemblablement faux. (Uniforme veut bien dire uniforme, et pas uniforme ±10% ou un truc du style.)

C'est évident qu'un seed "uniforme +/- 10%" va, si on le hashe correctement pour avoir une valeur 16 bits, être pris complètement uniformément (+/- 10%/2^16 soit 0.000015. En pratique, on a besoin de plus de 16 bits pour ne pas avoir de cycles, mais tu vois l'idée.

1. Je te parle de "uniforme ±10%" après tous les calculs.

Alors tu te trompes lourdement.

2. Si le standard dit "uniforme", ça veut dire ce que ça veut dire. C'est-à-dire que même "uniforme ±10^-1000000%" ne convient pas, parce que ce n'est pas uniforme!!!

Poste ça sur un forum un peu au courant des implémentations classiques de la random de la stdlib et tout le monde va te rire au nez; ce n'est pas pour rien que la routine d' "example" du standard C est pourrie, c'est parce qu'en général c'est mal implémenté (c'est aussi le cas sous TIGCC, quoi que tu en penses). Avoir 2^32 ou 2^31 possibilités de seeds ne changera rien.

Et très sincèrement, une plateforme utilisant un long (de 31 bits) n'aurait aucun handicap de ce point de vue-là

Où est le rapport?

Le rapport, c'est que ma méthode a une image de cardinal un peu plus de 2^31 et pas exactement 2^32. Donc c'est comme si j'utilisais un signed long et pas un unsigned. Pourtant le standard n'interdis pas d'utiliser un signed long pour ça...

Le problème est que ta distribution de seeds n'est pas équiprobable. Il y a des seeds qui ne sont pas utilisés et d'autres qui sont utilisés en double (enfin, pour être précis, c'est soit l'un soit l'autre en fonction de la version matérielle). Si on fait ça sur 31 bits en équiprobable, c'est autre chose!

Bon, on va d'abord se restreindre au cas des HW2 (quitte à prendre 128 au lieu de 64). L'image n'est "que" de 2^31.8, je ne vois pas le problème? Après ça, le premier appel de rand() renverra un hash qu'on peut supposer uniformément réparti...

Lily
:

it is especially important to avoid regular patterns appearing in remainders after division (most crudely, being alternately odd and even).

j'ai de bonnes raisons de penser que random()&1 n'est pas si aléatoire que ça

?

N'oublie pas que les derniers 8 bits du seed sont jetés quand le résultat est retourné (tout comme les premiers). (Le seed, lui, les garde évidemment.)

Oui, les bits de poids faibles, et?

Et ça réduit de loin le problème de la période.

Je ne dis pas qu'il est constant, je dis qu'il est de période 512. Bof bof.

Pollux :
Tu es gentil, mais tu vas encore essayer de relire mon message : tu prends modulo 2^8 (hum, en fait c'est modulo 2^9 parce qu'il faut aussi un bit pour la valeur du rand()&1), je ne te parle pas de diviser par 2^8...

Ah, tu parles du dernier bit... Ben, on fait notre possible pour qu'il soit varié. Il me semble bien que la période soit la plus longue possible pour une application affine en modulo. Et c'est pour ça que si tu prends un random(2), il va prendre le premier bit (non-jeté), pas le dernier.

Oui, je sais.

Ah oui, ce sont 9 bits qui sont jetés à gauche et pas 8 parce que le standard veut que ce soit <=32767. Ce n'est pas un défaut.

??? Ca veut dire que la seed n'a que 2^23 valeurs possibles, c'est un gros gros défaut (plus exactement, on peut quotienter par 0x800000.Z sans changer la valeur finale)

En tout cas, ça fait en sorte que ton idée d'"optimisation" du calcul du seed jette même plus de 17% des seeds possibles!

Mais si on remplace le lsr #8 par un moveq #9,dn/lsr dn, on perd 2 octets mais on élimine toute la détection du hardware et la multiplication, et on gagne en précision...

[EDIT : me suis loupé dans les [cite]]

Je quote la suite des spécifications Z-machine :

Remarks

It is dangerous to rely on the ANSI C random number routines, as some
implementations of these are very poor. This has made some games (in particular, 'Balances') unwinnable on some Unix ports of Zip.

En tout cas, si rand est trop mauvais pour toi, il y a la librairie statique ExtRand de Peter J. Rowe qui est censée faire mieux à travers l'utilisation de plus de bits. (Pollux, tu peux t'amuser à démonter ses algorithmes si tu as envie. )

(Pollux, tu peux t'amuser à démonter ses algorithmes si tu as envie. )

Si c'est un truc fait pour être fiable, je pense que le fait que ça soit efficace ne viendra pas seulement de "l'utilisation de plus de bits" mais aussi d'un algo un peu mieux pensé... Donc je crois pas qu'il y ait grand chose à démonter

Ton randomize() est un peu comme si tu voulais faire un calcul d'un sinus en utilisant une lib qui calcule 1000 chiffres après la virgule, mais que tu fais un DL à l'ordre 5 Le pire c'est que tu t'offusques si on passe à 999 chiffres parce que ça fait "perdre de la précision" (ce qui n'est pas entièrement faux en théorie : la précision est strictement inférieure en moyenne, même si pour |x| > 10^-190 le dernier chiffre est complètement aléatoire).

Perso, j'ai besoin souvent d'un générateur de nombres aléatoires uniforme, mais vraiment uniforme parce que sinon, pour obtenir un générateur uniforme, il me faut passer par la loi de répartition, et ça saoûle.
Pour ceux qui se demandent à quoi ça sert, c'est qu'à partir d'un générateur - l'uniforme étant le plus simple -, on peut générer une suite selon n'importe quelle loi. et si c'est pas uniforme, je risque fortement de déplacer les moments de ma loi...

L'algo qui est dans les sources originales de pinfocom est marrant :

extern word     random1;
extern word     random2;

word            temp;

temp = random1 << 1;
random1 = random2;
if (random2 & 0x8000)
    ++temp;
random2 ^= temp;
if (num)
    store(((word)(random2 & 0x7FFF) % num) + 1);
else
    store(0);

mais je ne sais pas si c'est très bon...
Sinon j'ai trouvé ça : http://www.helsbreth.org/random/rng_combo.html ils ont l'air de dire que ça marche bien

Pour le combo, il faut un long long pour le seed (au moins 48 bits), avec la résolution de nos timers et la fréquence moyenne des resets, on ne va pas pouvoir générer autant de bits de seed. 32 bits est le mieux qu'on puisse avoir comme seed.

L'exemple qu'ils donnent n'utilise que des unsigned long pourtant (et une seule seed) ?

Ils utilisent 3 longs, donc 96 bits. Mais leur fonction d'initialisation permet d'initialiser les 3 seeds á partir d'un seul de 32 bits. On peut mettre ça dans srand. Cela dit, avec ça, je vais devoir changer le format des fichiers de sauvegarde de Backgammon (rajouter 64 bits pour les 2 seeds supplémentaires). Mais bon, je ne vais pas empêcher un progrès dans TIGCCLIB juste parce qu'un hack grossier dans Backgammon a besoin d'un changement en conséquence. Le conflit d'intérêts n'est pas grand à ce point. Attention, je ne dis pas que ce sera définitivement cet algorithme-là qu'on va prendre si on change rand, il y en a d'autres qui sont intéressants. Et randomize a une priorité plus grande, parce que c'est là le défaut n°1 de notre système actuel.

Il y a certainement bcp plus simple que 'combo' sans être aussi affreux que l'actuel (ne serait-ce qu'en faisant un bête swap/lsr.w #1 du seed au lieu de faire comme c'est fait actuellement [lsr.l #8]).