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
:)
//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)
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)
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);
> 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 :(
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
So, ich hab jezt doch nochmal etwas dran rumgebastelt.
Als erstes hab ich etwas mit der Mathematik drauf eingeschlagen :P
1
unsignedintjulery_isqrt2(unsignedintval){
2
unsignedinttemp,g,b,bshft;
3
g=0;
4
b=0x8000;
5
bshft=15;
6
inti;
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
returng;
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.
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
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'.
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
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