Inverse efficace (1 / x) pour AVR

J'essaie de trouver un moyen efficace de calculer un inverse sur un AVR (ou de l'approcher).

J'essaie de calculer la période d'impulsion d'un moteur pas à pas afin de pouvoir faire varier la vitesse linéairement. La période est proportionnelle à l'inverse de la vitesse ( p = K/v), mais je ne peux pas penser à un bon moyen de calculer cela à la volée.

Ma formule est

p = 202/v + 298; // p in us; v varies from 1->100

En testant sur l'Arduino, la division semble être complètement ignorée en laissant pfixe à 298(bien que ce serait peut-être différent dans avr-gcc). J'ai également essayé de sommer vdans une boucle jusqu'à ce qu'elle dépasse 202et de compter les boucles, mais c'est assez lent.

Je pouvais générer une table de recherche et la stocker en flash, mais je me demandais s'il y avait une autre façon.

Edit : Peut-être que le titre devrait être "division efficace" ...

Mise à jour : Comme le souligne pingswept, ma formule pour mapper la période à la vitesse est incorrecte. Mais le problème principal est l'opération de division.

Edit 2 : Après une enquête plus approfondie, la division fonctionne sur l'arduino, le problème était dû à la fois à la formule incorrecte ci-dessus et à un débordement int ailleurs.

Une bonne chose à propos de la division est que plus ou moins tout le monde le fait. C'est une caractéristique assez centrale du langage C, et des compilateurs comme AVR-GCC (appelés par l'IDE Arduino) choisiront le meilleur algorithme de division disponible, même lorsque le microcontrôleur n'a pas d'instruction de division matérielle.

En d'autres termes, vous n'avez pas à vous soucier de la façon dont la division est implémentée, sauf si vous avez un cas spécial très étrange.

