subtilité de rand VG5000
Modérateurs : Papy.G, fneck, Carl
-
- Messages : 7924
- Inscription : 18 sept. 2010 12:08
- Localisation : Brest et parfois les Flandres
Re: subtilité de rand VG5000
Ah oui, ca a l'air plus complexe que ce que je décrivais plus haut. J'avoue ne pas comprendre le fait que cela travaille avec des nombres flottants. Est-tu sur qu'en fait ca ne serait pas de l'artithmétique 24 ou 32bits non signée ?
Samuel.
A500 Vampire V2+ ^8^, A1200 (030@50mhz/fpu/64mb/cf 8go),
A500 GVP530(MMU/FPU) h.s., R-Pi, TO9, TO8D, TO8.Démos
A500 Vampire V2+ ^8^, A1200 (030@50mhz/fpu/64mb/cf 8go),
A500 GVP530(MMU/FPU) h.s., R-Pi, TO9, TO8D, TO8.Démos
Re: subtilité de rand VG5000
Partant du principe que la fonction RND du BASIC retourne un nombre nécessairement réel, il n'y a rien d'étonnant à ce qu'ils aient utilisé que des opérations sur des réels. On aurait pu sans doute créer le nombre aléatoire par manipulation des bits de la mantisse mais vu que le Z80 est un très mauvais manipulateur de bits et qu'il n'a pas non plus de multiplication entière dédiée, je doute ce que ce soit mieux : là au moins la fonction RND se sert de fonctions annexes pour faire des calculs même si on pourra redire sur la performance.
-
- Messages : 7924
- Inscription : 18 sept. 2010 12:08
- Localisation : Brest et parfois les Flandres
Re: subtilité de rand VG5000
Je ne suis pas convaincu dans la mesure où la fonction Random.nextFloat() en java se base sur le générateur aléatoire entiers et qu'en C on fait souvent rand()/MAX_RAND pour avoir simplement un truc aléatoire entre 0 et 1 et même drand48() qui est plus performant fait un truc du même style (le générateur rand48() est entier).
En plus au niveau ASM c'est super simple de sortir un entier entre 0 et 1 sans aucun calcul flottant en même sans manipuler les bits: il suffit de tirer au hasard les 23bits de la mantisse, le dernier bit lui aussi au hasard pouvant venir du dernier octet tiré permet de choisir l'exposant non biaisé 0 ou 1 au hasard: 2^0 donnera un nombre entre 0 exclus et 0.5 inclus, alors que 2^1 donnera un entier entre 0.5 exclus et 1 inclus. On a alors une distribution homogène uniforme entre 0 (exclus) et 1 (inclus) en très peu de cycles. Exemple:
Code : Tout sélectionner
; pseudocode vaguement z80
call rnd8
ld (FAC),a ; ecriture poids faible mantisse
call rnd8
ld (FAC+1),a ; ecriture poids milieu mantisse
call rnd8
add $80,a ; mets le MSBit dans la carry
jp c,lbl ; si carry, alors le MSB est à présent à 0.
and a,$7f ; pas de carry, le MSBit était à 0. Je re-passe le MSBit à 0.
lbl:
ld (FAC+2),a ; ecriture poids fort de la mantisse (toujours MSBit=0 ==> nb toujours positif)
sbc a,a ; a=$ff si carry=1, 0 sinon
add a,$81 ; a=$81 ou $80 au hasard
ld (FAC+3),a ; écriture exposant 0 ou 1 au hasard
ret ;on a un nb entre 0 (exclus) et 1 (inclus) dans l'accu flottant (FAC)
; retourne 8 bits au hasard dans l'accu a (seed 16 bits, entropie introduite par le registre "r")
rnd8:
push hl
push de
ld hl,(seed)
ld a,r
ld d,a
ld e,(hl)
add hl,de
add a,l
xor h
ld (seed),hl
pop de
pop hl
ret
[code]
Samuel.
A500 Vampire V2+ ^8^, A1200 (030@50mhz/fpu/64mb/cf 8go),
A500 GVP530(MMU/FPU) h.s., R-Pi, TO9, TO8D, TO8.Démos
A500 Vampire V2+ ^8^, A1200 (030@50mhz/fpu/64mb/cf 8go),
A500 GVP530(MMU/FPU) h.s., R-Pi, TO9, TO8D, TO8.Démos
Re: subtilité de rand VG5000
@__sam__ en quelle année le vg5000 ? et le JAVA ? beaucoup de chose ont évolué entre les deux [dates] au niveau algorithmique. Ce que je dis, c'est que les concepteurs du BASIC n'ont pas nécessairement fait la recherche du meilleur algorithme sur ce point-là.
Dernière modification par hlide le 11 mai 2020 10:38, modifié 1 fois.
Re: subtilité de rand VG5000
Et tu triches avec "LD A,R". C'est sûr que ça aide à créer un peu d'aléatoire. ^^
-
- Messages : 7924
- Inscription : 18 sept. 2010 12:08
- Localisation : Brest et parfois les Flandres
Re: subtilité de rand VG5000
On se fiche du langage quand on concoit un algorithme (ce sont des maths), java/c/asm: même combat. Tous calculent random/random_max. En outre le code ASM donné (qui n'est rien d'autre que rand24()/2^24) montre qu'il était parfaitement possible d'avoir un algo rapide à partir d'un générateur entier même à l'époque. Par contre oui au niveau des algos, à l'époque on ne connaissait que les générateurs linéaires congruentiels pour ainsi dire, et ca n'est que plus récemment (~2000) que Marsaglia a sorti pleins d'algos à la fois meilleurs statistiquement, plus rapides, et pour certains nettement mieux adaptés aux 8bits.
Oui le LD A,R est une spécificité Z80 pour augmenter l'entropie, mais on peut s'en passer. N'importe quel générateur d'octet aléatoire de longue période (et première avec trois) convient.
Oui le LD A,R est une spécificité Z80 pour augmenter l'entropie, mais on peut s'en passer. N'importe quel générateur d'octet aléatoire de longue période (et première avec trois) convient.
Samuel.
A500 Vampire V2+ ^8^, A1200 (030@50mhz/fpu/64mb/cf 8go),
A500 GVP530(MMU/FPU) h.s., R-Pi, TO9, TO8D, TO8.Démos
A500 Vampire V2+ ^8^, A1200 (030@50mhz/fpu/64mb/cf 8go),
A500 GVP530(MMU/FPU) h.s., R-Pi, TO9, TO8D, TO8.Démos
Re: subtilité de rand VG5000
Ça dépend si l'on souhaite la même séquence pseudo-aléatoire à partir du même "seed". En ajoutant "LD A,R", on s'interdit de le faire, c'est que j'entendais par "un peu d'aléatoire". Je pensais que le BASIC permettait de définir un nouveau "seed" pour pouvoir reproduire la même séquence mais apparemment je dois confondre avec les fonctions C standard (rand() et srand(seed)). C'est souvent une option pour créer les mêmes événements par tableau de jeu par exemple.
Et merci pour les liens, en particulier le dernier qui me sera très certainement utile.
Et merci pour les liens, en particulier le dernier qui me sera très certainement utile.
- Mokona
- Messages : 1040
- Inscription : 17 déc. 2016 22:01
- Localisation : Nord Est des Yvelines
- Contact :
Re: subtilité de rand VG5000
Le BASIC premet en effet de donner une seed pour retrouver la même séquence (argument négatif).
C'est une propriété super importante du générateur dans pas mal de domaines (et très utilisé en jeux vidéo), et je pense que dans un algo plus optimisé, ça doit se garder. Il peut y avoir une commande annexe pour sortir une seed "imprévisible" à côté.
En tout cas, il y a effectivement moyen de faire plus concis que la routine de base du Microsoft BASIC. Mais en effet, le sujet a évolué depuis ce temps là...
Exemple dans z88dk : https://github.com/z88dk/z88dk/tree/mas ... z80/random
C'est une propriété super importante du générateur dans pas mal de domaines (et très utilisé en jeux vidéo), et je pense que dans un algo plus optimisé, ça doit se garder. Il peut y avoir une commande annexe pour sortir une seed "imprévisible" à côté.
En tout cas, il y a effectivement moyen de faire plus concis que la routine de base du Microsoft BASIC. Mais en effet, le sujet a évolué depuis ce temps là...
Exemple dans z88dk : https://github.com/z88dk/z88dk/tree/mas ... z80/random
-
- Messages : 7924
- Inscription : 18 sept. 2010 12:08
- Localisation : Brest et parfois les Flandres
Re: subtilité de rand VG5000
J'ai pas l'impression que c'est ce que dit la doc de Carl, mais elle a peut-être une erreur.
Samuel.
A500 Vampire V2+ ^8^, A1200 (030@50mhz/fpu/64mb/cf 8go),
A500 GVP530(MMU/FPU) h.s., R-Pi, TO9, TO8D, TO8.Démos
A500 Vampire V2+ ^8^, A1200 (030@50mhz/fpu/64mb/cf 8go),
A500 GVP530(MMU/FPU) h.s., R-Pi, TO9, TO8D, TO8.Démos
- Mokona
- Messages : 1040
- Inscription : 17 déc. 2016 22:01
- Localisation : Nord Est des Yvelines
- Contact :
Re: subtilité de rand VG5000
Toute cette discussion est partie du fait que le manuel n'était pas clair
Mais en plus, il est faux.
Mais en plus, il est faux.
- Mokona
- Messages : 1040
- Inscription : 17 déc. 2016 22:01
- Localisation : Nord Est des Yvelines
- Contact :
Re: subtilité de rand VG5000
Petite session à reproduire sur le matériel :
Code : Tout sélectionner
?RND(1)
.245121
?RND(0)
.245121
?RND(1)
.30503
?RND(0)
.30503
?RND(-0.1234)
.424713
?RND(0)
.424713
?RND(1)
.76887
?RND(-0.1234)
.424713
-
- Messages : 7924
- Inscription : 18 sept. 2010 12:08
- Localisation : Brest et parfois les Flandres
Re: subtilité de rand VG5000
ok donc 3 cas: arg<0, arg>0 et arg=0. Effectivement, c'est subtile.
Samuel.
A500 Vampire V2+ ^8^, A1200 (030@50mhz/fpu/64mb/cf 8go),
A500 GVP530(MMU/FPU) h.s., R-Pi, TO9, TO8D, TO8.Démos
A500 Vampire V2+ ^8^, A1200 (030@50mhz/fpu/64mb/cf 8go),
A500 GVP530(MMU/FPU) h.s., R-Pi, TO9, TO8D, TO8.Démos