point fixe de multiplication / division pour 15.16 nombres

Question

Je cherche un algorithme pour le point fixe 15,16 multiplier et diviser des nombres.

J'ai déjà addition et la soustraction. C'était facile - simple, ajouter 32 bits et Soustraire. Avec multiplier et diviser, je peux aussi ajouter de nombreuses fonctions trigonométriques et exponentielle / log. Et je pense que je peux faire face à juste multiplier, comme ma bibliothèque a une fonction réciproque et je peux l'utiliser pour mettre en œuvre la division: a * (1/b) = a / b. Mais un 32 bits ne fonctionne pas multiplier car il ne tient pas compte du point de radix.

Je travaille sur un microcontrôleur 16 bits, donc je voudrais éviter quoi que ce soit plus de multiplier 32 bits, ce qui prend environ 4 cycles sur mon processeur. Ce n'est pas essentiel que, je suis juste essayer de remplacer les mathématiques à virgule flottante.

J'ai entendu je besoin de changer ou de faire pivoter le résultat, mais je ne suis pas sûr de savoir comment cela contribuerait ou plus précisément comment le déplacer. Toute suggestion ou aide appréciée!

Answer 1

Pensez est ainsi: votre numéro a.b est représenté comme (a.b * 65536)

Si vous multipliez a.b * c.d la valeur que vous obtenez est (a.b * 65536) * (* c.d 65536), afin de mettre ce retour dans la représentation à droite, vous devez diviser par 65536

Lorsque vous divisez ab / cd la valeur que vous obtenez est (ab * 65536) / (cd * 65536), afin de mettre ce retour dans la représentation à droite, vous devez multiplier par 65536. Vous devez multiplier par 65536 avant la fracture pour préserver autant de bits que possible dans le résultat.

Bien sûr, vous pouvez remplacer (<< 16) pour (* 65536) si cela est plus rapide sur votre processeur. De même, vous pouvez remplacer (>> 16) pour (/ 65536).

Voici a.b * c.d:

uint32_t result_low = (b * d);
uint32_t result_mid = (a * d) + (b * c);
uint32_t result_high = (a * c); 
uint32_t result = (result_high << 16) + result_mid + (result_low >> 16)

Answer 2

D'abord la théorie:. En supposant des nombres signés, la multiplication d'un Q15.16 par un autre Q15.16 vous donnera un Q (15 + 15 + 1) (16 + 16) = nombre de Q31.32. Ainsi, vous devez une variable d'entier de 64 bits pour contenir le résultat.

Si votre compilateur a un type entier 64 bits, il suffit d'utiliser et de laisser la figure du compilateur comment faire le 32 bits x multiplication 32 bits sur le processeur 16 bits (c'est ce que les compilateurs sont pour):

int32_t a_15q16, b_15q16;
int64_t res_31q32 = (int64_t)a_15q16 * (int64_t)b_15q16;

Ce que vous faites ensuite avec le résultat de Q31.32 dépend vraiment de votre application.

Vous demandez peut-être pourquoi le résultat a besoin 31 entier au lieu de 30. En fait, le bit supplémentaire est nécessaire que pour le cas où vous multipliez -2 ^ 15 ^ -2 par 15. Si vos opérandes ne sont jamais garantis à l'égalité -2 ^ 15 en même temps, vous pouvez supposer un résultat Q30.32.

Pour savoir si votre compilateur supporte les entiers 64 bits, vous pouvez avoir besoin de regarder le manuel du compilateur. Si cela est un compilateur C99, voir s'il y a un type int64_t dans votre tête de stdint.h.

Answer 3

La multiplication se fait facilement avec 64 bits se multiplient: (a * b) >> 16. Division, de même, se fait facilement avec 64 bits: (a << 16) / b. En fonction de vos arrondi / besoins d'erreur, vous voudrez peut-être compliquer un peu que pour obtenir le dernier bit de la sortie correcte.