Multiplizieren mit sqrt(2)/2 in Schieben und Addieren

[romanua (Gast)]

Hallo,

ich studiere die FFT-Routine aus www.renan.org/ARM/doc/Apps16pdf.pdf ,
bzw. die ARM-Optimierungstips aus dem Dokument.

Es steht auf Seite 14, dass die Autoren Multiplikation durch sqrt(2)/2
in Shifts und Adds machen. Wie macht man das?


Danke,
r.

[Jan (Gast)]

sqrt2 ist ja 2^2 also
2 = 0b0010 ins quadrat =4
4 = 0b0100 also einfach einmal linksschieben
z.B.
a=0x02
a=a<<1
wäre sqrt

[romanua (Gast)]

Jan, Danke fuer die Erklaerung.

Ich habe mich, glaube ich, nicht ganz klar ausgedrueckt. Unter sqrt(2)
meinte ich 2^(1/2).

[Christoph Kessler (db1uq) (Gast)]

(die Hälfte von Wurzel von zwei ) ist identisch mit (eins durch Wurzel
von zwei)  und beträgt etwa 0,707.
Ich habe mal auf dem AVR ein Näherung von (Wurzel zwei minus 1)mittels
Schieben und addieren berechnet:

;* 106/256 is an approximation of Sqrt(2)-1 = 0.4142
  clr  TempH    ; (1) multiply by 106
  lsl  TempL    ; (1) 106 = 2+8+32+64
  rol  TempM    ; (1) = "*2"
  mov  VectL,TempL  ; (1)
  mov  VectM,TempM  ; (1) add to vector
  clr  VectH    ; (1)
  lsl  TempL    ; (1)
  rol  TempM    ; (1)
  lsl  TempL    ; (1)
  rol  TempM    ; (1) = "*8"
  add  VectL,TempL  ; (1)
  adc  VectM,TempM  ; (1) add to vector
  lsl  TempL    ; (1)
  rol  TempM    ; (1)
  lsl  TempL    ; (1)
  rol  TempM    ; (1) = "*32", high byte = 0
  add  VectL,TempL  ; (1)
  adc  VectM,TempM  ; (1) add to vector
  lsl  TempL    ; (1)
  rol  TempM    ; (1) = "*64"
  rol  TempH    ; (1) now we need a 3rd byte
  add  VectL,TempL  ; (1)
  adc  VectM,TempM  ; (1) add to vector
  adc  VectH,TempH  ; (1)

[Christoph Kessler (db1uq) (Gast)]

Es ging um einen AD-gewandelten 12 Bit breiten Messwert in TempL/TempH,
das Ergebnis wird noch durch 256 geteilt, indem das niederwertigste
Ergebnis-Byte VectL weggelassen wird.

[Christoph Kessler (db1uq) (Gast)]

für (Wurzel_zwei)/2 = 0,70710678118654752440084436210485..
wäre die nächste 8Bit-Näherung 181/256 = 0,70703125
mit 16 Bit: 46341/65536 = 0,7071075439453125

[romanua (Gast)]

Hallo,  Christoph,

Danke fuer den Ansatz. Ich hatte vor sqrt(2)/2 =0.707106781
als 181/256=0.70703125 zu berechnen. Das waere dann
1-2^(-2)-2^(-5)-2^(-7)-2^(-8).

Sagen wir mal, wir wollen x*sqrt(2)/2=x/sqrt(2)=x*0.707106781
berechnen.

ldr r1,=x
mov r2,r1
sub r2,r1,LSR #2
sub r2,r1,LSR #5
sub r2,r1,LSR #5
sub r2,r1,LSR #8

Direkt wurde ich es so machen (x ist 16 bit lang):

ldr r1,=x
ldr r2,=46341 @; Round( sqrt(2)*2^15 )
mul r2,r1,r2
mov r3,r3,LSR #16

das macht r3=x*0.707108

Ich frage mich jetzt, ob das nicht schneller ist, besonders wenn man
bedenkt, dass man ldr r2,=23170 "reusen"  kann.

[Kai (Gast)]

Hallo

Wie wärs so:
1. Mit 181 Multiplizieren (kann mann ja auch durch verschieben und
addieren machen)
2. Ergebnis durch 256 teilen (= das niederwertigste Byte weglassen)
(eventuell vorher 128 addieren, um Rundungsfehler zu vermeiden)

Der Fehler ist nach meiner Rechnung 0,01 Prozent.

[romanua (Gast)]

Hallo,Kai,

Danke fuer den Vorschlag.

Ich frage mich, ob es an sqrt(2)/2 etwas besonderes gibt, da  die
Autoren des Papers diesen Fall angeblich mit einer separaten Routine
behandeln.


So, wie wir oben vorgeschlagen haben, kann man eigentlich jede
irrationale Zahl annaehern.

Ich wuerde  erwarten, dass die sqrt(2)/2 auf eine Weise berechnen, auf
die man andere Faelle nicht berechnen kann.  Ich konnte aber nichts im
Netz finden.