Vermeidung von Gleitpunktarithmetik

Question

Ich schrieb einen kleinen Software-Synthesizer für das iPhone.
Zur weiteren Optimierung der Leistung gemessen ich meine Bewerbung mit Shark und fand, dass ich viel Zeit in float / sint16 Konvertierungen bin zu verlieren.
So schrieb ich einige Teile rund um die Umwandlungen durch Vorausberechnen Lookup-Tabellen zu erhalten, die „ready-to-use“ sint16 Proben zurück. Das funktioniert so weit in Ordnung.
Derzeit versuche ich nur Integer-Arithmetik einige Filter und meine ADSR-Hüllkurve Implementierung zu umschreiben zu verwenden, aber ich kann ein paar tipps verwenden, wie Multiplikationen / Divisionen ohne Schwimmer auszuführen.
Ich bin der iPhone kanonisches Format :

• LPCM
• 16-Bit-Integer-Proben

Was sind gute Ansätze eine Amplitude zu meiner letzten Probe anzuwenden, ohne einen Schwimmer mit?

Bearbeiten
Das einzige, was ich dachte, ist so weit, dass ich durch Potenzen von 2 durch Rechtsverschieben meiner aktuelle Probe teilen kann.

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

Aber ich kann mich keine elegante Weise einen glatten ADSR-Hüllkurve mit dem erstellen.

Edit2: Vielen Dank für Ihre großen Antworten!
Mein aktueller Ansatz:

• bringen alle meine ADSR-Hüllkurve Werte in den positiven Bereich sint16
• multiplizieren mit dem aktuellen Wert aus dem Wavetable (store Intermediate als sint32)
• verschiebt das Ergebnis um 16 nach rechts

Dies scheint zu funktionieren:)

Answer 1

Festpunkt ist gut, da in diesem Fall, dass Sie 16 Bits verwenden. Der einfachste Weg ist durch eine Leistung von 10 in Abhängigkeit von der Präzision, die Sie brauchen, um sich zu vermehren. Wenn Sie 32-Bit-ints als Zwischen verwenden können, sollten Sie in der Lage sein, anständige Genauigkeit zu erhalten. Am Ende können Sie zu einem 16-Bit-int zurück zu konvertieren, Runden oder Kürzen, wie Sie bevorzugen.

Edit: Sie wollen nach links verschieben, um die Werte größer zu machen. Speichern Sie das Ergebnis der Verschiebung in einer Art mit mehr Präzision (32 oder 64 Bit je nachdem, was Sie brauchen). einfaches Verschieben funktioniert nicht, wenn Sie signierte Typen verwenden

Achten Sie, wenn Sie multiplizieren oder zwei Festpunktzahlen zu teilen. Multipliziert man windet sich sein (a * n) * (b n) und Sie werden mit einem b n ^ 2 anstelle eines b n aufzuwickeln. Division (a n) / (b n), welches (a / b) anstelle von ((a n) / b). Deshalb habe ich mit Potenzen von 10 vorgeschlagen, macht es einfach, Ihre Fehler zu finden, wenn Sie nicht vertraut mit festen Punkt sind.

Wenn Sie Ihre Berechnungen fertig sind, können Sie nach rechts verschieben zurück auf eine 16-Bit-int zu erhalten. Wenn Sie Lust bekommen möchten, können Sie auch Runden, bevor Sie verschieben.

Ich schlage vor, Sie etwas zu lesen tun, wenn Sie bei der Umsetzung effizienter Fixpunkt wirklich interessiert sind. http://www.digitalsignallabs.com/fp.pdf

Answer 2

Die Antworten auf diese Frage SO sind ziemlich umfassend im Hinblick auf die Umsetzung. Hier ist ein bisschen mehr von einer Erklärung als ich dort sah:

Ein Ansatz ist es, alle Ihre Zahlen in einen Bereich zu zwingen, sagen [-1.0,1.0). Dann ordnen Sie diese Zahlen in den Bereich [-2 ^ 15 (2 ^ 15) -1]. Zum Beispiel

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

Wenn Sie diese beiden Zahlen multiplizieren Sie bekommen

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

von 32.768 in der letzten Zeile Aufteilung ist der Punkt, Patros gemacht über vervielfacht einen zusätzlichen Skalierungsschritt benötigen. Das macht mehr Sinn, wenn man die 2 ^ N Skalierung explizit schreiben:

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

