[C] Problème routine génération nombres aléatoires

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 de l’utilisateur
Falkor
Messages : 1701
Inscription : 28 juin 2010 12:09
Localisation : Cluny, Saône et Loire

[C] Problème routine génération nombres aléatoires

Message par Falkor »

Salut à tous,

Petite question... Toujours en parallèle de mes développements en C sur la Vectrex, j'aurais besoin de vos lumières concernant la génération de nombres pseudo-aléatoires.

J'ai à ma disposition deux fonctions dans la ROM :
// The Vectrex uses three bytes for the random seed.
void random_seed(uint8_t seed1, uint8_t seed2, uint8_t seed3);

// Produce a random value using the BIOS Random function.
int8_t random();
Bon déjà pas de bol, le simple fait d'appeler la fonction random_seed fait qu'ensuite tout appel à la fonction random() renvoie toujours le même nombre :roll: . On arrive à avoir des résultats différents en ne l'appelant pas. (bon why not...). Bref.

Mon souci est que la fonction random() me renvoie un entier signé 8 bits, donc entre -128 et +127, et que j'aimerai pouvoir "affiner" la plage de rendu des valeurs pour obtenir des entiers signés entre A et B. (toujours dans la plage entier signé 8 bits).

Seulement voilà j'aimerai savoir comment faire ça proprement. Impossible de passer en flottant sur cette machine (le compilateur ne les gère pas) et passer sur des entiers 16 bits est assez lent (et me semble un peu trop surdimensionné).

Pour me dépanner j'ai fait une table avec 255 entrées, mais c'est lourd en ROM et pas très propre au final.

Les solutions trouvées lors de mes recherches faisaient quasi toutes appel à des flottants, genre :

Code : Tout sélectionner

rand() % (max_number + 1 - minimum_number) + minimum_number
Il semble en plus que le générateur de nombres aléatoires du bios de la Vectrex ne soit pas si bon que ça.

Je peux éventuellement repartir sur des algos indépendants de toute bibliothèque, mais rien trouvé pour l'instant...

Des idées ?

Merci !

