Logicielsmoto.com

Nous sommes le 19 Mar 2024, 12:45

Heures au format UTC + 1 heure




Poster un nouveau sujet Répondre au sujet  [ 6 messages ] 
Auteur Message
 Sujet du message: Générateurs aléatoires
MessagePosté: 03 Mai 2019, 07:17 
Hors ligne

Inscription: 21 Aoû 2006, 09:06
Messages: 1800
Localisation: Brest
Pour un projet, je cherchais un générateur aléatoire suffisamment correct et rapide. Dans les années 70-80 on utilisait les générateurs concurrentiels linéaires dont on savait qu'ils étaient pas super bon statistiquement mais pas mal rapides. On les retrouve dans les bibliothèques C, Pascal, Forth et même dans le Basic de l'époque (je pense que le basic Thomson fait à partir des sources Microsoft en utilise un aussi).

Vers 2003, George Marsaglia a publié une nouvelle classe de générateurs appelés les XorShift. Ils n'utilisent que des décalages et des Xor et sont donc particulièrement rapides. Hélas les exemples donnés concernent surtout les générateurs pour 32bits ou plus. Rien pour les 8bits?

Et bien si. J'ai trouvé une page sur un générateur XorShift 16bits pour Z80.
Code:
/* 16-bit xorshift PRNG */

unsigned xs = 1;

unsigned xorshift( )
{
    xs ^= xs << 7;
    xs ^= xs >> 9;
    xs ^= xs << 8;
    return xs;
}

Le code Z80 est d'après l'auteur super efficace: 86 cycles. Oui c'est très rapide, et même plus rapide que les modulo-concurrentiels dont l'étape de multiplication est assez coûteuse sur Z80.

Il serait bien d'avoir une version 6809 de cet algorithme, et c'est ce que je propose ici:
Code:
SEED set  *+1
    ldd   #1          ; 3
*
* xs ^= xs << 7
*
    lsra              ; 2
    rorb              ; 2
    eorb  <SEED,pcr   ; 5
    stb   <TMP,pcr    ; 5
*
* xs ^= xs >> 9
*
* tricky part: put carry back in hi(xs>>9) so that it is
* same as if it was introduced in lo(xs) above.
*
    rorb              ; 2
    eorb  <SEED+1,pcr ; 5
*
* xs ^= xs << 8;
*
    tfr   b,a         ; 6
TMP set   *+1
    eora  #0          ; 2
    std   <SEED,pcr   ; 6

Ca nous fait l'algo en 38cycles, a priori plus rapide que Z80.... sauf que le Z80 du ZXSpectrum marche à 4mhz ce qui lui fait l'algo à 22µs. On est donc 2x plus lent. Ce qui nous tue ce sont les accès mémoires et les TFR (6 cycles pour travailler de registre à registre... misère!)

Je ne vois pas comment gagner des cycles, mais si quelqu'un peut faire mieux, je l'encourage à poster ici sa version histoire d'en faire profiter tout le monde :)

Mais bon 38µs c'est quand même pas mal rapide tout compte fait. C'est même plus rapide que la multiplication 16bits x 16bits d'un modulo-concurrentiel sur 6809 qui comptera au moins 4 MULs à 11 cycles chacun.

_________________
Good morning, that's a nice Tnetennba


Dernière édition par Samuel Devulder le 03 Mai 2019, 10:00, édité 3 fois.

Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Générateurs aléatoires
MessagePosté: 03 Mai 2019, 08:48 
Hors ligne

Inscription: 27 Juin 2006, 19:44
Messages: 1058
Localisation: France (24)
C'est déjà très optimisé. Si on pouvait se dispenser du "STB <TMP,PCR", ce serait parfaitement propre.

_________________
Marche a suivre pour s'inscrire sur ce forum
Do not forget to contact one of the administrators to validate your registration.
Le site des démos de Puls
L'émulateur Teo


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Générateurs aléatoires
MessagePosté: 03 Mai 2019, 09:26 
Hors ligne

Inscription: 21 Aoû 2006, 09:06
Messages: 1800
Localisation: Brest
On peut passer par la pile ou des variables extérieures au code. C'est plus propre... mais plus lent aussi.

_________________
Good morning, that's a nice Tnetennba


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Générateurs aléatoires
MessagePosté: 03 Mai 2019, 09:29 
Hors ligne

Inscription: 27 Juin 2006, 19:44
Messages: 1058
Localisation: France (24)
Oui, bien sûr, sans perdre de cycles ;)

_________________
Marche a suivre pour s'inscrire sur ce forum
Do not forget to contact one of the administrators to validate your registration.
Le site des démos de Puls
L'émulateur Teo


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Générateurs aléatoires
MessagePosté: 03 Mai 2019, 09:29 
Hors ligne

Inscription: 27 Juin 2006, 19:44
Messages: 1058
Localisation: France (24)
Déjà, il me semble que l'astuce pour récupérer le bit de poids faible du décalage par 7 pour le décalage par 9 est totalement incompressible :good: Tu fais presque du multi-threading!

_________________
Marche a suivre pour s'inscrire sur ce forum
Do not forget to contact one of the administrators to validate your registration.
Le site des démos de Puls
L'émulateur Teo


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Générateurs aléatoires
MessagePosté: 03 Mai 2019, 09:58 
Hors ligne

Inscription: 27 Juin 2006, 19:44
Messages: 1058
Localisation: France (24)
En fait, les lignes suivantes ne peuvent pas être contournées :
Code:
SEED set  *+1
    ldd   #1          ; 3
    ....
    lsra              ; 2
    rorb              ; 2
    eorb  <SEED,pcr   ; 5
    ....
    rorb              ; 2
    eorb  <SEED+1,pcr ;
    ....
    std   <SEED,pcr   ; 6

... parce qu'il faut quand même faire les calculs.
Les autres pèchent un peu plus. Mais ce sera difficile de faire mieux.

_________________
Marche a suivre pour s'inscrire sur ce forum
Do not forget to contact one of the administrators to validate your registration.
Le site des démos de Puls
L'émulateur Teo


Haut
 Profil  
Répondre en citant le message  
Afficher les messages postés depuis:  Trier par  
Poster un nouveau sujet Répondre au sujet  [ 6 messages ] 

Heures au format UTC + 1 heure


Qui est en ligne

Utilisateurs parcourant ce forum: Aucun utilisateur enregistré et 7 invités


Vous ne pouvez pas poster de nouveaux sujets
Vous ne pouvez pas répondre aux sujets
Vous ne pouvez pas éditer vos messages
Vous ne pouvez pas supprimer vos messages
Vous ne pouvez pas joindre des fichiers

Rechercher:
Aller à:  
cron
Développé par phpBB® Forum Software © phpBB Group
Traduction par phpBB-fr.com