Citation Envoyé par j.p.mignot
Tout à fait d'accord que l'algorithme ci-dessus est en O(ln(n)) et celui que j'ai donné est en O(n).
J'ai juste corrigé (et enlevé la récursion) un algo donné avant.

Toutefois pour une puissance de 10 on va gagner environ un facteur 3 sur les itérations mais avec un test 'if' et un 'modulo'. Est ont- vraiment encore gagnant ?
Question intéressante... le modulo 2, s'il pose problème il vaut mieux changer de compilateur si on est intéressé par les performances: c'est tester le bit le moins significatif.

Le saut est peut-être plus génant surtout qu'il ne peut pas être prédit, mais les multiplications restent quand même coûteuse, surtout quand on ne peut pas les pipeliner avec d'autres choses comme ici; il faudrait mesurer mais je crains que ça dépendent fortement du compilateur et de la cible: correctement schedulé, la deuxième multiplication de la boucle peut être faite avant et son délai masquer le saut ou l'autre multiplicitation. Naturellement, si on est dans un cas où la multiplication est logicielle la question ne se pose pas. On sort de toute manière de l'algorithmique.