Éviter l'arithmétique en virgule flottante

Question

J'ai écrit un petit synthé logiciel pour l'iPhone.
Pour améliorer les performances, j'ai mesuré mon application avec Shark et j'ai constaté que je perdais beaucoup de temps dans les conversions float/SInt16.
J'ai donc réécrit certaines parties pour contourner les conversions en pré-calculant des tables de recherche qui renvoient des échantillons SInt16 «prêts à l'emploi». Cela fonctionne bien jusqu'à présent.
Actuellement, j'essaie de réécrire certains filtres et ma mise en œuvre de l'enveloppe ADSR pour utiliser uniquement l'arithmétique entière, mais je pourrais utiliser quelques conseils pour effectuer des multiplications/divisions sans flottants.
Je ciblez les iPhone canonical format:

• LPCM
• 16 bits échantillons entiers

Quelles sont les bonnes méthodes pour appliquer une amplitude à mon échantillon final sans utiliser un flotteur?

Edit:
La seule chose que je pensais à ce jour est que je peux diviser par des puissances de 2 en décalant à droite mon échantillon actuel.

inBuffer[frame] = wavetable[i % cycleLengthInSamples] >> 4; 

Mais je ne peux pas imaginer de façon élégante de créer une enveloppe ADSR lisse avec cela.

Éditez2: Merci pour toutes vos réponses!
Mon approche actuelle:

• apporter toute mon enveloppe ADSR valeurs dans la gamme de SINT16 positif
• se multiplient avec la valeur actuelle de la table d'onde (intermédiaires de magasin comme SINT32)
• posté le résultat par 16 le droit

cela semble fonctionner :)

Answer 1

Point fixe est bon, car dans ce Si vous utilisez 16 bits. Le moyen le plus simple est de multiplier par une puissance de 10 selon la précision dont vous avez besoin. Si vous pouvez utiliser 32 bits ints comme intermédiaire, vous devriez être en mesure d'obtenir une précision décente. À la fin, vous pouvez revenir à un int de 16 bits, en arrondissant ou en tronquant comme vous préférez.

Editer: Vous souhaitez déplacer vers la gauche pour agrandir les valeurs. Stocke le résultat du décalage dans un type avec plus de précision (32 ou 64 bits en fonction de ce dont vous avez besoin). Le décalage simple ne fonctionnera pas si vous utilisez des types signés

Faites attention si vous multipliez ou divisez deux nombres à virgule fixe. La multiplication augmente (a * n) * (b n) et vous finissez par b n^2 au lieu d'un b n. La division est (a n)/(b n) qui est (a/b) au lieu de ((a n)/b). C'est pourquoi j'ai suggéré d'utiliser des puissances de 10, il est facile de trouver vos erreurs si vous n'êtes pas familier avec un point fixe.Lorsque vous avez terminé vos calculs, vous revenez à droite pour revenir à un int de 16 bits. Si vous voulez vous faire plaisir, vous pouvez également faire des arrondis avant de vous déplacer.

Je vous suggère de faire quelques lectures si vous êtes vraiment intéressé par la mise en œuvre de point fixe efficace. http://www.digitalsignallabs.com/fp.pdf

Answer 2

Jetez un oeil à cette page qui décrit les algorithmes de multiplication rapide.

http://www.newton.dep.anl.gov/askasci/math99/math99199.htm

Answer 3

Les réponses à this SO question sont assez complet en termes de mise en œuvre. Voici un peu plus d'explications que j'ai vues là-bas:

Une approche consiste à forcer tous vos nombres dans une plage, disons [-1.0,1.0). Ensuite, vous mappez ces nombres dans la plage [-2^15, (2^15) -1]. Par exemple,

Half = round(0.5*32768); //16384 
Third = round((1.0/3.0)*32768); //10923 

Lorsque vous multipliez ces deux chiffres que vous obtenez

Temp = Half*Third; //178962432 
Result = Temp/32768; //5461 = round(1.0/6.0)*32768 

par Dividing 32768 dans la dernière ligne est le point Patros fait au sujet de multiplications avoir besoin d'une étape de mise à l'échelle supplémentaire. Cela a plus de sens si vous écrivez explicitement la mise à l'échelle 2^N:

x1 = x1Float*(2^15); 
x2 = x2Float*(2^15); 
Temp = x1Float*x2Float*(2^15)*(2^15); 
Result = Temp/(2^15); //get back to 2^N scaling 

Voilà donc l'arithmétique. Pour l'implémentation, notez que la multiplication de deux entiers 16 bits nécessite un résultat de 32 bits, Temp doit donc être 32 bits. De plus, 32768 n'est pas représentable dans une variable de 16 bits, alors sachez que le compilateur rendra les messages instantanés sur 32 bits. Et comme vous l'avez noté, vous pouvez passer à multiplier/diviser par des puissances de 2 afin que vous puissiez écrire

