subtilité de rand VG5000

[Carl]

environ 1.5 milliard de tirages....pas de zéro ni 1 mais un out of memory de mon logiciel de stats

dcvg5k-printer.7z

(558.9 Kio) Téléchargé 147 fois

Carl

[Guillaume]

(supp modo: quote inutile)

1 Milliard et demi! Tu n'y es pas allé avec le dos de la cuillère!
Bon cela semble conclure le sujet!!

[joaopa]

@Merkerror Un petit article sur ton site sur ce point de Basic serait une bonne idée, je pense.
Pour aider les futurs développeurs sur VG5000 en basic !!

[__sam__]

En fait le problème initial ne concerne que le cas RND(1)=1 car le INT() sur VG5k fait un arrondit vers "-infini". Cela peut s'inverser en faisant -INT(-RND(1)*4) qui retournera alors un nombre entre 1 et 4 (inclus tous les deux).

Pour régler le problème définitivement, il faut faire un arrondi à l'entier le plus proche (round). Mais comme tous les basic n'ont pas cette instruction on peut l'émuler à partir de round(x) = int(x+0.5) (toujours avec un int qui arrondit vers -infini). La formule INT(0.5 + RND(1)*4) retournera alors des entiers entre 0 et 4 (inclus tous les deux). Par contre 0 et 4 seront chacun tirés moitié moins que les autres (je vous laisse voir pourquoi ).

Si on tient à l'uniformité des tirages 0 à 4, il faut utiliser la formule INT(RND(1)*5) qui ne produira jamais 5 --étant entendu que RND(1) est toujours strictement plus petit que 1-- et où 0, 1, 2, 3, et 4 auront tous le même poids (5 valeurs en tout).

[Mokona]

Je voulais commencer un petit article sur l''étude de RND, mais cela n'était pas possible sans traiter le format des nombres auparavant (la question que se posait hilde en page 1).

Donc : https://www.triceraprog.fr/vg5000u-trai ... mbres.html

[Guillaume]

D'autant que la fonction RND ne retourne pas toutes les possibilités de nombre dans le format.
Par example 0.000001, 0.000005 ou 0.999985 ne sortiront à aucun tirage. Donc il y a surement des trous partout dans l'interval.
Pour des tirages de nombre dans un petit interval (example INT(RND(1)*4) ) cela n'a aucune incidence.
Mais imaginons une application qui a besoin d'un grand interval de nombre tiré au hasard, cela peut poser des problèmes.
Par exemple une société spatiale tire au hasard parmi les 7 milliards et demi d'humains celui qui partira visiter et poser le pied sur Mars en premier!!
Est-ce que le RND du VG5000 exclu d'ores et déjà un certain nombre de candidat? Moi j'ai le numéro d'humain 4 738 657 812 et peut être celui ci ne peut jamais sortir avec la fonction (RND(1) x 7 500 000 000)!

Voila quelques sujets de recherche possible:
- Comment sont stockés le nombre réels dans le basic du VG5000, quel est donc l'intervalle possible au maximum?
- Est ce que la fonction RND renvoit toutes les possibilités de l'interval? ..XX.XXX.XX.XXX
- A partir de quel interval choisi cela commence à poser de réel problème de répartition de la chance? (par exemple sur un interval choisi de 100 000 avec RND(1)*100000, on a des valeurs qui reviennent significativement plus souvent que d'autres, mais toujours les memes liés à la methode de la fonction RND).
- A partir de quel interval choisi on se retrouve avec des nombres qui ne sorte jamais? (par exemple, nous l'avons vu, avec un interval d'un million ( RND(1)*1000000) nous avons déja des valeurs interdites, ici 1 2 3 4 5 ne sortent jamais à aucun tirage, pareil pour 999982 999983 ...

Et puis enfin, comment fonctionne RND? D'ou vient le facteur hasard (en général du temps d'une horloge). Comment a été écrite la fonction RND?

Pas mal de sujet pour le prochain confinement )

[Mokona]

> - Comment sont stockés le nombre réels dans le basic du VG5000, quel est donc l'intervalle possible au maximum?

La réponse à a première partie de la question est dans mon message au dessus...

> Et puis enfin, comment fonctionne RND? D'ou vient le facteur hasard (en général du temps d'une horloge). Comment a été écrite la fonction RND?

