Hi,
das Thema Quadratwurzel stellt sich häufig als zeitaufwendiges Problem
dar.
Nach einiger Überlegung habe ich hier eine Version erstellt, die meines
Wissen nach derzeit die schnellste für AVR/mega Prozessoren mit MUL und
MOVW Befehlen in Assembler ist. Bei 8Mhz werden 3,88 us verbraucht. Ohne
Call/Ret. Registersicherung überlasse ich je nach Anwendung dem Nutzer.
Als Ergebnis wird der ganzzahliger Anteil in Register r20 geliefert.
Diese Version ist (noch nicht ganz) Speedoptimiert. Es lassen sich noch
weitere ca. 6-10 Takte sparen. Eine Sizeoptimierte Version ist in Arbeit
(ca.15 Codezeilen, ASM). Eine 32bit Version ist in Arbeit. Desweiteren
eine sehr schnelle 16/32bit Divisionsroutine. Ebenso eine
fsqrt16-Floatversion mit 2 Nachkommastellen (xxx,xx). Dazu benötige ich
jedoch besagte Division.
Alle Routinen basieren auf einem einfachen Zahlentrick den ich als Kind
mal gelernt hab. Die Halbierungsroutine.
Prinzip: Das Ergebnis beginnt immer mit 128. Es liegt letztendlich
zwischen 0 und 255. Durch prüfen ob das Quadrat ("mul ergeb, ergeb")
grösser/gleich("brsh") ist lässt sich nun ermitteln ob das Ergebnis +64
oder -64 gerechnet werden muss.Dies setzt sich bis zu 1 fort. Damit
lässt sich mit nur 8 Zügen der genaue Wert ermitteln. Für jedes weitere
Bit in der Ausgangszahl erhöht sich die Anzahl an Zügen um 1.Also für
32bit, 16 Züge.
Dieses Prinzip läßt sich nun auf jede Bitgrösse anwenden.
Es werden 4 Arbeitsregister verbraucht,
Ich empfehle allen das Dezimalsystem zu vergessen. Das duale Bitsystem
ist das bessere (2er Potenz).
Dies ist mein Dank an das Forum für all die 1000 Tips und Hilfen (durch
lesen). Denn ich bin kein Programmieren, Informatiker oder Mathematiker.
Ich will nur n paar Roboter bauen ;)
Besonderen Dank an
Peter Dannegger, für inspirierende Codezeilen und clevere Ideen
(Interesse an einem kommerziellen Projekt?)
Gerhard Schmidt, für n AVR-Kurs, www.avr-asm-tutorial.net
D. Austin, AVR466 AppNote, für ne brauchbare Lösung (bald ohne Taylor ;)
)
ChaN, für die beste Routine ohne Hardwaremultyply, elm-chan.org
Ulrich Radig, für zeigen was alles machbar ist und ne coole Website
und viele andere...
Bei grösserem Interesse kann der Code auch kommentiert werden.
PS: Wer einen Fehler im Text findet darf ihn behalten, im Code nicht ;)
Marko Surup schrieb
> Bei 8Mhz werden 3,88 us verbraucht.
Korrektur: 8MHz -> 7,75 us, 16 MHz -> 3,88 us
Marko Surup schrieb
> D. Austin, AVR466 AppNote
Korrektur: AVR446 AppNote
raketenfred schrieb:> Ich kann leider kein ASM- aber wenn ich deinen Text richtig verstanden> habe- ist deine Wurzelroutine, der "Binären Suche" ähnlich?
Das ist korrekt.(ähnlich)
Der Unterschied ist das keine "Suche" stattfindet. Darin liegt ein Teil
der Optimierung.
Ein "Treffer" wird als "größer als" betrachtet. Dadurch werden keine
Abfragetakte verschwendet. In diesem Fall ca. 16 Takte.Eine weitere
Optimierung liegt in der Nichtauswertung des Vorzeichens für den
nächsten Schritt.dies wird durch die doppelte Subtraktion erreicht.Somit
wird das Ergebnis ständig hin und hergeschubbst.und das kann jedes
Rechenwerk sehr gut. Mit der letzen Subtraktion wird das Ergebnis dann
auf den richtigen Wert "gezogen".(oder eben nicht).Eine Auswertung auf
Treffer macht in der Praxis sowieso keinen Sinn, weil irgendwann eine
Zahl kommt die sowie die ganze Laufzeit braucht.Somit hat man ein
Laufzeitstabiles Modul das sich konstant verhält.
Ich kann schon mal bestätigen, daß der Algorithmus korrekt ist :-)
Meine Portierung für avr-gcc sieht momentan so aus:
C-Teil
1
#include<stdint.h>
2
3
externuint8_tsqrt16_floor(uint16_t);
ASM-Teil
1
#define __zero_reg__ 1
2
#define __tmp_reg__ 0
3
4
.macro DEFUN name
5
.global \name
6
.func \name
7
\name:
8
.endm
9
10
.macro ENDF name
11
.size \name, .-\name
12
.endfunc
13
.endm
14
15
.text
16
17
#define RES R23
18
#define QIN 24 // input
19
20
.macro qstep M
21
.if \M == 128
22
cpi QIN+1, hi8(16384)
23
.else
24
cp QIN, R0
25
cpc QIN+1, R1
26
.endif
27
28
.if \M == 1
29
sbci RES, 0
30
.else
31
brsh 0f
32
subi RES, \M
33
0: subi RES, -\M/2
34
.endif
35
.endm
36
37
DEFUN sqrt16_floor
38
ldi RES, 128
39
qstep 128
40
mul RES, RES
41
qstep 64
42
mul RES, RES
43
qstep 32
44
mul RES, RES
45
qstep 16
46
mul RES, RES
47
qstep 8
48
mul RES, RES
49
qstep 4
50
mul RES, RES
51
qstep 2
52
mul RES, RES
53
qstep 1
54
clr __zero_reg__
55
mov R24, RES
56
ret
57
ENDF sqrt16_floor
58
59
#undef RES
60
#undef QIN
Ein MOVW wird nicht benötigt, und einige andere Instruktionen konnten
wegoptimiert werden.
Das ist alles avr-gcc ABI-konform, und im Hinblick auf avr-gcc gibt es
noch Optimierungspotential indem die Funktion nicht als Blackbox
beschrieben wird, sondern ihr Registerverhalten dem Compiler dargelegt
wird.
> Ein MOVW wird nicht benötigt, und einige andere Instruktionen konnten> wegoptimiert werden.
Nicht ganz korrekt.
Zur Durchführung des 16 Vergleichs wird ein Compare with Carry benötigt
da der Vergleich nur mit den oberen 16 Registern möglich ist.Ein MOV
Befehl benötigt wie MOVW auch 2 Byte und 1 Takt.Er dient der
Übersichtlichkeit. Sollte es ein Target geben welches einen MUL Befehl
hat aber kein MOVW wäre dies korrekt.
Wie in der Main-post erwähnt ist eine Volloptimierung(Speed) in
Arbeit.Dennoch: welche Instruktionen könnten denn weg?
Korrektor zu MOVW und CPC möglicherweise hast du Recht!
Ich werde das gleich prüfen. Laut Datenblatt sollte der Vergleich mit
allen Registern gelingen.
Die Einschränkung gilt für CPI.
Marko Surup schrieb:> welche Instruktionen könnten denn weg?
Den Code hab ich oben hingeschrieben, einfach gegen deinen Code
vergleichen.
Hier ausgetextet als Disassembly; am Anfang und am Ende können ein paar
Befehle weg.
R23 = sqrt16_floor (R25:R24)
Clobbers: R0, R1
1
ldi r23, 0x80
2
cpi r25, 0x40
3
brcc .+2
4
subi r23, 0x80
5
subi r23, 0xC0
6
mul r23, r23
7
cp r24, r0
8
cpc r25, r1
9
brcc .+2
10
subi r23, 0x40
11
subi r23, 0xE0
12
mul r23, r23
13
cp r24, r0
14
cpc r25, r1
15
brcc .+2
16
subi r23, 0x20
17
subi r23, 0xF0
18
mul r23, r23
19
cp r24, r0
20
cpc r25, r1
21
brcc .+2
22
subi r23, 0x10
23
subi r23, 0xF8
24
mul r23, r23
25
cp r24, r0
26
cpc r25, r1
27
brcc .+2
28
subi r23, 0x08
29
subi r23, 0xFC
30
mul r23, r23
31
cp r24, r0
32
cpc r25, r1
33
brcc .+2
34
subi r23, 0x04
35
subi r23, 0xFE
36
mul r23, r23
37
cp r24, r0
38
cpc r25, r1
39
brcc .+2
40
subi r23, 0x02
41
subi r23, 0xFF
42
mul r23, r23
43
cp r24, r0
44
cpc r25, r1
45
sbci r23, 0x00
Zudem kann das zweite SUBI entfallen wenn man das erste LDI und das
erste SUBI entsprechend wählt. Allerdings ist die Laufzeit dann nicht
mehr unabhängig von der Eingabe.
@ Johann L. (gjlayde)
Vielen Dank für deine Optimierung.
MOVW war vollkommen unnötig. Die letzte Codezeile (sbci ergeb, 0) ist
ebenfalls clever.dies spart ungewünschte Branchverzweigungen am Ende.Ich
hatte das instinktive auch im Kopf (hier ist doch irgendwo ein Bit und
ich brauch doch nur noch eins).
Ich habe die HEX-Werte wieder auf DEC ungeschrieben, dies erhält doch
etwas die Transparenz und erlaubt eine leichtere Bitverbreiterung.
Welchen Unterschied siehst du zwischen BRSH und BRCC? Ich vermute da
keine negativen Zahlen auftreten ist das Einbeziehen des N-Flags nicht
von Bedeutung.
Ich bin Anfänger im Code schreiben und kenne noch nicht alle Befehle.Das
ist mein erster Algorithmus.(Kopf gegen Compiler, da verliert man
schonmal).
Eine Portierung auf die C-Ebene war nie geplant.Bei Implementierung
würde ich mich über eine Authorennennung+Optimizer freuen.Kann man das
ganze fix "ffsqrt16" nennen? (fastfloor...)
Laufzeit fest 52 Takte.
8 MHz -> 6,38 µs
16 MHz-> 3,19 µs
Ich habe Fragen zur AtmelAppNote 446, die Taylor-Approximation soll
entfernt werde. Da ich Möglichkeiten sehe auch zwei 32Bit-Wurzeln
schnell zu berechnen.
Kann mir jemand helfen?(Detailfragen bei Antwort)
Nochmals vielen Dank.
Marko Surup schrieb:> @ Johann L. (gjlayde)>> Ich habe die HEX-Werte wieder auf DEC ungeschrieben, dies erhält doch> etwas die Transparenz und erlaubt eine leichtere Bitverbreiterung.> Welchen Unterschied siehst du zwischen BRSH und BRCC?
In Beitrag "Re: 16bit Quadratwurzel in 63 Takten, fsqrt16.asm"
steht ja auch BRSH sowie Diezimalwerte. BRSH und BRCC sind exakt gleich
und haben sen selben Opcode, so wie es auch sonst viel semantischen
Zucker in den AVR-Instruktionen gibt. Der Disassembler muss sich jedoch
für eine Darstellung entscheiden da er nicht die Asm-Quelle kennt
sondern aus Maschinencode disassembliert.
Wie gesagt ist Beitrag "Re: AVR: 16bit Quadratwurzel in 63 Takten, fsqrt16.asm"
lediglich ein Disassembly das ich anfügte, weil dir die
Änderungen/Optimierungen im erstgenannten Post wohl nicht klar waren.
> Kann man das ganze fix "ffsqrt16" nennen? (fastfloor...)
Der Name ust ja fast egal, wichtig ist in erster Linie eine genaue
Dokumentation so daß man genau weiß, was der Algorithmus macht: Was ist
Ein- und Ausgabe, welche Register werden wie verändert, man brauch MUL
etc.
Eine Funktion "fast" zu nennen ist nur sinnvoll, wenn es auch eine
"slow"-Version gibt oder eine auf Größe optimierte. Die Funktion ist
allerdings recht kurz so daß eine Größenoptimierung nicht sooo viel
bringen dürfte.
Am Anfang kann noch eine weitere Instruktion gespart werden:
Anstatt
1
ldi r23, 128
2
cpi r25, 64
3
brsh 0f
4
subi r23, 128
5
0: subi r23, -64
geht
1
ldi r23, 192
2
cpi r25, 64
3
brsh 0f
4
ldi r23, 64
5
0:
Denn in C-Notation ist beides
1
R23=C?64:192;
> Ich habe Fragen zur AtmelAppNote 446, die Taylor-Approximation soll> entfernt werde. Da ich Möglichkeiten sehe auch zwei 32Bit-Wurzeln> schnell zu berechnen.> Kann mir jemand helfen?
Generall bin ich bei begrenztem Wertebereich der Arithmetik wie zB
Fixedpoint nicht sonderlich von Taylor o.ä. begeistert, da man a priori
nicht sieht, ob alle Zwischenergebnisse ohne Überlauf berechnet werden
können. Siehe auch meine Anmerkungen in
Beitrag "Re: e_funktion ohne Floating unit rechnen"
Für 32-Bit Wurzel gibt es einen Eintrag AVR Arithmetik: Wurzel im
Wiki, der sich damit vielleicht auch beschleunigen und/oder verkürzen
lässt. Eine aufgerollte Schleife wie bei der 16-Bit-Version dürfte aber
grob das 4-fache an Speicher verschlingen.
Mit der folgenden, size-optimierten Version bekommt man die Wurzel mit
10 Instruktionen bzw. in der avr-gcc kompatiblen Version mit 13
Instruktionen (inc. RET):
Ich möchte noch hinzufügen das der Code nativ in Assembler geschrieben
ist. Einen Disassembler hat der Code nie gesehen.
C ist was für Leute die sich gern mit kryptischen Sonderzeichen
schmücken.
Ich kann leider (noch) nicht nachvollziehen wie die Optimierung zustande
kam.
Meine Handoptimierung war ähnlich gedacht. Dennoch ist diese 2 Takte
besser.
Ein Size-optimierte Version von ffsqrt16 mache ich wenn mehrere danach
fragen würden.
Ich brauch sie nicht.Die Codelänge läge bei ca.16 Zeilen und 1-2
Register mehr.
Die 32bit Version wird etwa 120 Takte in Anspruch nehmen.
Marko Surup schrieb:> Ich möchte noch hinzufügen das der Code nativ in Assembler geschrieben> ist.
Das gilt für meinen Code auch.
> Einen Disassembler hat der Code nie gesehen.
Des Disassembler habe ich nur verwendet, um das Makro "qstep"
auszulösen. Dafür kenne ich keinen anderen Weg, als die Quelle zu
assemblieren und dann das Disassembly anzuschauen. Das Makro habe ich
verwendet, weil ich keinen Bandwurm schreiben wollte und mit dem Makro
die Struktur des Algorithmus' optisch ganz klar zu Tage tritt.
> C ist was für Leute die sich gern mit kryptischen Sonderzeichen> schmücken.
Naja, das gilt für jede (Programmier)Sprache, mit der man nicht vertraut
ist ;-)
> Ich kann leider (noch) nicht nachvollziehen wie die Optimierung zustande> kam.
Welche Optimierung meinst du denn? Sie kam genauso zustande wie deine
Optimierungen auch: via Brain 0.9. Keine Magie im Assembler, keine im
Disassembler.
> Ein Size-optimierte Version von ffsqrt16 mache ich wenn mehrere danach> fragen würden.
Steht bereits oben: 10 Instruktionen und für alle 65536 Eingabewerte
getestet :-)
> Die 32bit Version wird etwa 120 Takte in Anspruch nehmen.
Das sehe ich jetzt nicht. Dein Algorithmus aufgeblasen auf 32 Bits
müsste eine 32=16x16 Multiplikation verwenden, die geschätze 18 Ticks
braucht. Mit 15 * (Multiplikationen + Vergleichen + Addition) = 15 * (18
+ 4 + 4) bin ich bei knapp 400 Instruktionen, wobei ich die beiden
Additionen mit lediglich 4 Ticks angesetzt habe, da man anfangs nur auf
dem High-Teil operieren muss.
Damit wäre dein Algorithmus langsamer als die Routine von Ruud v. Gessel
aus dem Wiki, die mit ca. 300 Ticks und 60 Bytes zu Buche schlägt.
Johann L. schrieb:> via Brain 0.9. Keine Magie im Assembler, keine im> Disassembler.
Chapó! (Ein respektvolles Grinsen liegt mir im Gesicht)
Aber Brain 0.9 ist ja wohl ne Untertreibung, eher 2.0
Anfänger gegen Profi ... ;)
Zumindest weiss ich jetzt das meine Denkweise richtig ist.
Die size-optimierten Version ist sehr geil.Dann is das auch erledigt.
Besser sehe ich das nicht machbar.
Die 32 bit Version ist nicht als stures erweitern der 16 bit Version
gedacht.Ein Ansatz ist das nicht nur die erste Operation
nicht-ausgerechnet wird sondern die ersten 3. In die speedoptimierten 16
bit Version wollte ich das einbauen, sehe aber nicht mehr den Nutzen.
Also 16384<--? BRCC, 4096<--BRCC , 36864<--BRCC (Vielleicht 3-5 Takte,
oder?)
Das ganze dann auch für das HIGH-Byte der 32 bit.(ca. 10-15 Takte oder
mehr)
Damit würde sich die Bitbreite auf ca. 24 bit verringern.
Der weitere Ansatz wäre eine Div/100 und eine spätere
Zusammenführung.Das ist aber noch sehr sehr wage. Die Zahlen fliegen
noch im Kopf. Die noch geplante Divisionsroutine ist Teil davon.
120 Tackte sind wohl nicht haltbar. 160-200 denke ich aber schon.
Ne Optimierung deinerseits wäre ne Supersache. Aber wenn du das jetzt
umsetzt machts mir keinen Spass mehr und ich kann auch nicht mehr sagen
das es meine ist (ich hoffe du kannst das Verstehen). Es sei den ich
übernehm mich dann "musst" du ;)
Ich will daran Lernen und nicht einfach Code einkleben.
Zur Atmel AppNote 446: (D. Austin)
Eine deutsche Übersetzung der Formeln gibt es hier.
http://www.mikrocontroller.net/attachment/80637/Formeln_Geschwindigkeitsprofil.pdf
Meine Werte:
spr= 1600 (Schritte pro Umdrehung)
Schrittwinkel= 0.003926990816987242
Winkelgeschwindigkeit= ?
Winkelbeschleunigung= ?
1. Ich denke ich tue mich mit der rad- Benutzung schwer.
2. Welche ist die entscheidende Formel vor Taylor? (Gl 4.5)?
3. Wie sieht die Formel für Decceleration aus?(also Rückwärts)
4. kannst du ein Beispiel mit eingesetzten Zahlen machen.
5. Lässt sich ein nichtlineares Profil mit einer linearen Veränderung
der Winkelbeschleunigung/Schrittanzahl erreichen? Habe ich das richtig
verstanden?
Mach mich klug ;)
Marko Surup schrieb:> Die 32 bit Version ist nicht als stures erweitern der 16 bit Version> gedacht.Ein Ansatz ist das nicht nur die erste Operation> nicht-ausgerechnet wird sondern die ersten 3. In die speedoptimierten 16> bit Version wollte ich das einbauen, sehe aber nicht mehr den Nutzen.> Also 16384<--? BRCC, 4096<--BRCC , 36864<--BRCC (Vielleicht 3-5 Takte,> oder?)
Bahnhof?
> Das ganze dann auch für das HIGH-Byte der 32 bit.(ca. 10-15 Takte oder> mehr)> Damit würde sich die Bitbreite auf ca. 24 bit verringern.
Für eine 32-Bit Zahl könnte man den Highteil der Wurzel aus der Wurzel
des Highteils der Zahl erhalten und läge damit schlimmstenfalls 1 unter
dem korrekten Highteil. Wie man von da weiterkommt sehe ich jetzt aber
nicht. Für eine Suche müsste man dann ja irgendwo mittendrin aufsetzen.
> Ne Optimierung deinerseits wäre ne Supersache. Aber wenn du das jetzt> umsetzt machts mir keinen Spass mehr und ich kann auch nicht mehr sagen
Nö, da hab ich keine Ambitionen. Das einzige Mal daß ich ne Wurzel auf
AVR brauchte war es die Wurzel aus einer komplexen 4.12 Zahl um in
Echtzeit Julia-Mengen rendern zu können. Das Ergebnis war allerdings
sehr bescheiden und ich hab es dann sein lassen.
> Ich will daran Lernen und nicht einfach Code einkleben.
Dicker Pluspunkt :-)
> Zur Atmel AppNote 446: (D. Austin)> Eine deutsche Übersetzung der Formeln gibt es hier.> http://www.mikrocontroller.net/attachment/80637/Formeln_Geschwindigkeitsprofil.pdf>> Meine Werte:> spr= 1600 (Schritte pro Umdrehung)> Schrittwinkel= 0.003926990816987242
Also γ = 2π/1600
> Winkelgeschwindigkeit= ?
Mit den Bezeichnungen aus dem Papier und ν = Umdrehungen pro Sekunde ist
> Winkelbeschleunigung= ?
Ist mit diesen Angaben nicht bestimmbar → Hausaufgabe.
> 1. Ich denke ich tue mich mit der rad- Benutzung schwer.
Ein Umlauf = 2π d.h. als Winkelmaß dient der zurückgelegte Umfang geteit
durch den Kreisradius.
> 2. Welche ist die entscheidende Formel vor Taylor? (Gl 4.5)?
Es geht darum, eine gleichmäßig beschleinigte rotatorische Bewegung
mittels eines Schrittmotors zu erzeugen (offenbar unter der
Voraussetzung, daß am Motor keine Last hängt). Mit der konstanten
Winkelbeschleunigung α ergibt sich der Winkel γ(α) nach der Zeit t und
wenn man mit γ(0) = 0 und ω(0) = 0 startet zu γ(t) = ½ α t² oder
umgestellt nach t:
Weil α konstant ist, erhält man für die Zeit t_n, zu der ein Schritt
auszuführen ist, als proportional zu √n denn γ ist proportional zu n.
> 3. Wie sieht die Formel für Decceleration aus? (also Rückwärts)
Im Prinzip genauso, nur daß man in den Formeln für Winkelgeschwindigkeit
und Winkel nicht bei 0 anfängt für t=0 sindern mit ω(0) = ω_0 und γ(0) =
γ_0.
> 4. kannst du ein Beispiel mit eingesetzten Zahlen machen.
Das ist alles keine schwarze Magie und Stoff der Mittelstufe →
Hausaufgabe.
> 5. Lässt sich ein nichtlineares Profil mit einer linearen Veränderung> der Winkelbeschleunigung/Schrittanzahl erreichen? Habe ich das richtig> verstanden?
Was ist "Profil"?
Stephan Henning schrieb:> na dann wartet mal bis sich der PeDa meldet
auf den warte ich ja!!! seite der main-post
Habe mittlerweile eine (Fast)volloptimierten Algorithmus mit 48 Takten.
Ca. 45 sind drin :)
Marko Surup schrieb:> Habe mittlerweile eine (Fast)volloptimierten Algorithmus mit 48 Takten.> Ca. 45 sind drin :)
Ich bin bei 46 Ticks und 40 Instruktionen (also 6 * MUL), sehe aber
nicht, wo da noch gespart werden kann. :-(
Johann L. schrieb:> Ich bin bei 46 Ticks und 40 Instruktionen (also 6 * MUL), sehe aber> nicht, wo da noch gespart werden kann. :-(
Ich bin bei 46 Ticks mit 41(?) Instruktionen, sieht identisch aus
Ich sehe auch nix mehr ausser deine 40
Eine 41 Ticks Version hatte "Rechenfehler"
Eine Direktabfrage der ersten 3 MUL´s brachte keinen Takt-Gewinn.
Marko Surup schrieb:> ffsqrt16V3.txt
Damit erhalte ich srt16sp(4096) = 63
mul ergeb, ergeb
cpc r25, r1
versteh ich auch nicht, aber selbst
mul ergeb, ergeb
cp r25, r1
hilft nicht.
Johann L. schrieb:> Damit erhalte ich srt16sp(4096) = 63>> mul ergeb, ergeb> cpc r25, r1>> versteh ich auch nicht, aber selbst>> mul ergeb, ergeb> cp r25, r1>> hilft nicht.
ja... hab echt kein Erklärung...irgendwie unlogisch... ich geb mich
geschlagen.
srt16sp(36864) = 191 ?
ich werde das erste MUL nicht ganz los
zeig deins
Thomas O. schrieb:> hier gibts auch ein paar Infos dazu> http://www-user.tu-chemnitz.de/~heha/Mikrocontroll...
Der unqualifizierteste Kommentar der Woche. Psssst ;) (das ist die
Schlauberger-Mentalität die ich leiden kann). Nach Copy/Paste jetzt
Google/Paste.
Eine size-optimierte Version (die nicht das selbe in der Umsetzung ist)
wurde bereits erstellt.
@Johann:
Bin wieder bei 48 Takten.
Mir erschließt sich nicht mal im Ansatz warum ein Test auf das Highbyte
von 4096 (DEC 16, HEX10) nicht gelingt!!! Und wo ist das Carrybit hin?
PS: deine Erklärung zur AVRappnote is ja wohl n Witz! Ich bin
Autodidakt, mehr Hausaufgaben geht wohl kaum.Formeln abschreiben kann
ich selber. Es gibt keinen "echten" Kreisdurchmesser. Mach ein Beispiel
bis zum TCNT-Wert. Takt(n1)=60000, n=8000.Alle Werte sind bekannt.
Mittelstufe?, pfffff... (nix für Ungut)
Vielleicht ist der Ansatz aber auch Schrott.
Marko Surup schrieb:> @Johann:> PS: deine Erklärung zur AVRappnote is ja wohl n Witz!
So wie ich dich verstand hakt es bereits an den Basics?
> 1. Ich denke ich tue mich mit der rad- Benutzung schwer.> 2. Welche ist die entscheidende Formel [...]?
Ich sehe auch nicht, was da eine Integer-Wurzel bringt.
Marko Surup schrieb:> ja... hab echt kein Erklärung...irgendwie unlogisch... ich geb mich> geschlagen.> srt16sp(36864) = 191 ?> ich werde das erste MUL nicht ganz los>> zeig deins
Die Routine ist
1
qstep 1 << 6
2
mul RES, RES
3
qstep 1 << 5
4
mul RES, RES
5
qstep 1 << 4
6
mul RES, RES
7
qstep 1 << 3
8
mul RES, RES
9
qstep 1 << 2
10
mul RES, RES
11
qstep 1 << 1
12
mul RES, RES
13
qstep 1 << 0
14
;; for avr-gcc ABI
15
clr __zero_reg__
16
mov R24, RES
17
ret
Wobei die Logik im qstep-Makro steckt. Das erste qstep expandiert zu
1
ldi RES, hi8 (9*\M*\M)
2
cpi QIN+1, hi8 (4*\M*\M)
3
brsh 0f
4
ldi RES, hi8 (\M*\M)
5
0: cp QIN+1, RES
6
brsh 0f
7
subi RES, 64
8
0: subi RES, -80
wobei da noch nicht alles parametrisiert ist und daher noch magische
Zahlen auftauchen.
Für alle anderen Parameter M expendiert das Makro zu (austexten der
ganzen Routine erspar ich mir)
1
.if \M >= 16
2
cp QIN+1, R1
3
.else
4
cp QIN, R0
5
cpc QIN+1, R1
6
.endif
7
8
.if \M == 1
9
sbci RES, 0
10
.else
11
brsh 0f
12
subi RES, \M
13
0: subi RES, -\M/2
14
.endif
Damit bin ich wie gesagt bei 40 Instruktionen und 46 Ticks.
Allerding wird der Anfang zunehmend kryptischer. Wenn man weiter mit dem
Speed-Fetisch rumspielen will ist daher eine Nachguck-Tabelle für den
Anfang womöglich passender.
Fabian G. schrieb:> Wie aufwendig wäre es eigentlich die Routine noch so abzuändern, dass> auf das letzte Bit gerundet wird?
Bitte genauere Definition des gewünschten Ergebnisses.
Eine Rundung auf 0.5 zum Nächsten ist kaum sinnvoll da das "Raster"
trotzdem 1 bleibt.
Im Gegenteil, bei floor hat man wenigstens den genauen Umschaltpunkt.
Oder meinst du etwas anderes?
Johann L. schrieb:> @ Johann L
Ich habe noch mal einige Grundlegende Überlegungen angestellt und denke
das man nun die 16bit speedoptimierte Version abschliessen kann.
Ich kann deine Art den Code zu schreiben mittlerweile zum Teil
lesen(denke ich(!?!?))
Johann L. schrieb:> .if \M >= 16> cp QIN+1, R1
Das dürfte wohl die letzte sinnvolle Optimierung sein. Ich hab das
garnicht gerafft, erst nachdem ich fertig war. Das hatte ich auch. Bis
16*16 runter sind die LOWBYTE´s ja hübsche Nullen.
Vielen Dank für deine ausdauernde Hilfe, das sind Quantensprünge für
mich. :)))
Auch super das du den Sizecode in der AVR-Arithmetik gestellt hast.
Für nen Anfänger is das ne sehr geile Sache.
Dabei gefällt mir die Nutzung des Register mit lsr bei mir (lsr r22 ->>
add r23, r22)
Clevere Doppelnutzung.
Mein Code ist jetzt voll getestet: Er braucht 47 Takte und hat 41
Instruktionen.
Es entstehen keine magischen Zahlen mehr (schönes Wort).
Ich denke damit kann man das Thema auch abschliessen. Auch wenn da
vielleicht, eventuell, irgendwie,... noch was geht.
Ich hab wirklich ne Menge mitgenommen.
In den nächsten 2-3 Tagen würde ich den Code in einem neuen Thread
einstellen mit dann passender Überschrift und eine ausfühlichen
Erklärung zu Prinzip und Wirkungsweise. Sowie ebenfalls in die
AVR-Arithmetik Ecke.Jedoch in reinen asm (mir is das auch lieber). Wenn
du möchtest kannst du ja auch daraus Inlineassembler oder was auch immer
die Welt braucht machen.(ick würd wenn ick könnt, wa ;) )
Ich neige nicht zum Understatement darum sage ich ganz klar.
Das ist dann der schnellste Algorithmus der Welt für diese Anwendung.Und
der kürzeste auch. :))) Nicht zu vergessen: No-Jitter !!!
Leider willst du eine 32bit Version ja nicht mehr optimieren.Mal schaun
wie weit ich allein komm. Erst ab 24/32 bit is der Welt ja geholfen.
Johann L. schrieb:> Ich sehe auch nicht, was da eine Integer-Wurzel bringt.
Wohl wahr, aber mir dämmert da ne Idee ;)) ...
Nochmal Danke. Big Respect für Skills
Läubi .. schrieb:> Stell den code lieber direkt hier rein und die Erklärung ins Wiki, sonst> sind die infos wieder überall verstreut
Das wäre mir sehr sehr unrecht.ich kann verstehen das die codesammlung
bissl klar bleiben soll aber schon in der Main-post sind Fehler.und n
fehlerhafter code ist auch noch dabei.nicht sehr Vertrauenserweckend.das
ist nicht nur mein erster Code sondern auch mein erster Beitrag im
Internet.Und die Überschrift stimmt auch nicht mehr. Also wenn du mir
nicht mit Verbannung drohst, würd ich das lieber so machen. Ich würde
dann hier auf den neuen Thread verweisen. Bitte einen Link zum Wiki wo
ähnliches steht, wie gesagt bin Anfänger.
Marko Surup schrieb:> Fabian G. schrieb:>> Wie aufwendig wäre es eigentlich die Routine noch so abzuändern, dass>> auf das letzte Bit gerundet wird?>> Bitte genauere Definition des gewünschten Ergebnisses.> Eine Rundung auf 0.5 zum Nächsten ist kaum sinnvoll da das "Raster"> trotzdem 1 bleibt.> Im Gegenteil, bei floor hat man wenigstens den genauen Umschaltpunkt.> Oder meinst du etwas anderes?
Ok, falsch ausgedrückt.
Was ich meinte ist, dass ein sqrt(13) = 3,60555... eine 4 liefert
anstelle einer 3, also ein runden des Ergebnisses.
Marko Surup schrieb:> Fabian G. schrieb:>> Wie aufwendig wäre es eigentlich die Routine noch so abzuändern, dass>> auf das letzte Bit gerundet wird?>> Bitte genauere Definition des gewünschten Ergebnisses.
Die momentane floor-Version liefert
d.h. alle Nachkommastellen der Quadratwurzel werden abgeschnitten. Auf
das letzte Bit zu runden ist dann:
wobei man Zahlen
gesondert behandeln muss damit das Ergebnis nicht zu 0 überläuft, oder
man muss ein 9-Bit-Ergebnis liefern.
> Eine Rundung auf 0.5 zum Nächsten ist kaum sinnvoll da das "Raster"> trotzdem 1 bleibt.
Die gerundete Wurzel ist eine Abbildung w: |N → |N die sich über die
Minimierung des absoluten Fehlers definiert, d.h. es ist eine Funktion w
die folgendes erfüllt:
>> @ Johann L> Ich kann deine Art den Code zu schreiben mittlerweile zum Teil> lesen (denke ich(!?!?))
Bei dieser Routine bevorzuge ich, sie aus Makros zusammenzustöpseln weil
ich finde, daß sich damit die Übersichtlichkeit erhöht. In dieser
Diktion sieht der Algorithmus nämlich so aus:
1
ldi RES, 1 << 7
2
mul RES, RES
3
qstep 1 << 7
4
mul RES, RES
5
qstep 1 << 6
6
mul RES, RES
7
qstep 1 << 5
8
mul RES, RES
9
qstep 1 << 4
10
mul RES, RES
11
qstep 1 << 3
12
mul RES, RES
13
qstep 1 << 2
14
mul RES, RES
15
qstep 1 << 1
16
mul RES, RES
17
qstep 1 << 0
Das macht die Anatomie des Algorithmus' klar und ist Vorlage für sowohl
size-Optimierung, Portierung auf 32 Bits oder speed-Optimierung.
Dadurch, daß das qstep-Makro parametrisiert ist, sieht man auch
leichter, was bei einer Portierung zu tun ist (weniger oder garkeine
magischen Zahlen):
Die einfachste Version von qstep ist:
1
#define RES 23
2
#define QIN 24 // input
3
4
;; Das Ergebnis hat BB Bits d.h. es ist die Wurzel
5
;; aus einer Zahl mit 2*BB Bits zu berechnen.
6
#define BB 8
7
8
.macro qstep M
9
;; if (Qin >= R1:R0)
10
;; RES += M/2
11
;; else
12
;; RES -= M/2
13
cp QIN, R0
14
cpc QIN+1, R1
15
brsh 0f
16
subi RES, \M
17
0: subi RES, -\M/2
18
.endm
Die nächste Verfeinerung ist dann, diese Vergleiche smarter zu machen
und auszunutzen, daß das Multiplikationsergebnis u.U. low-Teil 0 hat:
1
.macro qstep M
2
;; if (Qin >= R1:R0)
3
;; RES += M/2
4
;; else
5
;; RES -= M/2
6
.if \M >= 1 << (BB/2)
7
;; low-Teil (R0) ist 0 nach MUL
8
cp QIN+1, R1
9
.else
10
cp QIN, R0
11
cpc QIN+1, R1
12
.endif
13
14
.if \M == 1
15
sbci RES, 0
16
0:
17
.else
18
brsh 0f
19
subi RES, \M
20
0: subi RES, -\M/2
21
.endif
22
.endm
Schliesslich fasst man die beiden ersten qsteps zusammen, um
Multiplikationen zu sparen:
1
.macro qstep M
2
.if \M == 1 << (BB-2)
3
ldi RES, 9 * \M/4
4
cpi QIN+1, \M
5
brsh 0f
6
ldi RES, \M/4
7
0: cp QIN+1, RES
8
brsh 0f
9
subi RES, \M
10
0: subi RES, -5 * \M/4
11
.else
12
13
.if \M >= 1 << (BB/2)
14
cp QIN+1, R1
15
.else
16
cp QIN, R0
17
cpc QIN+1, R1
18
.endif
19
20
.if \M == 1
21
sbci RES, 0
22
0:
23
.else
24
brsh 0f
25
subi RES, \M
26
0: subi RES, -\M/2
27
.endif
28
.endif
29
.endm
Spätestens hier wird klar, daß das hilfreich für eine 32-Bit Portierung
ist. Die erste Fallunterscheidung (hier für M = (1 << 6) = 64) schrumpft
die Implementierung schliesslich zu der Version mit 46 Ticks, wobei die
Ticks für avr-gcc und RET noch hinzukommen:
1
DEFUN sqrt16
2
qstep 1 << 6
3
mul RES, RES
4
qstep 1 << 5
5
mul RES, RES
6
qstep 1 << 4
7
mul RES, RES
8
qstep 1 << 3
9
mul RES, RES
10
qstep 1 << 2
11
mul RES, RES
12
qstep 1 << 1
13
mul RES, RES
14
qstep 1 << 0
15
;; for avr-gcc ABI
16
clr __zero_reg__
17
mov R24, RES
18
ret
19
ENDF sqrt16
> In den nächsten 2-3 Tagen würde ich den Code in einem neuen Thread> einstellen mit dann passender Überschrift und eine ausfühlichen
Hier der Thread tut's doch. Da hat man alles zusammen und es zerfasert
nicht. Kann man als OP nicht den Thread-Titel anpassen?
> Erklärung zu Prinzip und Wirkungsweise. Sowie ebenfalls in die> AVR-Arithmetik Ecke. Jedoch in reinen asm (mir is das auch lieber).>> Wenn du möchtest kannst du ja auch daraus Inlineassembler oder was> auch immer die Welt braucht machen.(ick würd wenn ick könnt, wa ;) )
Für die speed-Version würd ich ebenfalls Assembler bevorzugen, auch wenn
Inline-Assembler hier in einem C-Programm die letzten Ticks
zusammenkratzen würde weil kein Funktionsaufruf mehr notwendig ist.
Aber wer so weit gehen will, muss das bitte selber tun :-)
Einen 40-Instruktionen-Bandwurm in (ok, mit .macro wird's weniger) in
Inline-Assembler tu ich mir nicht an.
> Leider willst du eine 32bit Version ja nicht mehr optimieren.
Ich brauch keine Wurzel, noch nicht mal ne langsame. Für die 16-Bit
Version wollte ich nur mal sehen "was geht", und < 50 Ticks ist schon
erstaunlich ohne Nachguck-Tabelle.
Für die 32-Bit Version würde ich versuchen, den High-Teil des
Ergebnisses als Wurzel des High-Teils unter Verwendung der 16-Bit
Version vorauszuberechnen. Ich sehe aber noch nicht, wie man sich dann
wieder in den Algorithmus einklinkt weil der High-Teil des Ergebnisses
ja nach unten gerundet ist, d.h. u.U. um1 zu klein ist.
Spannender fände ich eine Fixpunkt-Version für 4.12 Q-Format, d.h. 12
Bit Nachkommastellen um auszuloten, ob man mit einem AVR in Echtzeit
Julia-Mengen auf eine Oszi-Röhre bekommt.
http://de.wikipedia.org/wiki/Julia-MengeLäubi .. schrieb:> Stell den code lieber direkt hier rein und die Erklärung ins Wiki, sonst> sind die infos wieder überall verstreut.
Das eine schliesst doch das andere nicht aus? Code und Erklärung würde
ich zusammen lassen und nicht auseinander reissen, d.h. Code und
Erklärung im Wiki und ggf. ein Link hierhin zu den leichtverderblichen
Sachen.
Marko Surup schrieb:> Also wenn du mir nicht mit Verbannung drohst,> würd ich das lieber so machen
Man muss es ja nicht über treiben ;)
Ich habe den Thread mal in das allgemeine Diskussionsforum verschoben,
dann kannst du einfach in der Codesammlung einen neuen Thread mit dem
(end) Ergebnis und passender Überschrift erstellen.
P.S. anmelden nicht vergessen, dann kann man eine gewisse zeit seine
Beiträge noch editieren.
Läubi .. schrieb:> Marko Surup schrieb:>> Also wenn du mir nicht mit Verbannung drohst,>> würd ich das lieber so machen> Man muss es ja nicht über treiben ;)>> Ich habe den Thread mal in das allgemeine Diskussionsforum verschoben,
hmmm... Hab mit schon den Wolf gesucht im Codesammlung-Forum :-/.
Könnte man nicht wenigstens einen Hinweis setzen, wenn Freds
rumgeschubst werden??
@Marko Surup
Für die 32-Bit-Version lande ich bei ca. 280 Ticks. Damit ist das
Verfahren im groben so schnell wie von Ruud v. Gessels in [[AVR
Arithmetik#Wurzel]]. An diesem Punkt sehe ich keinen Fortschritt weil
Ruud ohne MUL auskommt und das Verfahren nicht so verzwickt und kürzer
ist.
Für den Anfang der 32-Bit Routine kann man die 16-Bit Routine verwenden
wenn diese im letzten Schritt keine Operation mehr macht sondern
stattdessen das Carry mitliefert. Dies hab ich jedoch nicht
implementiert; es würde die Routine noch weiter verlangamen – was dann
auch auf die 16-Bit Version zuträfe, die man wiederverwenden will und
daher angepasst werden müsste (zB indem man im T-Flag übergibt, ob man
das Carry braucht oder die fertige Wurzel).
Läubi .. schrieb:> dann kannst du einfach in der Codesammlung einen neuen Thread mit dem> (end) Ergebnis und passender Überschrift erstellen.
Danke, in ein paar Tagen dann in der Codesammlung und in der
AVR-Arithmetik.
@
> Johann L.
Was bist du eigentlich für ein Windfähnchen und Blender. Würdest du
bitte aufhören dich in den Vordergrund zu spielen und dich mit meinen
Federn zu schmücken.Und was sollen diese Wichtigtuer-Matheerklärungen
die den Leser auch noch auf die falsche Fährte bringen.
Wenn hier einer meinen Algorithmus erklärt dann sollte ich das sein und
niemand der ihn nicht entwickelt hat. Also du.Irgendwie is dir mein Lob
zu Kopf gestiegen.
Johann L. schrieb:> wobei da noch nicht alles parametrisiert ist und daher noch magische> Zahlen auftauchen.> Damit bin ich wie gesagt bei 40 Instruktionen und 46 Ticks.
Du willst also meinen Algo als von dir schneller gemacht darstellen
obwohl er Rechenfehler hat und mit weiteren Parametern(?) versehen ist.
Die brauchen dann 0 Byte und 0 Sek? Damit versaust du mir schonmal mein
erstes Grundkonzept. Stabilität, Konsistenz und Transparenz.
Johann L. schrieb:>> Ich möchte noch hinzufügen das der Code nativ in Assembler geschrieben>> ist.>> Das gilt für meinen Code auch.
und warum kryptisiert du dann Anworten in zerrissenen Macros? Damit kann
man auch nur über Umwege was anfangen. Meine Posts sind direkt
einsetz-und testbar. Das hilft niemanden. Mein zweites Grundkonzept.
Nachvollziehbarkeit. Wolltest du das ichs nicht kapiere? Was mich gleich
zum nächsten Thema bringt:
Marko Surup schrieb:> Ich bin Anfänger im Code schreibenJohann L. schrieb:> So wie ich dich verstand hakt es bereits an den Basics?
Das scheint dich in den Glauben zu versetzten das ich keine Ahnung hab
und du änderst n paar Codezeilen(etwa 4) und dann denkt jeder "das hat
der Johann aber genial gemacht.
Ich bin seit 15 Jahren AVID-Editor und VFX-Artist. Ich gehöre zu den
Besten in Deutschland weil ich einfache, schnelle und nicht bekannte
Lösungen finde.In meiner Branche ist ein ungeschriebenes Gesetz, die
Arbeit eines Kollegen nicht ohne Absprache weiterzubenutzen. Als Respekt
vor der Leistung.(siehe lange Liste im Filmabspann).
Wie kommst du dazu meinen Algo (in deinem Schleifengewand) kryptisiert
mit lächerlichen 80 Takten und auch noch mit peinlichen 120 Takten in
die Arithmetik zu stellen ohne das mein eigener Algo/Code mit 47 Takten
zum Vergleich da steht???
Nicht mal ein Hinweis an mich darauf. Das mein Name druntersteht ist ja
wohl selbstverständlich und keines Dankes wert. Das gibt nur
Diskussionen und Verwirrung.
Du dokterst gerne an den Arbeiten anderer herum.Macht n schlauen
Eindruck,gel?!
Johann L. schrieb:> d.h. alle Nachkommastellen der Quadratwurzel werden abgeschnitten.
Ja ne is klar. Bitte nochmal den Algo studieren. Um was abzuschneiden
mit was drangewesen sein:
Fabian G. schrieb:>> Fabian G. schrieb:>>> Wie aufwendig wäre es eigentlich die Routine noch so abzuändern, dass>>> auf das letzte Bit gerundet wird?
Das war die Frage deine Antwort ist nur heisse Luft.
@ Fabian G. : eine brauchbare Lösung folgt nachdem der Hauptcode mit
Erklärung raus ist.
Johann L. schrieb:>> Ich kann deine Art den Code zu schreiben mittlerweile zum Teil>> lesen (denke ich(!?!?))
Das war keine Aufforderung. Soviel zum Vordergrund und der Eindruck das
es deins ist.
> In dieser> Diktion sieht der Algorithmus nämlich so aus:Johann L. schrieb:> Das macht die Anatomie des Algorithmus' klar und ist Vorlage für sowohl> size-Optimierung, Portierung auf 32 Bits oder speed-Optimierung.
Nochmal: Das ist MEIN Algo und du tust als ist es deiner.
Johann L. schrieb:> Die nächste Verfeinerung ist dann, diese Vergleiche smarter zu machen> und auszunutzen, daß das Multiplikationsergebnis u.U. low-Teil 0 hat:
Ist nich wahr!!!
Das hast Du aber genial gemacht.
Johann L. schrieb:>> Ne Optimierung deinerseits wäre ne Supersache. Aber wenn du das jetzt>> umsetzt machts mir keinen Spass mehr und ich kann auch nicht mehr sagen>> Nö, da hab ich keine Ambitionen.> Ich brauch keine Wurzel, noch nicht mal ne langsame.> Für die 32-Bit-Version lande ich bei ca. 280 Ticks.
Das tut mir leid!
> An diesem Punkt sehe ich keinen Fortschritt
Das auch!
Und warum willst du mir jetzt ne schwachsinnige 32bit Lösung vorschlagen
die mich nicht interessiert weil falsch im Ansatz? Denkst du, du bist
schlauer?
Entscheid dich mal.(oder besser bleib dabei)
Johann L. schrieb:> würd ich ebenfalls Assembler bevorzugen,> in Inline-Assembler tu ich mir nicht an.> Für die 32-Bit Version würde ich versuchen,> Bei dieser Routine bevorzuge ich, sie aus Makros zusammenzustöpseln
fällt dir was auf? Oder besser: fällt ICH was auf?
Zusammengefasst: Das ist mein Algo! Und du wirst immer als Optimizer
genannt sein.
Da werde ich persönlich für sorgen wo ich kann. Aber mehr auch nicht.
Ich gründe grad eine Firma und da möchte ich Klarheit schaffen.Das ist
ne Referenz. Nur darum hab ich meinen echten Namen dazugeschrieben.
@
> Läubi ..
sorry wenn ich hier mal vom Sachthema weg bin. Ist es möglich Punkt 7.2.
in der Arithmetik für ein paar Tage zu sperren. Um Irritationen zu
vermeiden.
Ich habe die Einträge in der Arithmetik gelöscht.
Besonders die C-Variante beweißt das die Wirkungsweise im Hinblick auf
das Verhalten von ALU´s und Mikroprozessoren im Allgemeinen vom Autor
nicht verstanden wurden.
Eine ausführliche Erklärung folgt dann im Wiki. Der Eintrag der beiden
Versionen Speed und/oder Size erfolgt dann wieder.
Marko Surup schrieb:> Ich habe die Einträge in der Arithmetik gelöscht.
Siehe unten...
> Besonders die C-Variante beweißt das die Wirkungsweise im Hinblick auf> das Verhalten von ALU´s und Mikroprozessoren im Allgemeinen vom Autor> nicht verstanden wurden.
Du wirst es wissen.
Bisher hatte ich eher nicht den Eindruck von Gjlayde, aber ich bin ja
nicht Jesus.
> Eine ausführliche Erklärung folgt dann im Wiki. Der Eintrag der beiden> Versionen Speed und/oder Size erfolgt dann wieder.
Wenn du nicht gerade wieder wegen irgendwas angepisst bist natürlich
nur.
---
Ich habe mir heute nacht mal den ganzen Thread angetan.
Meine Kurzzusammenfassung:
Erst kommt von dir etwas brauchbares, das geht dann eine Weile nett hin
und her und der Originalquelltext wird noch mal ein Stück verbessert.
Gjlayde setzt das dann in die Arithmetik-Rubrik, schreibt drunter, daß
das Original von dir stammt, erweitert das alles noch um die Einbindung
in avr-gcc (was wohl sinnvoll ist, weil ja nicht jeder alles in ASM
machen will), und du rastest aus.
Daraufhin wirst du ausfallend und löschst den von dir abgeleiteten Teil
plus den C-Teil von Gjlayde (!) kurzerhand aus dem Forum.
Ich weiß zwar nicht so recht warum du dich so aufregst, aber du wirst
schon einen Grund haben.
Trotzdem ist es eine ziemliche Dreistigkeit, neben der eigenen Arbeit
auch die anderer Leute aus dem Forum zu löschen.
Ich habe mir deshalb erlaubt, das wieder rückgängig zu machen.
Wenn etwas falsch ist, kannst du es ja korrigieren, klarstellen,
ergänzen oder was auch immer.
Eine konstruktive Diskussion (die es hier ja schon einige Zeit gab)
sieht jedenfalls anders aus, als das was du heute nacht getrieben hast.
Beleidigte Leberwurst spielen und mit der Schrotflinte hier zu löschen,
ist jedenfalls nicht angemessen.
Wenn du nicht willst, daß etwas an deinem Heiligtum
editiert/verbessert/verschlechtert wird, ohne daß dich jemand vorher
fragt, dann stelle es doch einen eigenen Server und mach hier einen Link
rein.
Vielleicht kann man ja wieder sinnvoller reden, wenn sich die Wogen in
ein paar Stunden geglättet haben?
Der Code ist nicht von Hochsprachen adaptierter. Compiler versagen voll
wenn man sie nicht von Hand darauf vorbereitet. Inlineassembler ist
machbar.
C-Version mit 120 Takten!!!! Muss ich noch was sagen.
Das alles und noch viel mehr würde ich gern mit meinem Originalcode (in
optimierter Version von Johann L.) erklären.
Der Code sieht simpel aus und ist es eigentlich auch, aber es gibt ein
paar Tricks.
Hat jemand meinen Code gesehen??? Er liegt immernoch auf meiner
Festplatte!
Nochmal:
Original 47 Takte
Sizeversion: 80 Takte
C-Version: 120 Takte ( und das hat nichts mit meinem Code zu tun)
!!!! Erst das Original, dann das Derivat !!!!
Ist das so schwer zu akzeptieren. Respekt vor der Leistung anderer.
Marko Surup schrieb:> Ist das so schwer zu akzeptieren. Respekt vor der Leistung anderer.
Gratuliere, wenn Du das Rad neu erfunden hast und Dich freust wie Bolle.
Aber wer zum Himmel braucht denn heute noch die Quadratwurzel aus 16Bit
int?
Wenn ich das schnell brauchen würde, würde ich einfach eine Tabelle im
Flash ablegen und fertg!
Willi schrieb:> Wenn ich das schnell brauchen würde, würde ich einfach eine Tabelle im> Flash ablegen und fertg!
Gewogen, gemessen und für nicht gut genug befunden.
Der nächste bitte...
Marko Surup schrieb:> C-Version mit 120 Takten!!!! Muss ich noch was sagen.
Da C i.a. verständlicher ist als Assembler, finde ich es eine gute Idee
von Johann, auch die C-Variante zur Veranschaulichung zur Verfügung zu
stellen. Hier geht es meines Erachtens weniger um die Takte (also
Geschwindigkeit), sondern eher um eine verständliche Präsentation des
Algorithmus.
Zu Deinem persönlichen Verhalten hier im Thread möchte ich besser nichts
sagen. Du kämst schlecht weg dabei. Dein "Aushängeschild" für Deine
zukünftige Firma hast Du Dir jedenfalls selbst kaputtgemacht. Im
Geschäftsleben ist nicht nur Fachkompetenz gefragt. Und außerhalb des
Fachs weist Du doch einige Schwächen auf...
Frank M. schrieb:> Da C i.a. verständlicher ist als Assembler, finde ich es eine gute Idee
Warum dann nicht gleich in Basic, Amateur!
Warum steht dann die Taktzahl drunter?
Nochmal: Ich sollte der erste sein. Danach die Ableger. Ich habe nur um
ein paar Tage gebeten mehr nicht. Dann wär alles gut!!!!
Mein Verhalten? Blablabla.... Ich verteidige mein geistiges Eigentum!
Ehre wem Ehre gebührt.
Aber damit haben Deutsche ja n Problem. Ich geh besser in die USA.
Der nächste bitte...
(Tendenz steht auf nichtbekanntgeben, braucht ja keiner)
Marko Surup schrieb:> Warum dann nicht gleich in Basic, Amateur!
Danke für die Bezeichnung "Amateur", Du amüsierst mich königlich :-)
Genau das meine ich: Du hältst Dich für den lieben Gott und alle anderen
für Dummköpfe. Du bist arrogant, anmaßend, selbstherrlich und bist auch
in anderen Gebieten der Sozialkompetenz eine absolute Nullnummer. Deine
mickrigen 16-Bit-Wurzeln interessieren mich und wahrscheinlich 99% der
anderen Leser hier einen Scheißdreck. Ich lese diesen Thread eigentlich
nur, weil ich es herrlich finde, wie ein kleiner Junge sich an 46 Takten
so dermaßen aufgeilen kann.
> Warum steht dann die Taktzahl drunter?
Vielleicht, um anzudeuten, dass dieser Algorithmus für C (und evtl. für
andere Hochsprachen auch) schlecht geeignet ist?
> Nochmal: Ich sollte der erste sein. Danach die Ableger. Ich habe nur um> ein paar Tage gebeten mehr nicht. Dann wär alles gut!!!!
Du willst der Gott sein, alles klar. Johann hat Dir protzendes Ungetüm
doch nur in seiner eher bescheidenen Art zugearbeitet, was willst Du
eigentlich? Soll sich hier nun die Gemeinde auf die Knie begeben und
Dich anbeten?
> Mein Verhalten? Blablabla.... Ich verteidige mein geistiges Eigentum!
Wo hat Dir jemand etwas "gestohlen"? Schreib erstmal ein Copyright in
Deinen Source und erkläre die Lizenzform Deines weltbewegenden Codes,
den kein Schwein braucht.
> Ehre wem Ehre gebührt.
Ehre spricht man sich nicht selbst zu. Sie wird einem zuteil. Und bis
dahin musst Du noch hart arbeiten. Ehre für eine höchst unportable
Assembler-Routine für einen 8-Bit-Prozessor, welcher in ein paar Jahren
obsolet ist? Etwas kleingeistig gedacht, denke ich. Dafür bekommt man
noch nichtmals einen Orden aus einem Kaugummiautomaten.
> Aber damit haben Deutsche ja n Problem. Ich geh besser in die USA.
Ja. Geh möglichst weit weg.
> Der nächste bitte...
Mit diesem Spruch, den Du hier wiederholt rausgelassen hast, demontierst
Du Dich hinunter bis zum Clown - nicht als Arzt, der meint, die
Dummköpfe hier im Forum "behandeln" zu müssen.
Marko Surup schrieb:> Nochmal: Ich sollte der erste sein. Danach die Ableger. Ich habe nur um> ein paar Tage gebeten mehr nicht. Dann wär alles gut!!!!
Irgendwie möchte ich nicht so recht glauben, dass dies noch die
nichteingelochte Person in Original ist.
Und wenn dem doch so ist: holt einen Arzt!
Hi
>Ich geh besser in die USA.
Möglichst schnell. Was meinst du, was mir in 30 Jahren
Assemblerprorammierung schon alles eingefallen ist. Dein geniales
Verfahren steht, wenn ich mich recht erinnere schon in 'Arithmetische
Algorithmen der Mikrorechentechnik' DDR/1989. Und selbst wenn nicht,
bist du mit Sicherheit nicht der erste, dem das eingefallen ist. Andere
machen nur nicht so ein Trara.
MfG Spess
@Marko Surup
Ich glaub du überschätzt dich und deine Leistung ganz schön. Du willst
hier als große Leistung rausstellen, dass bei deiner Berechnung die
Schleife aufgelöst wurde und die Vergleiche weggelassen wurden. Das man
sowas machen kann, um die Geschwindigkeit zu erhöhen, fand ich auch mal
ganz toll und es war ein echter Aha-Effekt als mir das mal jemand in
einem Assemblerprogramm für den Amiga 500 gezeigt hat. Allerdings ist
das nu schon fast 20 Jahre her.
@Marko Surup
Du bist doch ein logisch denkender Mensch. Da stimmst du mir doch
bestimmt zu, dass wenn so viele Leute anderer Meinung sind als du, das
es vielleicht doch möglich wäre, das sie im Recht sind und du nicht. Wir
können ja mal ganz demokratisch abstimmen. ;-)
Marko Surup schrieb:> Ich gehöre zu den> Besten in Deutschland weil ich einfache, schnelle und nicht bekannte> Lösungen finde.In meiner Branche ist ein ungeschriebenes Gesetz, die> Arbeit eines Kollegen nicht ohne Absprache weiterzubenutzen.
Klingt irgendwie nach Kindergarten.
Marko Surup schrieb:> C-Version mit 120 Takten!!!! Muss ich noch was sagen.
Ach Gottchen. Hast Du eigentlich schon mal etwas davon gehört, dass man
bei solchen Dingen meist einen Kompromiss aus Rechenzeitbedarf,
Platzbedarf, Entwicklungszeit, Wartbarkeit und Portabilität eingeht?
Irgendwelche extrem in eine Richtung optimierten Dinge zeugen in den
meisten Fällen von wenig oder keiner Erfahrung oder sind reine
Spielerei.
> Nochmal:> Original 47 Takte> Sizeversion: 80 Takte> C-Version: 120 Takte ( und das hat nichts mit meinem Code zu tun)>> !!!! Erst das Original, dann das Derivat !!!!>> Ist das so schwer zu akzeptieren. Respekt vor der Leistung anderer.
Du hast ja nicht mal Respekt vor anderen Personen. Wenn Du Deinen Code
für so genial hältst, dass den niemand "anrühren" darf, dann behalte ihn
doch einfach für Dich. Hier werden Dinge diskutiert, geholfen, erweitert
und verbessert, ganz im Sinne von offener Software. Solche Kinderkacke
"Mein Code, mein Code - rühr' den bloß nicht an!!1elf!!" will hier doch
keiner lesen.
Marko Surup schrieb:> Ich gründe grad eine Firma und da möchte ich Klarheit schaffen.Das ist> ne Referenz.
Ja, eine ganz tolle Referenz! Wenn ein potentieller Kunde Dein
Geschwafel hier liest, wird er einen großen Bogen um Deine Firma machen.
Ja.
Mit genau der Methode (Beim MSB beginnend abtesten ob das Quadrat der
bisherigen 'Wurzel' größer oder kleiner als die Ausgangszahl ist, haben
wir Anfang der 80-er Jahre auf einem Z-80 16 Bit Wurzeln gerechnet.
Und wenn es mir nicht zu blöd wäre, würde ich bei Knuth nachsehen, ob
das Verfahren (=der Algorithmus) bei ihm schon dokumentiert ist. AUs dem
Bauch heraus würde ich sagen "Ja, er ist." Solche Sachen haben das Zeug
dazu, von Donald Knuth oder jemandem in seinem Umfeld 'erfunden' worden
zu sein. Und wenn schon nicht von ihm selber, dann zumindest von
jemanden in diesem Zeitfenster: so um 1960
So weltbewegend neu ist dieser Algorithmus nicht. Die Umsetzung in
AVR-Assembler ist etwas worüber man reden kann. Die Sache mit den SUBI
ist clever gelöst, keine Frage. Allerdings hat das mit Algorithmen
nichts zu tun, sondern mit einer konkreten Implementierung eines
Algorithmuses.
Kleiner Hinweis: Vielleicht mal etwas strengere Massstäbe anlegen, was
ein Algorithmus ist und was dazu im Vergleich eine konkrete
Implementierung auf einem konkreten Prozessor darstellt. Beides ist
nicht identisch.
Marko Surup schrieb:> Ich geh besser in die USA.
Wär' mir neu daß in den USA jetzt bottom-feeder gesucht werden.
Und es hatte mich auch gewundert daß Johann L. (gjlayde) so lange Dein
arrogantes Rumgekaspere ertragen hat. Denke mal da war'n ziemlich großes
Stück Wohlwollen dahinter.
Marko Surup schrieb:> @>> Johann L.> Was bist du eigentlich für ein Windfähnchen und Blender. Würdest du> bitte aufhören dich in den Vordergrund zu spielen und dich mit meinen> Federn zu schmücken.
Wo soll das denn passiert sein. Im Wiki-Eintrag habe ich ganz klar
geschrieben, daß es sich um "eine größenoptimierte Version eines
Algorithmus' von Marko Surup" handelt mit Link zu diesem Thread.
> Johann L. schrieb:>> Damit bin ich wie gesagt bei 40 Instruktionen und 46 Ticks.> Du willst also meinen Algo als von dir schneller gemacht darstellen> obwohl er Rechenfehler hat und mit weiteren Parametern(?) versehen ist.
Die/der von mir — welchen Begriff darf ich denn nun verwenden, ohne daß
du Anstoß daran nimmst? — Implementierung? Code? Portierung?
Darstellung? Algorithmus? Anpassung? hatte keine Fehler. Bevor ich den
??? mit 46 Ticks hier einstellte, habe ich ihn für alle 2^16
Eingabewerte getestet.
> Johann L. schrieb:>> Marko Surup schrieb:>>> Ich möchte noch hinzufügen das der Code nativ in Assembler geschrieben>>> ist.>>>> Das gilt für meinen Code auch.> und warum kryptisiert du dann Anworten in zerrissenen Macros? Damit kann> man auch nur über Umwege was anfangen.
Es ist in GNU-Assembler geschrieben. Mit diesem ist der Code ohne Umwege
und direkt übersetzbar. Für mich ist das einfacher, als den Code wieder
für einen anderen Assembler rückzuübersetzen, zumal es nur eine
Arbeitsversion darstellt und ich den Wiki-Code in Inline-Assembler
gefasst habe, was bekannterweise GNU-as voraussetzt.
> Meine Posts sind direkt einsetz-und testbar.
Jepp. Meine auch. Copy & Paste in Assembler-Quelle, avr-as drüber und
fertig. Wenn du ohnehin eine Arbeitsversion in einem anderen Assembler
vorliegen hast, ist es das einfachste, diese zu modifizieren wenn du
Änderungen testen möchtest.
> Marko Surup schrieb:>> Ich bin Anfänger im Code schreiben> Johann L. schrieb:>> So wie ich dich verstand hakt es bereits an den Basics?> Das scheint dich in den Glauben zu versetzten das ich keine Ahnung hab
Mein Zitat ist hier vollkommen aus dem Zusammenhang gerissen, denn es
bezog sich auf den von dir verlinkten Artikel, in dem du Probleme mit
rad-Verwendung erwähntest sowie die "relevante Formel" zu lokalisieren:
Marko Surup schrieb:> 1. Ich denke ich tue mich mit der rad- Benutzung schwer.> 2. Welche ist die entscheidende Formel vor Taylor? (Gl 4.5)?> ...> Mach mich klug ;)> und du änderst n paar Codezeilen(etwa 4) und dann denkt jeder "das hat> der Johann aber genial gemacht.
Vor Anfangs 63 Ticks zu 46 sind's bestimmt mehr als 4 Zeilen gewesen.
Aber egal. Wolltest du nun Tipps zur Implementierung oder nein oder
was? Sorry daß ich die überflüssigen MOVW oder CPC erwähnt habe.
> Ich gehöre zu den Besten in Deutschland weil ich einfache,> schnelle und nicht bekannte Lösungen finde.In meiner Branche ist ein> ungeschriebenes Gesetz, die Arbeit eines Kollegen nicht ohne Absprache> weiterzubenutzen. Als Respekt vor der Leistung.
Wo bitte ist das in diesem Thread oder im Wiki-Artikel passiert? Wenn
dir die Stelle im Wiki nicht prominent genug oder nicht fett genug oder
nicht oft genug ist, dann füg es an der für dich passenden Stelle hinzu!
Gleiches gilt für andere Versionen ob nach speed oder Farbe oder wie
auch immer optimiert.
> Wie kommst du dazu meinen Algo (in deinem Schleifengewand) kryptisiert> mit lächerlichen 80 Takten und auch noch mit peinlichen 120 Takten in> die Arithmetik zu stellen ohne das mein eigener Algo/Code mit 47 Takten> zum Vergleich da steht???
In Gottes Namen dann mach die heiligen Zeilen doch dazu! Es ist eine auf
Größe optimierte Version und mit 10 Instruktionen ist sie eben kürzer
als deine mit 47.
Die 120 Ticks der C-Version sind nicht peinlich sondern das, was für
diese einfache, exemplarische C-Variante gemessen wurde. Nicht mehr und
nicht weniger.
> Nicht mal ein Hinweis an mich darauf. Das mein Name druntersteht ist ja> wohl selbstverständlich und keines Dankes wert. Das gibt nur> Diskussionen und Verwirrung.
Ja was denn nun? Nennung oder keine?
> Johann L. schrieb:>> d.h. alle Nachkommastellen der Quadratwurzel werden abgeschnitten.> Ja ne is klar. Bitte nochmal den Algo studieren. Um was abzuschneiden> mit was drangewesen sein:
Großen Missverständnis. Das Ergebnis deines Algorithms' lässt sich
angeben als "Quadratwurzel, Nachkommastellen abgeschnitten". Wie
dieses Ergebnis berechnet wird ist völlig offen, die Umschreibung ist
lediglich ein "as if" und macht keine Aussage darüber, of die
weggeworfenen Stellen je berechnet wurden oder nicht. Die z.B:
Spezifikation von IEEE-konformer Arithmetik. Anders wäre sowas
überhaupt nicht sinnvoll zu spezifizieren.
> Zusammengefasst: Das ist mein Algo!
Sehe ich 100% wie
Karl Heinz Buchegger schrieb:> Mit genau der Methode (Beim MSB beginnend abtesten ob das Quadrat der> bisherigen 'Wurzel' größer oder kleiner als die Ausgangszahl ist, haben> wir Anfang der 80-er Jahre auf einem Z-80 16 Bit Wurzeln gerechnet.>> Und wenn es mir nicht zu blöd wäre, würde ich bei Knuth nachsehen, ob> das Verfahren (=der Algorithmus) bei ihm schon dokumentiert ist. Aus dem> Bauch heraus würde ich sagen "Ja, er ist." Solche Sachen haben das Zeug> dazu, von Donald Knuth oder jemandem in seinem Umfeld 'erfunden' worden> zu sein. Und wenn schon nicht von ihm selber, dann zumindest von> jemanden in diesem Zeitfenster: so um 1960
Bestimmt schon früher. Zuse verwendete in seiner Z3 zB das Verfahren wie
beim schriftlichen Wurzelziehen. Das Problem, Quadratwurzeln
numerisch/schriftlich zu berechnen lässt sich bis in die Antike
zurückverfolgen.
Das Verfahren ist ähnlich dem, wie es beim schriftlichen Wurzelziehen
angewandt wird. Dort versucht man Multiplikationen zu vermeiden und
verwendet dazu die binomischen Formeln. Für die hier vorliegenden Fall
mit Hardware-Multiplier stört eine Multiplikation natürlich nicht.
Ansonsten gibt es das Verfahren bis auf Details der Umsetzung in
http://www.dattalo.com/technical/theory/sqrt.html (Another Iterative
Algorithm)
und bestimmt in zig anderen Stellen wenn man nicht nur den ersten
Google-Treffer nennt.
...oder ganz ohne Multiplikation, indem nur die Differenz zum vorherigen
Produkt mitgeführt wird. Exemplarisch in einer C-Formulierung der
Quadratwurzel, wie sie auf einem Abakus berechnet wurde:
http://medialab.freaknet.org/martin/src/sqrt/sqrt.cKarl Heinz Buchegger schrieb:> So weltbewegend neu ist dieser Algorithmus nicht. Die Umsetzung in> AVR-Assembler ist etwas worüber man reden kann. Die Sache mit den SUBI> ist clever gelöst, keine Frage. Allerdings hat das mit Algorithmen> nichts zu tun, sondern mit einer konkreten Implementierung eines> Algorithmuses.>> Kleiner Hinweis: Vielleicht mal etwas strengere Massstäbe anlegen, was> ein Algorithmus ist und was dazu im Vergleich eine konkrete> Implementierung auf einem konkreten Prozessor darstellt. Beides ist> nicht identisch.Frank M. schrieb:> Marko Surup schrieb:>> C-Version mit 120 Takten!!!! Muss ich noch was sagen.>> Da C i.a. verständlicher ist als Assembler, finde ich es eine gute Idee> von Johann, auch die C-Variante zur Veranschaulichung zur Verfügung zu> stellen. Hier geht es meines Erachtens weniger um die Takte (also> Geschwindigkeit), sondern eher um eine verständliche Präsentation des> Algorithmus.
100% richtig erkannt :-)
Ob es in C oder C++ oder Lisp oder BASIC oder Pseudocode steht, ist
durch Wurscht.
Wenn dich die Angabe der Ticks stört, dann entferne sie eben. Und mache
deinen Algorithmus dazu und verbessere den Eintrag wenn du möchtes. Oder
schmolle in der Ecke oder was auch immer, aber beleidige nicht andere
Forenteilnehmen oder unterstelle ihnen Unlautere Motive oder Ideenklau
von Algorithmen, die wahrscheinlich schon die alten Babylonier kannten.
Ansonsten bin ich durch mit dem Thema, bevor ich noch für Herzinfarkte
oder andere bleibende Schäden verantwortlich gemacht werde.
Ist halt dumm, wenn man gerade entdeckt hat, daß die Erde keine Scheibe
ist, aber alle Anderen wissen's schon.
Das führt zu nervösen Reaktionen in der Eingewöhnungsphase. Aber das
gibt sich.
Thread beobachten
Seitenaufteilung abschalten