(PS : je ne sais pas si je suis dans le bon topic... N'hésitez pas à déplacer au besoin)
__sam__
Messages : 7923
Inscription : 18 sept. 2010 12:08
Localisation : Brest et parfois les Flandres

Re: [C] Problème routine génération nombres aléatoires

Message par __sam__ »

Falkor a écrit : 21 juil. 2021 11:07 Bon déjà pas de bol, le simple fait d'appeler la fonction random_seed fait qu'ensuite tout appel à la fonction random() renvoie toujours le même nombre :roll: . On arrive à avoir des résultats différents en ne l'appelant pas. (bon why not...). Bref.
C'est probablement que tu n'as pas eu de chance dans le choix de tes graines seed1..3 et es tombé sur un point fixe. Par hasard tu n'aurais pas passé des zéros là dedans.
Mon souci est que la fonction random() me renvoie un entier signé 8 bits, donc entre -128 et +127, et que j'aimerai pouvoir "affiner" la plage de rendu des valeurs pour obtenir des entiers signés entre A et B. (toujours dans la plage entier signé 8 bits).
C'est classique. A et B sont inclus je présume ?
Les solutions trouvées lors de mes recherches faisaient quasi toutes appel à des flottants, genre :

Code : Tout sélectionner

rand() % (max_number + 1 - minimum_number) + minimum_number
Ca n'est pas du flottant mais du modulo entier qui est une opération couteuse qui en plus apporte un léger biais dans la mesure où suivant les valeurs de primalité entre (B-A) et 256, le modulo va en favoriser certains.

Une autre façon de faire, plus homogène est en fait de tirer un nombre au pif entre 0.0 et 1.0 de multiplier par (B-A) et ajouter A: A + (B-A)*u() avec un un flottant aléatoire entre 0 et 1.

Oui mais c'est du flottant ça et il n'y en a pas sur Vectrex (ou alors c'est très lent). C'est pas grave: la solution est de passer par des nombres en point fixes. On remplace u() par un appel à urand()/255 où urand() retourne un nombre entier entre 0 et 255 (urand() = rand()+128 mais (unsigned)rand() convient aussi). La formule devient: A + ((B-A)*urand())/255 et là (B-A) et urand() sont tout deux des entiers 8 bits. C'est un produit de deux 8 bits ce que le mc6809 sait très bien faire.

Oui mais il reste la division entière par 255. C'est vrai. C'est une opération couteuse... mais on remarque que grosso-modo diviser en entier par 255 ne donne pas un résultat très loin d'une division en entier par 256.. En effet, au plus on aura B-A=255 et urand()=255, soit un produit n de 65025. Or n/255 = 255 et (n + n/256)/256=255 aussi

Code : Tout sélectionner

* Divise D (255*255 max) par 255
DIV255
	STA	,-S
	CLR	,-S
	ADDD	,S++
	TFR	A,B
	CLRA
	RTS
Au final la routine pour avoir un nombre aléatoire entre A et B (tous les deux inclus) devient

Code : Tout sélectionner

* Nombre aléatoire entre valeur registre A et valeur de registre B
randAB:
	STA 	,-S
	SUBB	,S	
	STB	,-S	; on stocke B-A
	JSR	rand	; on traitera le retour sur B comme un entier non signé 
	LDA	,S	; A = "B-A", B = urand()
	MUL		; D = (B-A)*urand()
	STA	,S
	CLR	,-S
	ADDD	,S++	; D + D/256
	TFR	A,B
	CLRA		; D = (D + D/256)/256
	ADDB	,S+	; D = A + (B-A)*urand()/255
	RTS
Il semble en plus que le générateur de nombres aléatoires du bios de la Vectrex ne soit pas si bon que ça.
C'est possible. Perso j'ai trouvé que les générateurs "mutliply with carry de Marsaglia sont petits et très rapides sur le 6809.

Code : Tout sélectionner

seed0	FCB	0	; important : toujours garder à 0 car on fait un ADDD
seed1	FCB	123
seed2	FCB	234
mwcRand8:
	LDA	#249	; entier a qui a la plus longe période (31 871) pour du 8 bits
	LDB	seed2	; b=x (sortie précédente)
	MUL		; D=ax
	ADDD	seed0	; D=ax+c
	STA	seed1	; c=int((ax+c)/256) (*)
	STB	seed2	; x=dernier résultat (*)
	CLRA		; pour avoir un D entre 0 et 255 (optionnel car souvent on trash A juste après)
	RTS
Attention à ne jamais avoir seed1 et seed2 à 0 car là le générateur ne produit que des 0 (point fixe).
__
(*) NOTE: les STA seed1/STB seed2 peuvent être combinés en un seul STD seed1, mais ici je veux faire simple et compréhensible.

Après il y a les XORSHIFT qui sont aussi rapides et facile à implémenter sur 68000 (ou 8 bits si on est familier avec l'arithmétique multi-précision) et ont une super longue période et passent pas mal de tests statistiques.

PS: code source non testé et donné à titre indicatif.
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
Falkor
Messages : 1701
Inscription : 28 juin 2010 12:09
Localisation : Cluny, Saône et Loire

Re: [C] Problème routine génération nombres aléatoires

Message par Falkor »

Merci de ton retour très complet !
__sam__ a écrit : 21 juil. 2021 12:31 Par hasard tu n'aurais pas passé des zéros là dedans.
Bin non justement... J'ai testé avec différents triplets de valeurs (toutes différentes de 0), toujours pareil. (Bon le nombre "unique" changeait bien à chaque changement de seed...). Et j'ai vu dans un exemple que le gars utilisait direct random() sans initialiser, du coup j'ai fait pareil.
__sam__ a écrit : 21 juil. 2021 12:31 C'est classique. A et B sont inclus je présume ?
Oui tout à fait ! -127 < A < B < 127
__sam__ a écrit : 21 juil. 2021 12:31 Ca n'est pas du flottant mais du modulo entier qui est une opération couteuse qui en plus apporte un léger biais dans la mesure où suivant les valeurs de primalité entre (B-A) et 256, le modulo va en favoriser certains.

Une autre façon de faire, plus homogène est en fait de tirer un nombre au pif entre 0.0 et 1.0 de multiplier par (B-A) et ajouter A: A + (B-A)*u() avec un un flottant aléatoire entre 0 et 1.
Oui pardon l'exemple cité ne correspondait pas. Oui ce que j'ai appelé par défaut "flottant" c'est bien de multiplier par un flottant valant entre 0 et 1.
__sam__ a écrit : 21 juil. 2021 12:31 Oui mais c'est du flottant ça et il n'y en a pas sur Vectrex (ou alors c'est très lent). C'est pas grave: la solution est de passer par des nombres en point fixes. On remplace u() par un appel à urand()/255 où urand() retourne un nombre entier entre 0 et 255 (urand() = rand()+128 mais (unsigned)rand() convient aussi). La formule devient: A + ((B-A)*urand())/255 et là (B-A) et urand() sont tout deux des entiers 8 bits. C'est un produit de deux 8 bits ce que le mc6809 sait très bien faire.

Oui mais il reste la division entière par 255. C'est vrai. C'est une opération couteuse... mais on remarque que grosso-modo diviser en entier par 255 ne donne pas un résultat très loin d'une division en entier par 256.. En effet, au plus on aura B-A=255 et urand()=255, soit un produit n de 65025. Or n/255 = 255 et (n + n/256)/256=255 aussi
Je vais essayer comme ça. Après je ne suis pas spécialement contraint par le temps dans cette application précise, au sens ou je n'ai que 3 nombres aléatoires à calculer toutes les 4 ou 5 secondes (reset de la position d'obstables).

J'ai vu pas mal d'exemples donnés en assembleur suivant différents algos. Je n'ai pas encore trop testé le coup d'inclure des routines assembleur dans le code C ( asm {...}), il faudra sans doute que j'y vienne.
__sam__
Messages : 7923
Inscription : 18 sept. 2010 12:08
Localisation : Brest et parfois les Flandres

Re: [C] Problème routine génération nombres aléatoires

Message par __sam__ »

A titre d'exemple j'ai retrouvé l'un des générateurs XOR-SHIFT sur 68000:

Code : Tout sélectionner

* unsigned int Q_rand(void) {
*	unsigned int x = Q_randseed;
*	x ^= x << 13;
*	x ^= x >> 17;
*	x ^= x << 5;
*	return Q_randseed = x;	
* }
		xref	_Q_randseed
		xdef	_Q_rand
_Q_rand
		move.l	_Q_randseed,d0
		move.l	d0,d1
		lsl.l	#8,d1
		lsl.l	#5,d1
		eor.l	d1,d0
		move.l	d0,d1
		swap	d1
		lsr.w	#1,d1
		eor.w	d1,d0
		move.l	d0,d1
		lsl.l	#5,d1
		eor.l	d1,d0
		move.l	d0,_Q_randseed
		RTS
Il a une graine Q_seed de 32bits et génère 32bits aléatoires. Je pense qu'une adaptation 6809 serait un bon exercice, mais il y a une version avec des décalages plus adaptés aux 8/16 bits qui ne savent décaler l'accu que d'un bit: http://www.retroprogramming.com/2017/07 ... n-z80.html (ou https://codebase64.org/doku.php?id=base ... _generator)

Code : Tout sélectionner

/* 16-bit xorshift PRNG */

unsigned xs = 1;

unsigned xorshift( )
{
    xs ^= xs << 7;
    xs ^= xs >> 9;
    xs ^= xs << 8;
    return xs;
}
que je coderais bien avec du code auto-modifiable car on a pas d'orpérations logique/arithmétique de registre à registre:

Code : Tout sélectionner

  LDD   #1	; seed ne doit pas être nul
seed set *-2
  LSRA
  RORB
  EORB  <seed,PCR
  STB   <tmp1,PCR
  RORB
  EORB  <seed+1,PCR
  STB   <seed+1,PCR
  EORB  #0
tmp1 set *-1
  STB   <seed,PCR
qui génère chacun des 65535 nombres 16bits non nuls une fois et une fois seulement dans un ordre aléatoire assez robuste en 36 cycles sur 23 octets (31 cycles sur 18 octets si on mets tout en direct-page).

A noter: j'aime aussi bien cette version qui retourne le nombre aléatoire directement dans D (c'est pratique)

Code : Tout sélectionner

   1136  3     B3A8 CC   0001       LDD   #1
   1137                  B3A9     seed set *-2
   1138  2     B3AB 44              LSRA
   1139  2     B3AC 56              RORB
   1140  4+1   B3AD E8   8C F9      EORB  <seed,PCR
   1141  4+1   B3B0 E7   8C F6      STB   <seed,PCR
   1142  2     B3B3 56              RORB
   1143  4+1   B3B4 E8   8C F3      EORB  <seed+1,PCR
   1144  6     B3B7 1F   98         TFR   B,A
   1145  4+1   B3B9 A8   8C ED      EORA  <seed,PCR
   1146  5+1   B3BC ED   8C EA      STD   <seed,PCR
----------------
41 cycle(s)
23 byte(s)
----------------
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
Falkor
Messages : 1701
Inscription : 28 juin 2010 12:09
Localisation : Cluny, Saône et Loire

Re: [C] Problème routine génération nombres aléatoires

Message par Falkor »

__sam__ a écrit : 22 juil. 2021 08:51

Code : Tout sélectionner

/* 16-bit xorshift PRNG */

unsigned xs = 1;

unsigned xorshift( )
{
    xs ^= xs << 7;
    xs ^= xs >> 9;
    xs ^= xs << 8;
    return xs;
}
Super merci je vais essayer avec ça en adaptant sur 8 bits (ou tel quel en faisant un cast...).

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

Re: [C] Problème routine génération nombres aléatoires

Message par __sam__ »

Il y a le code ASM juste en dessous :)
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