Schnelle Berechnung sqr(2)/2 mit der ARM

[Vlad S. (sempai)]

Ich versuche derzeit eine kleine Anwendung für die FFT auf ARM Assembler 
zu schreiben. Ich berufe mich auf "Application Note 16: Implementing 
Fast Fourier Transforms on the ARM RISC Processor". Auf der Seite 14 
steht:

"... For these values of k, cos(kw) and sin(wk) take on simple values 
such as 0, 1 and sqr(2)/2. Multiplies by these constants can be done 
using shifts and adds. The MUL instruction is not needed..."

Ich habe aber niergendwo im Internet gefunden, wie man mit Shifts und 
Adds a*sqr(2)/2 schneller berechnen kann, als der Befehl MUL, der 3 bis 
5 Takte dauert und meines Erachtens sowieso schneller sein muss. Kann 
jemand die Frage klären? Danke für jede Hilfe.

[nop(); (Gast)]

Du meinst sicher sqrt(2)/2 ? sqr(2)/2 ist naemlich eher einfach.

[Nils (Gast)]

Hallo Vlad,

Ein Leftshift entspricht einer Multiplikation mit 2.
Ein Rightshift entspricht einer Division durch 2.

Beispiel:
Dez: 1*1  Bin: 01 << 0 -> 01
Dez: 1*2  Bin: 01 << 1 -> 10
Dez: 2/2  Bin: 10 >> 1 -> 01

mit
>> Rightshift
<< Leftshift

Weiter:
SQRT(2)/(2) = 1 / SQRT(2)
Dieser Wert ist ungefähr (32-Bit-Bereich):
23170/32768 = 23170 / (2^15)

Also ist die Multiplikation x * SQRT(2)/(2):
(x * 23170) >> 15

Für 2er-Potenzen von x gilt:
2^n * 23170 / (2^15) = 23170 * 2^(n-15) für n >=15
Äquivalent (und hier hier interessanter):
2^n * 23170 / (2^15) = 23170 / 2^(15-n) für n < 15

Also:
2^n * 23170 / (2^15) entspricht 23170 >> (15-n)
Damit ein Shift und eine Addition.

Gruß
Nils

[Vlad S. (sempai)]

Danke Nils,

allerdings bin ich mir immer noch nicht im Klaren, wie es praktisch 
funktionieren würde.

Mal angenommen, ich habe einen beliebigen Wert im Register, 32 Bit, die 
ersten 16 Stellen entsprechen Zahlen vor dem Komma, die letzten 16 - 
nach dem Komma. Wie kan ich den o.g. Algorithmus verwenden?..

Z.B.:
520=512+8=2^9+2^8
520/sqrt(2)=(2^9+2^8)*23170/(2^15) entspricht 23170>>(15-9) + 
23170>>(15-3)

Zu viele Schritte, oder habe ich etwas falsch verstanden?

[hackklotz (Gast)]

> Schnelle Berechnung sqr(2)/2

Warum willst du das Berechnen? Ist doch eine Konstante...

[Nils (Gast)]

Hallo Vlad,

google mal nach:
'shift & add algorithmus' (bzw. 'shift & add algorithm')
Da wirst Du fündig, z.B.:
www.iaik.tugraz.at/teaching/03_rechnernetze%20und%20organisation/folien/ 
VO04_alu.pdf
www.uni-paderborn.de/fachbereich/AG/rammig/www/members/berndk/RA-PDF/RA0 
9_Arithmetik.pdf

Inwieweit Dir das eine Rechenzeitersparnis bringt, musst Du selbst 
beurteilen. Wenn Du hardwareseitig keine Festkomma-Multiplikation 
implementiert hast, sollte 'shift & add' schon Rechenzeit sparen.

Zu Deinem Beispiel:
520=512+8=2^9+2^3

520 / SQRT(2)
= 2^9 * 23170/(2^15) + 2^3 * 23170/(2^15)
= 23170 / (2^6) + 23170 / (2^12)

entspricht:
(23170 >> 6) + (23170 >> 12)

Achja, betreffs: Application Note 16
Der Satz:
The MUL instruction is not needed...
geht weiter
... for the first three stages.
Ich lese das so, dass für eine weitere Entwicklung der Fourier-Reihe 
keine Rechenzeitersparnis durch 'shift & add' zu erreichen ist - 
korrigiert mich, wenn ich falsch liege.

Gruß
Nils

[Vlad S. (sempai)]

Hallo Nils,

im "Application Note 16: ..." geht es wirklich darum, dass die 
optimierte schnelle Fourier Transformation bei sin und cos von 0, pi/4 
und pi/2 keine MUL Befehle benutzt. Dadurch wird die Rechenzeit fast 
doppel schneller. Bei anderen Werten ist MUL einzusetzen, da hast du 
recht.

Da steht cos(pi/4)=sin(pi/4)=sqrt(2)/2. Man hätte denken können, dass 
die Berechnung von a*sqrt(2)/2 in ein paar Takten mit Shifts und Adds zu 
erreichen ist. Das von dir angebotene Verfahren ist sehr gut, aber dafür 
muss man genau wissen, was man berechnet, um der Wert a in der Reihe 
2^n+...2^2+2^1+2^0 presentieren zu können. Und wenn man es schon weiß, 
bräuchte man keine zusätzlichen Berechnungen durchzuführen, oder?..

Die Frage war, wie man mit einer unbekannten Zahl arbeiten kann. 
Wahrscheinlich, wenn ich mir den Shift & Add Algorithmus grob ansehe, 
geht man davon aus, dass sqrt(2)/2 ungefähr gleich 23170/32768 = 23170 / 
(2^15) ist, und benutzt diese Konstante bei der Berechnung durch diesen 
Algorithmus. Muss mir es durch den Kopf gehen lassen.

Besten Dank für die Auskunft!

[Nils (Gast)]

>> Und wenn man es schon weiß, bräuchte man keine zusätzlichen Berechnungen 
durchzuführen, oder?..
Genau. Und wenn Du mit beliebigen Werten multipliziert, musst Du shift & 
add solange in einer Schleife durchführen, bis Du keine 2er-Potenzen 
mehr übrig hast - multiplizieren eben - nur im 2er-System.

Der Trick, Konstanten durch rationale Zahlen mit einem Nenner 2^n 
darzustellen, funktioniert auch für andere 'beliebte' Konstanten, z.B.:
ln(2) = 22713 / (2^15)
Ebenso für andere Bit-Weiten:
1/SQRT(2) = 11585 / (2^14)
ln(2) = 11356 / (2^14)

Schön, dass Du weitergekommen bist,
Gruß
Nils