subtilité de rand VG5000

Cette catégorie traite de développements récents pour nos vieilles machines, applications, jeux ou démos... Amis programmeurs, c'est ici que vous pourrez enfin devenir célèbres!

Modérateurs : Papy.G, fneck, Carl

Avatar du membre
Carl
Modérateur
Messages : 11129
Enregistré le : 08 avr. 2007 13:21
Localisation : http://www.doledujura.fr
Contact :

Re: subtilité de rand VG5000

Message par Carl » 08 mai 2020 09:40

environ 1.5 milliard de tirages....pas de zéro ni 1 mais un out of memory de mon logiciel de stats :wink:
dcvg5k-printer.7z
(558.9 Kio) Téléchargé 7 fois
Carl

Guillaume
Messages : 45
Enregistré le : 26 avr. 2020 15:24
Localisation : Nice

Re: subtilité de rand VG5000

Message par Guillaume » 08 mai 2020 10:48

Carl a écrit :
08 mai 2020 09:40
(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
Messages : 500
Enregistré le : 14 sept. 2013 12:17

Re: subtilité de rand VG5000

Message par joaopa » 08 mai 2020 22:26

@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__
Messages : 5161
Enregistré le : 18 sept. 2010 12:08
Localisation : Brest et parfois les Flandres

Re: subtilité de rand VG5000

Message par __sam__ » 08 mai 2020 23:50

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).
Samuel.
A500 Vampire V2+ ^8^, A1200(030@50mhz/fpu/64mb/cf 8go),
GVP530 (MMU/FPU) h.s., R-Pi, TO9, TO8D, TO8.

Avatar du membre
Mokona
Messages : 515
Enregistré le : 17 déc. 2016 22:01
Localisation : Nord Est des Yvelines
Contact :

Re: subtilité de rand VG5000

Message par Mokona » 09 mai 2020 12:34

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
Messages : 45
Enregistré le : 26 avr. 2020 15:24
Localisation : Nice

Re: subtilité de rand VG5000

Message par Guillaume » 09 mai 2020 13:37

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 :-))

Avatar du membre
Mokona
Messages : 515
Enregistré le : 17 déc. 2016 22:01
Localisation : Nord Est des Yvelines
Contact :

Re: subtilité de rand VG5000

Message par Mokona » 09 mai 2020 13:57

> - 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
Messages : 45
Enregistré le : 26 avr. 2020 15:24
Localisation : Nice

Re: subtilité de rand VG5000

Message par Guillaume » 09 mai 2020 14:53

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.

Avatar du membre
gilles
Messages : 2066
Enregistré le : 07 août 2008 13:44
Localisation : Nantes
Contact :

Re: subtilité de rand VG5000

Message par gilles » 09 mai 2020 15:02

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__
Messages : 5161
Enregistré le : 18 sept. 2010 12:08
Localisation : Brest et parfois les Flandres

Re: subtilité de rand VG5000

Message par __sam__ » 09 mai 2020 15:36

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.
Image

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.
Samuel.
A500 Vampire V2+ ^8^, A1200(030@50mhz/fpu/64mb/cf 8go),
GVP530 (MMU/FPU) h.s., R-Pi, TO9, TO8D, TO8.

Guillaume
Messages : 45
Enregistré le : 26 avr. 2020 15:24
Localisation : Nice

Re: subtilité de rand VG5000

Message par Guillaume » 09 mai 2020 15:51

gilles a écrit :
09 mai 2020 15:02
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
Messages : 45
Enregistré le : 26 avr. 2020 15:24
Localisation : Nice

Re: subtilité de rand VG5000

Message par Guillaume » 09 mai 2020 15:56

__sam__ a écrit :
09 mai 2020 15:36
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
Messages : 1601
Enregistré le : 29 nov. 2017 10:23

Re: subtilité de rand VG5000

Message par hlide » 09 mai 2020 17:24

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).

Avatar du membre
Carl
Modérateur
Messages : 11129
Enregistré le : 08 avr. 2007 13:21
Localisation : http://www.doledujura.fr
Contact :

Re: subtilité de rand VG5000

Message par Carl » 09 mai 2020 17:32

Merci Mokona et Sam pour vos éclaircissements...

Carl

Avatar du membre
Mokona
Messages : 515
Enregistré le : 17 déc. 2016 22:01
Localisation : Nord Est des Yvelines
Contact :

Re: subtilité de rand VG5000

Message par Mokona » 10 mai 2020 22:43

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

Répondre