Logicielsmoto.com http://logicielsmoto.com/phpBB/ |
|
Générateurs aléatoires http://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 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/ |