Leistung der 2 Approximation in Fixpunkt

Question

Zur Zeit verwende ich eine kleine Nachschlagetabelle und lineare Interpolation, die ziemlich schnell und auch genau genug ist (maximaler Fehler ist kleiner als 0,001). Allerdings habe ich mich gefragt, ob es eine Annäherung gibt, die noch schneller ist. Da der ganzzahlige Teil des Exponenten extrahiert und durch Bitverschiebungen berechnet werden kann, muss die Approximation nur im Bereich von [-1,1] funktionieren Genauigkeit für Polynome niedriger Ordnung. Ich könnte mit einem maximalen Fehler um 0,01 herum leben, aber ich kam nicht in die Nähe dieser Zahl. Polynome höherer Ordnung sind keine Option, da sie viel weniger effizient sind als meine aktuelle auf der Nachschlagetabelle basierende Lösung.

Answer 1

Da kein spezifisches Festkommaformat angegeben wurde, werde ich eine mögliche Alternative zur Tabellensuche unter Verwendung von s15.16 Festkommaarithmetik demonstrieren, die ziemlich häufig verwendet wird. Die Grundidee besteht darin, den Eingang a in einen Integralteil i und einen Bruchteil f zu teilen, so dass f in [-0,5,0,5], dann verwenden Sie eine 0.037.790.090.1009.auf [-0.5, 0.5] und führen finale Skalierung basierend auf i.

Minimax Approximationen können mit Tools wie Mathematica, Maple oder Sollya generiert werden. Wenn keines dieser Werkzeuge verfügbar ist, könnte man eine benutzerdefinierte Implementierung des Remez-Algorithmus verwenden, um Minimax-Approximationen zu erzeugen.

Das Horner-Schema sollte verwendet werden, um das Polynom auszuwerten. Da Festkommaarithmetik verwendet wird, sollte die Auswertung des Polynoms die Operanden in Zwischenschritten bis zum maximal möglichen Ausmaß skalieren (d. H. Ohne Überlauf), um die Genauigkeit der Berechnung zu optimieren.

Der folgende C-Code geht davon aus, dass Rechtsverschiebungen, die auf vorzeichenbehaftete ganzzahlige Datentypen angewendet werden, zu arithmetischen Verschiebungsoperationen führen und daher negative Operanden entsprechend verschoben werden. Dies ist nicht garantiert durch die ISO-C-Norm, aber meiner Erfahrung nach wird es mit verschiedenen Werkzeugketten gut funktionieren. Im schlimmsten Fall könnte eine Inline-Anordnung verwendet werden, um die Erzeugung der gewünschten arithmetischen Rechtsverschiebungsbefehle zu erzwingen.

Der Ausgang des Tests einbezogen mit der fixed_exp2() Umsetzung unten aussehen soll, wie folgt:

testing fixed_exp2 with inputs in [-5.96484, 15) 
max. rel. err = 0.000999758 

Dies zeigt, dass die von 0,001 gebunden gewünschten Fehler für Eingänge im Intervall erfüllt ist [-5,96484, 15).

#include <stdio.h> 
#include <stdlib.h> 
#include <stdint.h> 
#include <math.h> 

/* compute exp2(a) in s15.16 fixed-point arithmetic, -16 < a < 15 */ 
int32_t fixed_exp2 (int32_t a) 
{ 
    int32_t i, f, r, s; 
    /* split a = i + f, such that f in [-0.5, 0.5] */ 
    i = (a + 0x8000) & ~0xffff; // 0.5 
    f = a - i; 
    s = ((15 << 16) - i) >> 16; 
    /* minimax approximation for exp2(f) on [-0.5, 0.5] */ 
    r = 0x00000e20;     // 5.5171669058037949e-2 
    r = (r * f + 0x3e1cc333) >> 17; // 2.4261112219321804e-1 
    r = (r * f + 0x58bd46a6) >> 16; // 6.9326098546062365e-1 
    r = r * f + 0x7ffde4a3;   // 9.9992807353939517e-1 
    return (uint32_t)r >> s; 
} 

double fixed_to_float (int32_t a) 
{ 
    return a/65536.0; 
} 

int main (void) 
{ 
    double a, res, ref, err, maxerr = 0.0; 
    int32_t x, start, end; 

    start = 0xfffa0900; 
    end = 0x000f0000; 
    printf ("testing fixed_exp2 with inputs in [%g, %g)\n", 
      fixed_to_float (start), fixed_to_float (end)); 

    for (x = start; x < end; x++) { 
     a = fixed_to_float (x); 
     ref = exp2 (a); 
     res = fixed_to_float (fixed_exp2 (x)); 
     err = fabs (res - ref)/ref; 
     if (err > maxerr) { 
      maxerr = err; 
     } 
    } 
    printf ("max. rel. err = %g\n", maxerr); 
    return EXIT_SUCCESS; 
}