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.
Gast
#596625
Du meinst sicher sqrt(2)/2 ? sqr(2)/2 ist naemlich eher einfach.
Gast
#596641
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
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?
Gast
#596937
> Schnelle Berechnung sqr(2)/2
Warum willst du das Berechnen? Ist doch eine Konstante...
Gast
#597449
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
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!
Gast
#597514
>> 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