So führen Sie eine Approximation kleiner Werte für sqrt (x) auf einem FPGA durch

Ich versuche, eine Festkomma-Routine zu implementieren, bei der der Wert von für kleines berechnet wird , das sich nähert . Die Zielarchitektur ist ein FPGA. Ein Problem ist, dass sich diese Funktion nicht leicht für die Verwendung von Taylors Erweiterung eignet. Man kann sehen , dass für kleine Werte von x, die Steigung von bis ins Unendliche geht , wenn nähert sich , also die Funktion Auswertung einer Potenzreihe mit großen Koeffizienten mit einem kleinen beinhaltet Multiplikation . Diese Methode ist daher numerisch instabil. x0$\sqrt{x}$$x$$0$ x0$\sqrt{x}$$x$$0$$x$

Unter Verwendung eines iterativen Ansatzes liefert der Newton-Raphson die folgende iterative Gleichung: , wo wir uns befinden versuchen, zu approximieren . Da klein ist, müsste ebenfalls klein sein, damit die Lösung konvergiert. Da die Gleichung das Teilen einer kleinen Zahl durch eine andere kleine Zahl beinhaltet, besteht die Möglichkeit, dass die Festpunktarithmetik fehlschlägt.$x_{n+1} = \frac {x_{n}}{2}- \frac{\alpha} {2x_{n}}$ αx$\sqrt {\alpha}$$\alpha$$x_{n}$

Damit möchte ich wissen, wie man eine Näherung kleiner Werte für Verwendung von Festkomma-Arithmetik implementiert, entweder unter Verwendung vorberechneter Koeffizienten oder iterativer Methoden.$\sqrt{x}$

Eine Routine, die ich zuvor verwendet habe (ich weiß nicht, ob es eine "richtige" ist oder nicht), ist ein Divide-and-Conquer-Ansatz.

Sie beginnen mit einem beliebigen oberen und unteren Wert (z. B. 5 bzw. 0 - die höchsten und niedrigsten Quadratwurzeln, die Sie finden möchten) und finden den Mittelpunkt zwischen ihnen. Quadrieren Sie diesen Wert.

Wenn der quadratische Wert größer als Ihr Ziel ist, setzen Sie den oberen Wert auf Ihren quadratischen Wert. Wenn es niedriger ist, stellen Sie den niedrigeren Wert ein.

Wiederholen Sie diesen Vorgang, bis entweder der quadratische Wert mit Ihrem Suchwert übereinstimmt oder Sie genügend Iterationen ausgeführt haben, um so genau zu sein, wie Sie möchten.

Hier ist eine kleine Version, die ich in Perl zusammengeschlagen habe:

#!/usr/bin/perl

my $val = shift;

my $max = 5;
my $min = 0;

my $iterations = 0;
my $maxiter = 40;

while(($max > $min) and ($iterations<$maxiter))
{
    $iterations++;
    my $diff = $min + ($max - $min) / 2;
    my $square = $diff * $diff;

    if($square == $val)
    {

        print "Square root found at $diff\n";
        print "$iterations iterations\n";
        exit(0);
    } else {
        if($square > $val)
        {
            $max = $diff;
        } else {
            $min = $diff;
        }
    }
}

my $diff = $min + ($max - $min) / 2;
print "Approximate square root after $iterations iterations: $diff\n";

Dies verwendet natürlich Gleitkomma, könnte aber leicht an einen festen Punkt angepasst werden. Sie können die Genauigkeit variieren, indem Sie die Iterationsgrenze ändern. Jede Iteration wird etwas genauer als die vorherige.

zB: - finde die Quadratwurzel von 9:

Approximate square root after 40 iterations: 2.99999999999955
   - or - 
Approximate square root after 10 iterations: 3.00048828125
   - or - 
Approximate square root after 5 iterations: 3.046875

Wenn es den Wert 3 gefunden hätte, hätte es natürlich früh aufgehört.

Geben Sie ihm genügend Iterationen und es sollte sehr genau sein:

./sqrt.pl 0.00284
Square root found at 0.0532916503778969
59 iterations

Hier sind einige Ideen und Routinen des aufgestiegenen transzendierenden Meisters / Guru Scott Dattalo hier .
Das ist natürlich ein Witz, außer dem Guru (Guru?) Teil. Scott ist großartig.

Relevante Diskussion. 2005 & PIC und einige sind C, können aber von Wert sein.

Wieder Scott - 2003

Zwei Meister !!!
Dattallo & Golovchenko.
Eine Reihe von Methoden

Sie haben nicht angegeben, was Sie unter "kleiner Wert" oder "Annäherung" verstehen. Also, was ich vorschlagen werde, könnte nicht funktionieren, aber hier geht.