La fonction RND est mon prochain article (c'est déjà décortiqué : à partir du dernier nombre tiré, une multiplication tiré dans une table tournante de 8 facteurs, puis une addition tiré dans une table tournante de 4 entrées, et tous les 171 tirages, la mantisse est perturbée).

Pour une analyse mathématique poussée des propriétés, c'est hors de mon champ. Mais ça m'étonnerait que le générateur du BASIC MS soit de classe cryptographique...

Je n'ai pas vu d'influence d'entropie (horloge ou quoi que ce soit), tous les facteurs sont déterminés (mais les multiplicatifs sans en RAM, donc on peut les changer).

[Guillaume]

Pas de facteur d'entropie, que c'est triste. Cela veut dire que le VG5000 tire toujours les memes numéros dans le même ordre.
Effectivement c'est le cas:
.245121
.305003
.311866
Je ne m'en doutais même pas.
J'ai fais un petit programme pour voir si la modification de la mémoire agissait.
Cela change si on travail avec des variables. Ca décale dans la séquence c'est tout.

Cela veux dire que dans un jeu, les mouvements des ennemis au hasard par exemple, seront toujours les memes.
L'entropie viendra peut-être uniquement du comportement du joueur (de l'humain) qui peut différer d'une partie à l'autre si les variables sont affectées différement et que cela à une incidence sur la séquence de la fonction RND.

[gilles]

Il suffit de tirer des nombre aux hasard pendant qu’on attend que le joueur demarre la partie et ce sera un meilleur « hasard » (je sais, ce n’en est pas vraiment un mais c’est suffisant)

[__sam__]

faire

Code : Tout sélectionner

x = (x*a + b) mod c

est ce qui est appliqué dans les générateurs modulo-congruentiels. C'est un grand classique des générateurs aléatoires. Simples à implementer, on les retrouve partout, en particulier dans l'algorithme RANDU. Très rapide, il a cependant la particularité d'avoir de mauvaise qualités statistiques. Par exemple le bit de poids faible alterne entre 0 et 1 et des correlations linéaires entre valeurs consécutives sont présentes (évidemment). On remarque ces défauts quand on fait un affichage 2D ou 3D de points tirés au hasard (cf viewtopic.php?p=117679#p117679): il apparaît des "lignes" très caractéristiques.


Le basic du VG5k semble contourner ces défauts en faisant varier a et b à chaque itération (c reste constant = 2^16, car le modulo est alors gratuit.) La période de ces constantes est 8 et 4 ce qui semble être une bonne idée pour le rendre moins prédictif. Sauf que si on déroule formellement le générateur sur 8*4=32 étapes (j'ai pas fait le calcul.. peut-être que le PPMC de 8 et 4 suffit), on retombe sur une formule du style x(n+k) = x(n)*A + B pour tout n (un truc linéaire appliqué sur un truc linéaire reste linéaire). Bref c'est toujours un générateur linéaire congruentiel, mais avec d'autres constantes, mais comme le "modulo c" ne change pas, la période finale reste la même et les même défauts statistiques fondamentaux s'y retrouvent. C'est probablement pour ca qu'ils modifient la mantisse de temps en temps pour allonger la période et réduire la visibilité des défauts statistiques.

[Guillaume]

Il suffit de tirer des nombre aux hasard pendant qu’on attend que le joueur demarre la partie et ce sera un meilleur « hasard » (je sais, ce n’en est pas vraiment un mais c’est suffisant)

Oui, simple et bonne idée!

[Guillaume]

faire

Code : Tout sélectionner

x = (x*a + b) mod c

est ce qui est appliqué dans les
...
C'est probablement pour ca qu'ils modifient la mantisse de temps en temps pour allonger la période et réduire la visibilité des défauts statistiques.

Merci _Sam_. Il m'a fallu du temps pour lire ton post. Il me manque des notions pour tout comprendre mais c'est très instructif.

[hlide]

Oh bah ça ressemble très fortement à du IEEE_754 en précision 32-bit mais dans une version antérieure qui n'intègre sans doute pas les notions d'infini ou de NAN ou de nombre dénormalisé, avec le bit de signe plutôt du côté de la mantisse pour pouvoir lire l'exposant en un octet sans décalage (trop gourmand en Z80).

[Carl]

Merci Mokona et Sam pour vos éclaircissements...

Carl

[Mokona]

Voici à présent le déroulé de la routine de génération des nombres aléatoires.

https://www.triceraprog.fr/vg5000u-nomb ... oires.html