subtilité de rand VG5000

Cette catégorie traite de développements récents destinés à 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

__sam__
Messages : 7924
Inscription : 18 sept. 2010 12:08
Localisation : Brest et parfois les Flandres

Re: subtilité de rand VG5000

Message par __sam__ »

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
Avatar de l’utilisateur
hlide
Messages : 3470
Inscription : 29 nov. 2017 10:23

Re: subtilité de rand VG5000

Message par hlide »

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.
__sam__
Messages : 7924
Inscription : 18 sept. 2010 12:08
Localisation : Brest et parfois les Flandres

Re: subtilité de rand VG5000

Message par __sam__ »

hlide a écrit : 11 mai 2020 00:41 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.
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
Avatar de l’utilisateur
hlide
Messages : 3470
Inscription : 29 nov. 2017 10:23

Re: subtilité de rand VG5000

Message par hlide »

@__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.
Avatar de l’utilisateur
hlide
Messages : 3470
Inscription : 29 nov. 2017 10:23

Re: subtilité de rand VG5000

Message par hlide »

Et tu triches avec "LD A,R". C'est sûr que ça aide à créer un peu d'aléatoire. ^^
__sam__
Messages : 7924
Inscription : 18 sept. 2010 12:08
Localisation : Brest et parfois les Flandres

Re: subtilité de rand VG5000

Message par __sam__ »

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.
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
Avatar de l’utilisateur
hlide
Messages : 3470
Inscription : 29 nov. 2017 10:23

Re: subtilité de rand VG5000

Message par hlide »

Ç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.
Avatar de l’utilisateur
Mokona
Messages : 1040
Inscription : 17 déc. 2016 22:01
Localisation : Nord Est des Yvelines
Contact :

Re: subtilité de rand VG5000

Message par Mokona »

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
__sam__
Messages : 7924
Inscription : 18 sept. 2010 12:08
Localisation : Brest et parfois les Flandres

Re: subtilité de rand VG5000

Message par __sam__ »

Mokona a écrit : 11 mai 2020 11:46 Le BASIC premet en effet de donner une seed pour retrouver la même séquence (argument négatif).
J'ai pas l'impression que c'est ce que dit la doc de Carl, mais elle a peut-être une erreur.
Image
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
Avatar de l’utilisateur
Mokona
Messages : 1040
Inscription : 17 déc. 2016 22:01
Localisation : Nord Est des Yvelines
Contact :

Re: subtilité de rand VG5000

Message par Mokona »

Toute cette discussion est partie du fait que le manuel n'était pas clair :)

Mais en plus, il est faux.
Avatar de l’utilisateur
Mokona
Messages : 1040
Inscription : 17 déc. 2016 22:01
Localisation : Nord Est des Yvelines
Contact :

Re: subtilité de rand VG5000

Message par Mokona »

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
__sam__
Messages : 7924
Inscription : 18 sept. 2010 12:08
Localisation : Brest et parfois les Flandres

Re: subtilité de rand VG5000

Message par __sam__ »

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
Répondre