Forum: Projekte & Code [ASM] (schnelle) Integer Wurzel 32bit


Announcement: there is an English version of this forum on EmbDev.net. Posts you create there will be displayed on Mikrocontroller.net and EmbDev.net.
von Läubi .. (laeubi) Benutzerseite


Angehängte Dateien:

Lesenswert?

Habe leztens mal die Wurzelfunktion aus der Codesammlung ausprobiert und 
war etwas "geschockt", bei großen Werten braucht die doch seeeeeeehr 
lange (über 850.000 clocks! ~ 100ms je nach Operandengröße).
Habe mich dann etwas nach Alternativen umgesehen und eine 
Implementierung gefunden die mit einer konstanten Zeit auskommt und habe 
das ganze mal in ASM umgesezt.

*Ergebnis*: unabhängig vom Operanden etwa 1300 Takte

Im Anhang befindet sich die ASM Datei + eine 
geschwindigkeitsoptimierte Variante welche nur 600 Takte braucht für 
beliebig große 32bit Operanden (verbraucht dann allerdings etwa 
1300bytes an code gegenüber 150byte der nicht optimierten Variante)

Im Source kann ausgewählt werden ob Platz/Speed optimierte Variante 
Verwendung finden soll, und ob das Device den movw Befehl unterstüzt.

Hier mal der Code der platzoptimierten Version, im ASM-File ist das 
vieleicht für den nicht so geübten ASM/AVR Studio Programmierer etwas 
unübersichtlich da ich viel mit den Assemblerdirektiven rumgespielt habe 
:)
1
wurzel32fast:
2
/* #######################################################################
3
Based on an Algorithm by Jim Ulery
4
  http://www.azillionmonkeys.com/qed/ulerysqroot.pdf
5
6
  Ported to ASM by Läubi, 2008
7
8
  Input r5:r4:r3:r2
9
  Output r1:r0
10
11
  ! Achtung! Die Eingabe wird hierbei zerstört!
12
  ! Wenn diese noch benötigt wird vorher sichern!
13
14
  C-Version:
15
  static unsigned julery_isqrt(unsigned long val) {
16
      unsigned long temp, g=0, b = 0x8000, bshft = 15;
17
      do {
18
          if ( val >= ( temp = (((g << 1) + b)<<bshft--) ) ) {
19
             g += b;
20
             val -= temp;
21
          }
22
      } while (b >>= 1);
23
      return g;
24
  }
25
####################################################################### */
26
//Register sichern
27
  push XL
28
  push XH
29
  push r17
30
  push r16
31
  push r6
32
  push r7
33
  push r8
34
  push r9
35
  push r10
36
  //X = b
37
  ldi XL,  LOW(0x8000)
38
  ldi XH, HIGH(0x8000)
39
  //r1:r0 = g = 0
40
  clr r0
41
  clr r1
42
  //temp = bshft
43
  ldi r17, 15
44
  clr r16
45
  wurzel32_2_wloop:
46
    //temp = g
47
    clr r9
48
    clr r8
49
    mov r7, r1
50
    mov r6, r0
51
    //g << 1
52
    lsl r6
53
    rol r7
54
    rol r8
55
    //leztes rol kann ausgelassen werden da g maximal 16 bit breit
56
    //und r9 = 0
57
    //+b
58
    add r6, XL
59
    adc r7, XH
60
    adc r8, r16
61
    adc r9, r16
62
    // << bshft
63
    mov r10, r17
64
    wurzel32_2_wl:
65
      lsl r6
66
      rol r7
67
      rol r8
68
      rol r9
69
      dec r17
70
    brne wurzel32_2_wl
71
    //bshft--
72
    mov r17, r10
73
    dec r17
74
    //val >= temp
75
    cp r2, r6
76
    cpc r3, r7
77
    cpc r4, r8
78
    cpc r5, r9
79
    brlo wurzel32_2_wd
80
    //g + = b
81
    add r0, XL
82
    adc r1, XH
83
    //val -=temp
84
    sub r2, r6
85
    sbc r3, r7
86
    sbc r4, r8
87
    sbc r5, r9
88
  //b >> 1 != 0?
89
  wurzel32_2_wd:
90
    lsr XH
91
    ror XL
92
    cpi XL, 1
93
    cpc XH, r16
94
    brne wurzel32_2_wloop
95
  //Register wieder herstellen
96
  pop r10
97
  pop r9
98
  pop r8
99
  pop r7
100
  pop r6
101
  pop r16
102
  pop r17
103
  pop XH
104
  pop XL
105
  ret

Hinweise sind gerne willkommen, ich möchte aber gleich darauf hinweisen 
das ich NICHT bis auf den lezten Takt optimiert habe (es ist also noch 
Potential drin wenn jemand spaß daran hat das noch weiter zu führen)