Si vous vous inquiétez, alors vous pourriez aimer lire les algorithmes de division officiels suggérés par Atmel (un optimisé pour la taille du code et un optimisé pour la vitesse d'exécution; aucun ne prend de mémoire de données). Ils sont dans:

http://www.atmel.com/dyn/resources/prod_documents/doc0936.pdf

qui est la note d'application "AVR200: routines de multiplication et de division" répertoriée sur la page Atmel pour ses (assez gros) processeurs Atmega comme les Atmega 168 et Atmega 328 utilisés dans les Arduinos standard. La liste des fiches techniques et notes d'application se trouve à:

http://www.atmel.com/dyn/products/product_card.asp?part_id=4720

me semble que tout ce dont vous avez besoin est une table de recherche à 100 entrées. Ça ne va pas beaucoup plus vite que ça.

#define VALUE_FOR_V_EQUALS_ZERO 0
uint16_t formula_lookup[100] = {VALUE_FOR_V_EQUALS_ZERO, 500, 399, 365, 348, ..., 300};

...

//"calculate" formula
p = formula_lookup[v > 67 ? 67 : v];

MODIFIEZ- vous en fait seulement une table de recherche de 68 valeurs puisque les valeurs de v supérieures à 67 sont toujours évaluées à 300.

Il y a de très bonnes techniques mentionnées dans le livre "Hackers Delight par Henry Warren et sur son site web hackersdelight.org . Pour une technique qui fonctionne bien avec des microcontrôleurs plus petits lors de la division par constantes, regardez ce fichier .

Votre fonction ne semble pas donner le résultat souhaité. Par exemple, la valeur 50 renvoie environ 302, tandis que 100 renvoie environ 300. Ces deux résultats n'entraîneront pratiquement aucun changement dans la vitesse du moteur.

Si je vous comprends bien, vous cherchez vraiment un moyen rapide de mapper les nombres 1-100 à la plage 300-500 (environ), de telle sorte que 1 correspond à 500 et 100 correspond à 300.

Essayez peut-être: p = 500 - (2 * v)

Mais je peux me méprendre - essayez-vous de calculer la ponctualité d'une onde carrée à fréquence constante? Quel est le 298?

Un moyen efficace d'approximer les divisions consiste à effectuer des décalages. par exemple si x = y / 103; diviser par 103 équivaut à multiplier par 0,0097087, donc pour approximer ce premier, sélectionnez un «bon» nombre de quart (c.-à-d. un nombre de base 2, 2,4,8,16,32 et ainsi de suite)

Pour cet exemple 1024 est un bon ajustement car on peut dire que 10/1024 = 0,009765 Il est alors possible de coder:

x = (y * 10) >> 10;

N'oubliez pas bien sûr de vous assurer que la variable y ne déborde pas de son type lorsqu'elle est multipliée. Ce n'est pas exact, mais c'est rapide.

Sur une autre note, si vous essayez de faire une division sur un CPU qui ne prend pas en charge la division, il y a une façon vraiment cool de le faire dans cet article Wiki.

http://en.wikipedia.org/wiki/Multiplicative_inverse

Pour approximer l'inverse de x, en utilisant uniquement la multiplication et la soustraction, on peut deviner un nombre y, puis remplacer à plusieurs reprises y par 2y - xy2. Une fois que le changement de y devient (et reste) suffisamment petit, y est une approximation de l'inverse de x.

Ce processus ici semble mcu convivial, mais il aurait besoin d' un peu de portage.

Bien qu'il semble que la LUT serait plus facile. Vous n'auriez besoin que de 100 octets, moins si vous utilisiez une certaine interpolation, et puisque la LUT est remplie de constantes, le compilateur pourrait même la localiser dans la zone de code au lieu de la zone de données.

Vérifiez que la division est effectuée en virgule flottante. J'utilise Microchip et non AVR, mais lorsque vous utilisez C18, vous devez forcer vos littéraux à être traités comme des virgules flottantes. Par exemple. Essayez de changer votre formule pour:

p = 202.0/v + 298.0;

Vous voulez rapide, alors voilà ..... Puisque l'AVR ne peut pas normaliser efficacement (décalage vers la gauche jusqu'à ce que vous ne puissiez plus changer), ignorez tous les algorithmes pseudo flottants. Le moyen le plus simple pour une division entière très précise et plus rapide dans un AVR est via une table de correspondance réciproque. La table stockera les inverses mises à l'échelle par un grand nombre (disons 2 ^ 32). Vous implémentez ensuite une multiplication unsigned32 x unsigned32 = unsigned 64 dans l'assembleur, donc réponse = (numérateur * inverseQ32 [dénominateur]) >> 32.
J'ai implémenté la fonction de multiplication à l'aide de l'assembleur en ligne, (enveloppé dans une fonction ca). GCC prend en charge les "longs longs" 64 bits, cependant, pour obtenir le résultat, vous devez multiplier 64 bits par 64 bits, pas 32x32 = 64 en raison des limitations du langage C sur l'architecture 8 bits ......

L'inconvénient de cette méthode est que vous utiliserez 4K x 4 = 16K de flash si vous souhaitez diviser par des entiers de 1 à 4096 ......

Une division non signée très précise est maintenant obtenue en environ 300 cycles en C.

Vous pouvez envisager d'utiliser des entiers à l'échelle 24 bits ou 16 bits pour plus de vitesse et moins de précision.

p = 202/v + 298; // p in us; v varies from 1->100

La valeur de retour de votre équation est déjà p=298puisque le compilateur divise d'abord puis ajoute, utilisez une résolution muldiv entière qui est:

p = ((202*100)/v + (298*100))/100 

Son utilisation est la même multiplication a*f, avec a = entier f = fraction.

Cela donne r=a*fmais f=b/calors r=a*b/cmais cela ne fonctionne pas encore car la position des opérateurs, donne la fonction finale r=(a*b)/cou muldiv, une manière de calculer les nombres de fraction en utilisant uniquement un entier.