Am einfachsten wäre es, einen Nachschlagetisch zu erstellen. Im Wesentlichen ein ROM, in dem der Adressbus die Nummer ist, die Sie quadratisch verwurzeln möchten, und die Datenausgabe das Ergebnis ist. Mit einem einzelnen BRAM können Sie eine 9-Bit-In- und 8-Bit-Out-LUT ausführen. Natürlich geben Ihnen mehr BRAMs einen größeren Tisch.

(BRAM = Der Xilinx-Begriff für einen Block-RAM, der auch als ROM verwendet werden kann. Andere FPGAs haben ähnliche Eigenschaften.)

Wenn Sie mehr Präzision wünschen, als Ihnen BRAMs bieten, können Sie zwei LUT-Einträge einfach linear interpolieren. Angenommen, Sie möchten eine 12-Bit-Eingabe, haben aber nur BRAMs für 10 Bit. Sie nehmen die obersten 10 Bits Ihrer Eingabe und schlagen diese in der LUT nach. Addieren Sie 1 zu diesen 10 Bits und suchen Sie auch diesen Wert. Anschließend führen Sie eine einfache lineare Interpolation zwischen den beiden Ergebnissen durch, wobei Sie anhand der unteren 2 Bits das Verhältnis eines Werts zum anderen angeben. Natürlich gibt Ihnen dies nur eine Annäherung, aber ich denke, wenn Sie rechnen, werden Sie feststellen, dass es vielleicht gut genug ist.

Diese Methode ist bei Zahlen mit niedrigem Wert am ungenauesten, aber wenn die Eingabe auf höhere Werte geht, steigt die Genauigkeit erheblich an.

Eine Optimierung des obigen Verfahrens wäre die Verwendung der BRAMs als Dual-Port-ROM. Auf diese Weise können Sie zwei Werte auslesen, ohne die Anzahl der verwendeten BRAMs zu erhöhen. Auf diese Weise können Sie auch einen SQRT für jeden Taktzyklus mit einigen Verzögerungen beim Pipelining berechnen.

Diese Methode funktioniert übrigens auch für SINE / COSINE!

Versuchen Sie den folgenden Ansatz

• Wenn die Zahl negativ ist, gehen Sie entsprechend vor.
• Wenn die Zahl 0 ist, geben Sie 0 zurück.
• Andernfalls:
• Normalisieren Sie auf eine Zahl im Bereich [1/4, 1]: Zählen Sie, wie oft k Sie Ihre Zahl mit 4 ( x <<= 2in C) multiplizieren müssen, bis sie innerhalb des obigen Bereichs liegt.
• Verwenden Sie einen beliebigen Ansatz (Polynomnäherungen, Newtons Methode für sqrt a [n] = (a [n-1] + k / a [n-1]) / 2 usw.), um die Quadratwurzel innerhalb dieses Bereichs zu berechnen
• denormalisieren: um k Bits nach rechts verschieben

Versuchen Sie also lassen Sie und als nächstes Wenn MSb n von rechts ist, sei zuerst . Konvergiert in <4 Iterationen.d = ( x - y 2 ) / 2 y = ( x / y - y ) ≤ 1 y = y + d . y = 1 ≪ ( n / 2 $x=(y+d)^2 \approx y^2+2dy$$d=(x-y^2)/2y = (x/y-y) \gg 1$$y=y+d.$$y=1 \ll (n/2)$

Versuch: Verbessertes Erraten für die 1. Variable

Ihre Zahl kann berücksichtigt werden: A * 2 ^ n
Die erste Annäherung lautet dann: A * 2 ^ (n / 2)

Angenommen, Sie verwenden eine 32-Bit-Zahl, wobei 24 Bit zum Halten von Brüchen verwendet werden. Für Zahlen> 1:
1. Zählen Sie die Anzahl der im ganzzahligen Teil (N) verwendeten Bits.
2. Halbieren Sie diese Zahl (N '= N / 2, dh 1 Bit nach rechts verschoben).
3. Verschieben Sie die ursprüngliche Zahl nach rechts um N'. : Dies ist Ihre erste Vermutung.

In diesem Format ist die kleinste Zahl, die Sie haben können, 2 ^ -24. Die Quadratwurzel wird ungefähr 2 ^ -12 ba. Also für Zahlen <1:
1. Zählen Sie die Anzahl der "Null" -Bits im Bruch, bis Sie ein gesetztes Bit (N) erreichen.
2. Halbieren Sie diese Zahl (N '= N / 2, dh 1 Bit nach rechts verschoben).
3. LINKS Verschieben Sie die ursprüngliche Zahl um die überarbeitete Anzahl: Dies ist Ihre erste Vermutung.

Beispiel:
0,0000 0000 0000 0000 1 [16 führende Nullen] entspricht ungefähr: 0,0000 0000 1

Wenn Sie immer noch Probleme mit kleinem A haben: Können Sie 1 / A berechnen?
Wenn ja, invertieren Sie Ihre Zahl und versuchen Sie es mit dem Inverse Square Root-Algorithmus:
x' = 0.5x * (3 - Ax^2)