von Läubi .. (laeubi) Benutzerseite


Angehängte Dateien:

Lesenswert?

Und hier nochmal die "C-Variante" in einer compilierbaren Version welche 
ich zum testen verwendet habe.

von sum (Gast)


Lesenswert?

Hi Läubi,

sehr schick. Hast du mal verglichen, was der C-Compiler daraus macht?

Grüesse,
 sum

von Benedikt K. (benedikt)


Lesenswert?


von sum (Gast)


Lesenswert?

Habe gerade nochmal nachgeschaut, bei mir macht der Compiler 140 Byte 
draus. Wieviele Takte das braucht, weiss ich natürlich nicht.

sum

von Läubi .. (laeubi) Benutzerseite


Lesenswert?

sum wrote:
> Hi Läubi,
>
> sehr schick. Hast du mal verglichen, was der C-Compiler daraus macht?
>
> Grüesse,
>  sum
nein, ich hab kein gcc oder ähnliches bei mir installiert. Vieleicht 
kanns ja mal jemand probieren :)

Benedikt K. wrote:
> Die hier ist schneller und kleiner
Kannte ich nicht und hab ich jezt auch nicht getestet, kleiner ja auf 
jedenfall, aber es werden keine Register gerettet wenn du das bei mir 
noch abziehst kommt man auf den selben "speed".
Und ich fands auch mal interesannt sowas selbst zu machen und die Lösung 
aus der Codesammlung scheint mir nicht sehr brauchbar für 32bit (es sei 
den man hat vieeeel Zeit)

von Benedikt K. (benedikt)


Angehängte Dateien:

Lesenswert?

Läubi Mail@laeubi.de wrote:

> Benedikt K. wrote:
>> Die hier ist schneller und kleiner
> Kannte ich nicht und hab ich jezt auch nicht getestet, kleiner ja auf
> jedenfall, aber es werden keine Register gerettet wenn du das bei mir
> noch abziehst kommt man auf den selben "speed".

Retten braucht man nichts.
Ich hab die Wurzelroutine von ELM Chan etwas angepasst, so dass man ihn 
direkt in den Compiler einbinden kann. Man muss nur 1 Register sichern. 
Macht 55 Words...

Nutzen lässt sich das ganze dann so:
unsigned int sqrt32(unsigned long);

von Läubi .. (laeubi) Benutzerseite


Lesenswert?

> var[12:02] = <broken>
hab ich jezt so interpretiert das die Arbeitsregister 12 bis 2 zerstört 
werden.

Gibts eigentlich ne Erklärung WARUM die Routine funktioniert? Stehen ja 
leider keien Kommentare drann oder so :(

von Benedikt K. (benedikt)


Angehängte Dateien:

Lesenswert?

Läubi Mail@laeubi.de wrote:
>> var[12:02] = <broken>
> hab ich jezt so interpretiert das die Arbeitsregister 12 bis 2 zerstört
> werden.

Ja, dürfte so sein. Aber das interessiert im Normalfall ja nicht weiter, 
da der Compiler davon ausgeht, dass diese Register überschrieben werden.

> Gibts eigentlich ne Erklärung WARUM die Routine funktioniert? Stehen ja
> leider keien Kommentare drann oder so :(

Ich habe es auch schon aufgegeben die Programme von dem zu verstehen. 
Mir reicht es, wenn ich diese nutze kann.
Ich habe noch die 16bit Wurzelfunktion angehängt:
unsigned char sqrt16(unsigned int);

Die Multiplikatikations und Divisionsroutinen von dem sind auch nett:
Hier die komplette Seite von dem:
http://elm-chan.org/cc_e.html

von Läubi .. (laeubi) Benutzerseite


Angehängte Dateien:

Lesenswert?

So, ich hab jezt doch nochmal etwas dran rumgebastelt.

Als erstes hab ich etwas mit der Mathematik drauf eingeschlagen :P
1
unsigned int julery_isqrt2(unsigned int val) {
2
  unsigned int temp, g, b, bshft;
3
  g=0;
4
  b = 0x8000;
5
  bshft = 15;
6
  int i;
7
  for (i = 0; i < 15; i++) {
8
    temp = g;
9
    temp = temp + (b >> 1);
10
    temp = temp <<(bshft+1);
11
    if ( val >= temp) {
12
      g += b;
13
      val -= temp;
14
    }
15
    bshft--;
16
    b = b >> 1;
17
  }
18
  temp = (g<<1);
19
  temp = temp|1;
20
  if ( val >= temp) {
21
    g += b;
22
    val -= temp;
23
  }
24
  return g;
25
}
Man spart sich hier etwas das rumschieben von g, b und bshft können 
konstant angenommen werden wenn man die schleife ausrollt.
Der C-Compiler sollte es auch etwas einfacher haben das zu optimieren. 
Wenn man eine Architektur mit barrelshifter hat ist der Algorithmus auch 
noch etwas effizienter zu implementieren.

Ergebnis: Schnelle Variante 300-400 Takte, 810bytes code.

Sehr viel Code im vergleich zu gerademal etwa 100 Takten ersparnis im 
Vergleich zu Elm-Chans Version aber fals jemand es besonders eilig hat 
und etwas Codespace übrig ist es vieleicht ne Alternative, und ansonsten 
hat das rumbasteln auch Spaß gemacht :)
Der Code enthält jezt alle Optiemierungen für das schieben die mir 
eingefallen sind (0, 8, 16) der rest wird dann per links/rechts 
nachgeholt. da geht auch die meiste Zeit für drauf.

von Daniel C. (cagara)


Lesenswert?

Was macht ihr da eigentlich :) schmunzel

