Si un matériel ne prend pas en charge les opérations de module ou de division, il faut beaucoup plus de cycles CPU pour simuler le module / division par logiciel. Existe-t-il un moyen plus rapide de calculer la division et le module si l'opérande vaut 10?
Dans mon projet, j'ai souvent besoin de calculer le module entier 10. En particulier, je travaille sur PIC16F et j'ai besoin d'afficher un nombre sur un écran LCD. Il y a 4 chiffres à prendre en charge, il y a donc 4 appels à la fonction module et division (implémentation logicielle). Autrement dit, comme suit:
digit = number % 10; // call to an expensive function
number /= 10; // call to an expensive function
somehow_lit_segments();
digit = number % 10; // call to an expensive function
number /= 10; // call to an expensive function
somehow_lit_segments();
digit = number % 10; // call to an expensive function
number /= 10; // call to an expensive function
somehow_lit_segments();
digit = number % 10; // call to an expensive function
number /= 10; // call to an expensive function
somehow_lit_segments();
Il existe d'autres domaines qui utilisent un code similaire.
Réponses:
Voici un algorithme binaire vers BCD que j'ai utilisé il y a plusieurs années basé sur celui trouvé ici . J'utilisais un pilote d'affichage BCD externe à 7 segments afin que le résultat puisse être écrit sur les ports appropriés directement sous forme de BCD compressé pour la sortie.
C'est assez rapide si vous avez un multiplicateur matériel dans le PIC, j'utilisais un PIC18F97J60. Si vous n'avez pas de multiplicateur matériel sur votre PIC, envisagez d'utiliser shift + add pour la multiplication.
Cela prend un entier 16 bits non signé et renvoie un BCD emballé à 5 chiffres, il pourrait être modifié et rendu plus rapide pour 4 chiffres. Il utilise shift + additions pour approximer la division par 10 mais étant donné la plage d'entrée limitée, il est exact pour cette utilisation. Vous voudrez peut-être emballer le résultat différemment ainsi pour aligner la façon dont vous utilisez le résultat.
la source
En supposant que des entiers non signés, la division et la multiplication peuvent être formées à partir de décalages de bits. Et à partir de la division et de la multiplication (entières), modulo peut être dérivé.
Pour multiplier par 10:
Diviser par 10 est plus difficile. Je connais plusieurs algorithmes de division. Si je me souviens bien, il existe un moyen de diviser par 10 rapidement en utilisant les décalages de bits et la soustraction, mais je ne me souviens pas de la méthode exacte. Si ce n'est pas vrai, il s'agit d'un algorithme de division qui gère <130 cycles . Je ne sais pas quel micro vous utilisez, mais vous pouvez l'utiliser d'une certaine manière, même si vous devez le porter.
EDIT: Quelqu'un dit plus à Stack Overflow , si vous pouvez tolérer un peu d'erreur et avoir un grand registre temporaire, cela fonctionnera:
En supposant que vous ayez la division et la multiplication, modulo est simple:
la source
Vous pouvez convertir du binaire en BCD compressé sans aucune division en utilisant l' algorithme de double dabble . Il utilise uniquement shift et add 3 .
Par exemple, convertir 243 10 = 11110011 2 en binaire
Cet algorithme est très efficace lorsqu'il n'y a pas de diviseur matériel disponible. De plus, seul le décalage à gauche de 1 est utilisé, donc c'est rapide même quand un levier de vitesses n'est pas disponible
la source
Selon la quantité de chiffres dont vous avez besoin, vous pourrez peut-être utiliser la méthode de la force brute (
d
- numéro d'entrée,t
- chaîne ASCII de sortie):Vous pouvez également changer les multiples ifs en une boucle, avec des puissances de dix obtenues par multiplication ou une table de recherche.
la source
Cette note d'application décrit les algorithmes pour l'arithmétique BCD, y compris la conversion du binaire en BCD et vice versa. L'Appnote est d'Atmel, qui est AVR, mais les algorithmes décrits sont indépendants du processeur.
la source
Je n'ai pas de bonne réponse, mais il y a une grande discussion sur notre site soeur Stack Overflow sur le même sujet exact de la division et de l'optimisation modulo.
Avez-vous suffisamment de mémoire pour implémenter une table de recherche?
Hackers Delight a un article sur les algorithmes de division optimaux.
la source
Avez-vous envisagé de conserver cette valeur comme BCD tout le temps (en utilisant de simples sous-programmes spéciaux "BCD increment" et "BCD add"), plutôt que de conserver cette valeur sous forme binaire et de la convertir en BCD si nécessaire (en utilisant une conversion plus difficile à comprendre) du binaire au sous-programme BCD)?
À un moment donné, tous les ordinateurs stockaient toutes les données sous forme de chiffres décimaux (engrenages à dix positions, tubes à vide à code sur deux, BCD, etc.), et cet héritage persiste encore aujourd'hui. (voir Pourquoi les puces d'horloge en temps réel utilisent BCD ).
la source
La PICList est une ressource incroyable pour les personnes qui programment des processeurs PIC.
Conversion BCD
Avez-vous envisagé d'utiliser une sous-routine binaire vers BCD éprouvée et prête à l'emploi spécialement optimisée pour le PIC16F?
En particulier, les utilisateurs de la PICList ont passé beaucoup de temps à optimiser les conversions binaires en BCD sur un PIC16F. Ces routines (chacune optimisée à la main pour une taille spécifique) sont résumées dans "PIC Microcontoller Radix Conversion Math Methods" http://www.piclist.com/techref/microchip/math/radix/index.htm
division entière et mod
Sur un processeur comme le PIC16F, un sous-programme spécialisé pour diviser par une constante est souvent beaucoup plus rapide qu'une routine à usage général "diviser la variable A par la variable B". Vous voudrez peut-être mettre votre constante (dans ce cas, "0,1") dans la "Génération de code pour la multiplication / division constante" http://www.piclist.com/techref/piclist/codegen/constdivmul.htm ou consultez le routines en conserve près de http://www.piclist.com/techref/microchip/math/basic.htm .
la source
Étant donné une multiplication matérielle 8x8, on peut calculer un divmod-10 d'un nombre de taille arbitraire en utilisant une routine qui le calcule pour un nombre de 12 bits dans la plage 0-2559 via la procédure:
Je suggère d'écrire une routine divmod dont le MSB du nombre sera en W et le LSB pointé par FSR; la routine doit stocker le quotient dans FSR avec post-décrémentation et laisser le reste dans W. Pour diviser un 32 bits par 10, on utiliserait alors quelque chose comme:
Une étape divmod-6 serait très similaire, sauf en utilisant des constantes de 85 et 6 plutôt que de 51 et 10. Dans les deux cas, je m'attendrais à ce que divmod10_step soit de 20 cycles (plus quatre pour l'appel / retour), donc un divmod10 court serait être d'environ 50 cycles et un long divmod10 serait d'environ 100 (si l'on cas particulier la première étape, on pourrait économiser quelques cycles).
la source
ce n'est peut-être pas le plus rapide mais c'est un moyen simple.
la source