Y a-t-il un algorithme rapide, similaire à la puissance de 2, qui peut être utilisé avec 3, I.e. N% 3. Peut-être quelque chose qui utilise le fait que si la somme de chiffres est divisible par trois, le nombre est également divisible.
Cela conduit à une question suivante. Quel est le moyen rapide d'ajouter des chiffres dans un numéro? C'est à dire. 37 -> 3 +7 -> 10 Je cherche quelque chose qui n'a pas de conditionnel que ceux-ci ont tendance à inhiber la vectorisation
merci
3 Réponses :
Vous n'êtes pas sûr de votre première question, mais pour votre seconde, vous pouvez profiter de l'opérateur ceci fonctionne car % et de la division entier: 12345% 10 = 5 , 12345/10 = 1234 et continuez jusqu'à ce que num == 0
Oui, c'est cette solution évidente. Cependant, la division et le modulo sont des opérations très coûteuses, de l'ordre de centaines de cycles sur ma plate-forme. Je suis plus intéressé par quelque chose qui n'implique pas ceux qui ne concernent pas. Je dois dire que ceci est une question purement curiosité.
(non testé - vous pourriez avoir besoin de quelques réductions supplémentaires.) Est-ce plus rapide que votre matériel ne peut faire x% 3? Si c'est le cas, ce n'est probablement pas beaucoup. 4% 3 == 1 , donc (4 ^ k * a + b)% 3 == (A + B)% 3 . Vous pouvez utiliser ce fait pour évaluer x% 3 pour un X 32 bits x:
Ce Comp.Compilers article a une recommandation spécifique pour l'informatique MODULO 3.
une alternative, surtout si la taille du maximum du dividende est modeste, c'est multiplier par la réciproque de 3 en tant que valeur à virgule fixe, avec suffisamment de morceaux de précision pour gérer le dividende de taille maximum pour calculer le quotient, puis Soustrayez 3 * quotient du dividende pour obtenir le reste. Toutes ces multiples peuvent être implémentées avec une séquence fixe de changements et d'ajouts. Le nombre d'instructions dépendra du modèle de bits de la réciprocité. Cela fonctionne assez bien lorsque le dividende Max est de taille modeste.
En ce qui concerne l'ajout de chiffres dans le nombre ... Si vous souhaitez ajouter les chiffres décimal , vous allez finir de ce qui constitue une conversion numérique-décimale, qui implique diviser par 10 quelque part. Si vous êtes prêt à vous contenter d'ajouter les chiffres de base2, vous pouvez le faire avec une boucle facile à droite et ajoutez une boucle. Différentes astuces intelligentes peuvent être utilisées pour le faire dans des morceaux de n bits pour accélérer davantage.
L'ajout de chiffres ne fonctionnera pas dans ce cas parce que vous devriez convertir le numéro en premier à un nombre décimal qui prend beaucoup plus de temps que de diviser.
Qu'est-ce que tu essayes réellement d'atteindre? À moins que ce ne soit une curiosité théorique, je doute que ce problème spécifique que vous puissiez être le goulot d'étranglement d'une application réelle ...
C'est à la fois pratique et théorique. La question découle d'essayer de distribuer plusieurs boucles imbriquées sur des centres cartésiens parmi les threads (Cuda spécifiquement, mais il n'est pas important) .J'ai déjà résolu le problème d'une autre manière, mais j'aimerais toujours savoir s'il y a un moyen. C'est un véritable goulot d'étranglement depuis la division entière et le modulo sont beaucoup plus chers que les opérations de points flottants que j'essaie de faire parallèlement.
@Georg Schölly: Pourquoi Decimal? Vous pouvez faire une chose similaire en binaire, par exemple, décimal 13 = 0xb = binaire "1101" est 1 modulo 3, à cause de -1 + 1-0 + 1 = 1. C'est la base de la réponse acceptée, bien que je doute que c'est la voie la plus rapide.