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.
Connexion
M’enregistrer
FAQ
Rechercher
Tu fais presque du multi-threading!