N = 15; 
SInt16 x1 = round(x1Float * (1 << N)); 
SInt16 x2 = round(x2Float * (1 << N)); 
SInt32 Temp = x1*x2; 
Result = (SInt16)(Temp >> N); 
FloatResult = ((double)Result)/(1 << N); 

Mais supposons que [-1,1) n'est pas la bonne gamme? Si vous préférez limiter vos nombres à, disons, [-4.0,4.0), vous pouvez utiliser N = 13. Ensuite, vous avez 1 bit de signe, deux bits avant le point binaire, et 13 après. Ce sont les types fractionnaires à points fixes 1.15 et 3.13 respectivement. Vous échangez la précision dans la fraction pour l'espace libre. Ajouter et soustraire des types fractionnaires fonctionne correctement tant que vous observez la saturation. Pour diviser, comme l'a dit Patros, la mise à l'échelle s'annule. Donc, vous devez faire

Quotient = (x1/x2) << N; 

ou, pour préserver la précision

Quotient = (SInt16)(((SInt32)x1 << N)/x2); //x1 << N needs wide storage 

et en divisant par Multiplying nombres entiers fonctionne normalement. Par exemple, de diviser par 6, vous pouvez simplement écrire

Quotient = x1/6; //equivalent to x1Float*(2^15)/6, stays scaled 

Et dans le cas de division par une puissance de 2,

Quotient = x1 >> 3; //divides by 8, can't do x1 << -3 as Patros pointed out 

Ajout et soustraction de nombres entiers, cependant, ne fonctionne pas naïvement . Vous devez d'abord voir si le nombre entier correspond à votre type x.y, faire le type fractionnaire équivalent, et continuer.

J'espère que cela aide l'idée, regardez le code dans cette autre question pour les implémentations propres.

Answer 4

En général, supposons que vous utilisiez une représentation à virgule fixe 16.16 signée. Ainsi, un entier 32 bits aura une partie entière signée 16 bits et une partie fractionnaire 16 bits. Alors je ne sais pas quelle langue est utilisée dans le développement iPhone, mais cet exemple est en C (Objective-C peut-être?):

#include <stdint.h> 

typedef fixed16q16_t int32_t ; 
#define FIXED16Q16_SCALE 1 << 16 ; 

fixed16q16_t mult16q16(fixed16q16_t a, fixed16q16_t b) 
{ 
    return (a * b)/FIXED16Q16_SCALE ; 
} 

fixed16q16_t div16q16(fixed16q16_t a, fixed16q16_t b) 
{ 
    return (a * FIXED16Q16_SCALE)/b ; 
} 

Notez que ce qui précède est une mise en œuvre simpliste, et ne protège pas de l'arithmétique débordement. Par exemple, dans div16q16() I multiple avant la division pour maintenir la précision, mais en fonction des opérandes, l'opération peut déborder. Vous pouvez utiliser un intermédiaire 64 bits pour surmonter cela. En outre, la division s'annule toujours parce qu'elle utilise une division entière. Cela donne les meilleures performances, mais peut affecter la précision des calculs itératifs. Les correctifs sont simples mais s'ajoutent aux frais généraux.

Notez que lorsque vous multipliez ou divisez par une puissance constante de deux, la plupart des compilateurs repèrent l'optimisation triviale et utilisent un décalage. Cependant, C ne définit pas le comportement pour un décalage vers la droite d'un entier signé négatif, donc je l'ai laissé au compilateur pour le mettre en sécurité et la portabilité. YMV sur n'importe quelle langue que vous utilisez.

Dans un langage OO, fixed16q16_t serait naturellement un candidat pour une classe avec une surcharge d'opérateur, donc vous pouvez l'utiliser comme un type arithmétique normal.

Vous trouverez peut-être utile pour convertir les types:

double fixed16q16_to_double(fixed16q16_t fix) 
{ 
    return (double)fix/FIXED16Q16_SCALE ; 
} 

int fixed16q16_to_int(fixed16q16_t fix) 
{ 
    // Note this rounds to nearest rather than truncates 
    return ((fix + FIXED16Q16_SCALE/2))/FIXED16Q16_SCALE ; 
} 

fixed16q16_t int_to_fixed16q16(int i) 
{ 
    return i * FIXED16Q16_SCALE ; 
} 

fixed16q16_t double_to_fixed16q16(double d) 
{ 
    return (int)(d * FIXED16Q16_SCALE) ; 
} 

Ce sont les principes de base, il est possible d'obtenir plus sophistiqués et ajouter TRIG et d'autres fonctions mathématiques.

L'addition et la soustraction fixes fonctionnent avec les opérateurs + et - intégrés et leurs variantes.