Das ist also die Arithmetik. Für die Umsetzung beachten Sie, dass die Multiplikation von zwei 16-Bit-Integer braucht ein 32-Bit-Ergebnis, so sollte Temp 32-Bit sein. Auch ist 32768 nicht in einem 16-Bit-Variable darstellbar, so beachten Sie, dass der Compiler 32-Bit-immediates machen. Und wie Sie bereits erwähnt haben, können Sie verschieben multiplizieren / dividieren durch Potenzen von 2, so können Sie schreiben

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);

Aber angenommen, [-1,1) ist nicht der richtige Bereich? Wenn Sie lieber Ihre Zahlen beschränken würde, sagen wir, [-4.0,4.0), können Sie N = 13 verwenden Dann haben Sie ein Vorzeichenbit, zwei Bits vor dem binären Punkt und 13 nach. Diese sind 1,15 und 3,13 festen Punkt gebrochene Typen jeweils genannt. Sie handeln Präzision in der Fraktion bei einer lichten Höhe.

Addition und Subtraktion von fraktionierten Typen funktioniert gut, solange man für die Sättigung blicken. Für Kluft, wie Patros sagte, bricht die Skalierung tatsächlich aus. So haben Sie tun

Quotient = (x1/x2) << N;

oder zu bewahren Präzision

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

Multipliziert und durch ganze Zahlen Dividieren normal arbeitet. Zum Beispiel, um 6 zu teilen, können Sie einfach schreiben

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

Und im Fall des durch eine Potenz von 2 teilt,

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

Hinzufügen und ganze Zahlen subtrahieren, aber funktioniert nicht naiv. Sie müssen zuerst sehen, ob die ganze Zahl in Ihrem x.y Typ passt, die äquivalente fraktionierte Art zu machen und gehen Sie weiter.

Ich hoffe, dass dies mit der Idee hilft, Blick auf den Code in dieser anderen Frage für saubere Implementierungen.

Answer 3

Haben Sie einen Blick auf diese Seite, die eine schnelle Multiplikation Algorithmen beschrieben.

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

Answer 4

In der Regel sagen Sie eine signierte 16.16 Festpunktdarstellung verwendet werden. So dass ein 32-Bit-Integer-einen signierten 16-Bit-Integer-Teil und einen 16-Bit-Bruchteil hat. Dann weiß ich nicht, welche Sprache in iPhone Entwicklung verwendet wird, aber dieses Beispiel ist in C (Objective-C vielleicht?):

#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 ;
}

Beachten Sie, dass die oben eine vereinfachte Implementierung und bietet keinen Schutz vor arithmetischer Überlauf. Zum Beispiel in div16q16 () werden mehrfach vor dem divide Präzision zu halten, sondern in Abhängigkeit von den Operanden, auf dem Betrieb überlaufen. Sie können einen 64-Bit-Zwischen verwenden, um dies zu überwinden. Auch die Kluft immer abrundet, weil es Integer-Division verwendet. Dies ergibt die beste Leistung, kann aber die Präzision der iterativen Berechnungen beeinflussen. Fixes sind einfach, aber auf den Overhead hinzuzufügen.

Beachten Sie, dass bei Multiplizieren oder Dividieren durch eine Konstante Potenz von zwei, die meisten Compiler wird die triviale Optimierungs beschmutzen und eine Verschiebung verwenden. Jedoch C definieren das Verhalten nicht für eine Rechtsverschiebung eines negativen Ganzzahl mit Vorzeichen, so habe ich es an den Compiler beließ es für die Sicherheit und Portabilität zu erarbeiten. YMV auf welcher Sprache Sie verwenden.

In einer OO-Sprache würde fixed16q16_t natürlich ein Kandidat für eine Klasse mit Überladen von Operatoren, so dass Sie es wie ein normaler arithmetischen Typ verwenden können.

Sie finden es sinnvoll, zwischen Arten zu konvertieren:

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) ;
}

Das ist die Grundlagen ist es möglich, komplexere zu bekommen und Trig und andere mathematische Funktionen hinzuzufügen.

Fixed Addition und Subtraktion funktioniert mit den eingebauten in + und -. Betreiber und deren Varianten