Wurzel in 800 Takten?? uiuiui

Warum nicht so? (x ist anfang der Wert, und am schluss seine wurzel)

int a,b;
b = x;
a = x = 0x3f;
x = b/x;
a = x = (x+a)>>1;
x = b/x;
a = x = (x+a)>>1;
x = b/x;
x = (x+a)>>1;

diese annäherung ist doch ne gute obere schranke für die echte wurzel, 
und sogut wie identisch!

Beschrieben in diesem Paper: 
http://supp.iar.com/FilesPublic/SUPPORT/000419/AN-G-002.pdf

von Andreas S. (andreas) (Admin) Benutzerseite


Lesenswert?

Und wie lange dauert eine 32 Bit-Division auf dem AVR?

von Löwe (Gast)


Lesenswert?

Zu faul zum Lesen - Daniel? Elm Chan braucht max. 185 Takte (16-Bit) und 
das Ergebnis ist genau.

von Gerry M. (gerry501)


Lesenswert?

Läubi .. schrieb:
>> var[12:02] = <broken>
> hab ich jezt so interpretiert das die Arbeitsregister 12 bis 2 zerstört
> werden.
>
> Gibts eigentlich ne Erklärung WARUM die Routine funktioniert? Stehen ja
> leider keien Kommentare drann oder so :(

Es wird ein Verfahren zum schriftlichen Wurzelziehen verwendet (ähnlich 
wie schriftlich dividieren):
http://de.wikipedia.org/wiki/Schriftliches_Wurzelziehen

hier ist das ganze für Binär-Zahlen noch verständlicher dargestellt:
http://www.onlinemathe.de/forum/Binaersystem-Zahlentheorie

Elm-Chan hat das Verfahren sehr trickreich umgesetzt. Ein Tip für 
Interessierte (16bit squareroot): Das Bit2 in seinem Register var4 
entspricht bei den 8 Durchläufen dem jeweiligen 'Lösungs-Bit'.

von Johann L. (gjlayde) Benutzerseite


Lesenswert?

Läubi .. schrieb:

> Im Anhang befindet sich die ASM Datei + eine
> geschwindigkeitsoptimierte Variante welche nur 600 Takte braucht für
> beliebig große 32bit Operanden (verbraucht dann allerdings etwa
> 1300bytes an code gegenüber 150byte der nicht optimierten Variante)
>
> Hinweise sind gerne willkommen, ich möchte aber gleich darauf hinweisen
> das ich NICHT bis auf den lezten Takt optimiert habe (es ist also noch
> Potential drin wenn jemand spaß daran hat das noch weiter zu führen)

Hi, im Wiki gibt's jetzt eine Version die nur noch 315 Ticks braucht und 
zusammen mit avr-gcc läuft:
   http://www.mikrocontroller.net/articles/AVR_Arithmetik#avr-gcc_Implementierung_.2832_Bit.29

von Michael H. (overthere)


Lesenswert?

Sieht schon verdammt brauchbar aus!
Könnte noch jemand die 16 Bit variante implementieren und ins Wiki 
schreiben?

von Johann L. (gjlayde) Benutzerseite


Lesenswert?

Michael H. schrieb:
> Sieht schon verdammt brauchbar aus!
> Könnte noch jemand die 16 Bit variante implementieren und ins Wiki
> schreiben?

Das hat eigentlich alles schon  Ruud v Gessel gemacht. Den Link zu den 
Implementierungen hab ich im Wiki zugefügt. Müsste also nur jemand 
wikitizieren und am besten umstellen auf avr-gcc ABI-konforme 
Registerbelegung. Und noch nen C-Header analog zur 32-Bit Wurzel.

Johann

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.