Logicielsmoto.com
http://www.logicielsmoto.com/phpBB/

Générateurs aléatoires
http://www.logicielsmoto.com/phpBB/viewtopic.php?f=3&t=601
Page 1 sur 1

Auteur:  Samuel Devulder [ 03 Mai 2019, 07:17 ]
Sujet du message:  Générateurs aléatoires

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.

Auteur:  Prehisto [ 03 Mai 2019, 08:48 ]
Sujet du message:  Re: Générateurs aléatoires

C'est déjà très optimisé. Si on pouvait se dispenser du "STB <TMP,PCR", ce serait parfaitement propre.

Auteur:  Samuel Devulder [ 03 Mai 2019, 09:26 ]
Sujet du message:  Re: Générateurs aléatoires

On peut passer par la pile ou des variables extérieures au code. C'est plus propre... mais plus lent aussi.

Auteur:  Prehisto [ 03 Mai 2019, 09:29 ]
Sujet du message:  Re: Générateurs aléatoires

Oui, bien sûr, sans perdre de cycles ;)

Auteur:  Prehisto [ 03 Mai 2019, 09:29 ]
Sujet du message:  Re: Générateurs aléatoires

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!

Auteur:  Prehisto [ 03 Mai 2019, 09:58 ]
Sujet du message:  Re: Générateurs aléatoires

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.

Page 1 sur 1 Heures au format UTC + 1 heure
Powered by phpBB® Forum Software © phpBB Group
https://www.phpbb.com/