Forum: Mikrocontroller und Digitale Elektronik AVR: 16bit Quadratwurzel in 63 Takten, fsqrt16.asm


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 Marko S. (markosurup)


Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
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 ;)

: Verschoben durch User
von Marko S. (markosurup)


Bewertung
0 lesenswert
nicht lesenswert
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

von raketenfred (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Ich kann leider kein ASM- aber wenn ich deinen Text richtig verstanden 
habe- ist deine Wurzelroutine, der "Binären Suche" ähnlich?

von Marko Surup (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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.

von Johann L. (gjlayde) Benutzerseite


Bewertung
0 lesenswert
nicht lesenswert
Ich kann schon mal bestätigen, daß der Algorithmus korrekt ist :-)

Meine Portierung für avr-gcc sieht momentan so aus:

C-Teil
#include <stdint.h>

extern uint8_t sqrt16_floor (uint16_t);

ASM-Teil
#define __zero_reg__ 1
#define __tmp_reg__ 0

.macro DEFUN name
.global \name
.func \name
\name:
.endm

.macro ENDF name
.size \name, .-\name
.endfunc
.endm

.text

#define RES R23
#define QIN 24 // input

.macro qstep M
.if \M == 128
    cpi QIN+1, hi8(16384)
.else
    cp  QIN,   R0
    cpc QIN+1, R1
.endif
    
.if \M == 1
    sbci RES, 0 
.else
    brsh 0f
    subi RES, \M
0:  subi RES, -\M/2
.endif
.endm

DEFUN sqrt16_floor
    ldi     RES, 128
    qstep 128
    mul     RES, RES
    qstep 64
    mul     RES, RES
    qstep 32
    mul     RES, RES
    qstep 16
    mul     RES, RES
    qstep 8
    mul     RES, RES
    qstep 4
    mul     RES, RES
    qstep 2
    mul     RES, RES
    qstep 1
    clr     __zero_reg__
    mov R24, RES    
    ret
ENDF sqrt16_floor

#undef RES
#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.

von Marko Surup (Gast)


Bewertung
0 lesenswert
nicht lesenswert
> 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?

von Marko Surup (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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.

von Johann L. (gjlayde) Benutzerseite


Bewertung
0 lesenswert
nicht lesenswert
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
  ldi     r23, 0x80 
  cpi     r25, 0x40 
  brcc    .+2       
  subi    r23, 0x80 
  subi    r23, 0xC0 
  mul     r23, r23
  cp      r24, r0
  cpc     r25, r1
  brcc    .+2       
  subi    r23, 0x40 
  subi    r23, 0xE0 
  mul     r23, r23
  cp      r24, r0
  cpc     r25, r1
  brcc    .+2       
  subi    r23, 0x20 
  subi    r23, 0xF0 
  mul     r23, r23
  cp      r24, r0
  cpc     r25, r1
  brcc    .+2       
  subi    r23, 0x10 
  subi    r23, 0xF8 
  mul     r23, r23
  cp      r24, r0
  cpc     r25, r1
  brcc    .+2       
  subi    r23, 0x08 
  subi    r23, 0xFC 
  mul     r23, r23
  cp      r24, r0
  cpc     r25, r1
  brcc    .+2       
  subi    r23, 0x04 
  subi    r23, 0xFE 
  mul     r23, r23
  cp      r24, r0
  cpc     r25, r1
  brcc    .+2       
  subi    r23, 0x02 
  subi    r23, 0xFF 
  mul     r23, r23
  cp      r24, r0
  cpc     r25, r1
  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.

von Marko S. (markosurup)


Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
@ 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.

von Johann L. (gjlayde) Benutzerseite


Bewertung
0 lesenswert
nicht lesenswert
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
   ldi     r23, 128 
   cpi     r25, 64 
   brsh    0f
   subi    r23, 128 
0: subi    r23, -64 

geht
   ldi     r23, 192
   cpi     r25, 64 
   brsh    0f
   ldi     r23, 64
0:

Denn in C-Notation ist beides
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.

von Johann L. (gjlayde) Benutzerseite


Bewertung
0 lesenswert
nicht lesenswert
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):
#define RES  23
#define QIN  24 // input
#define MASK 22

; R24 = sqrt16 (R25:R24)
; clobbers: R22, R23, __tmp_reg__

sqrt16_floor_size:
    ldi MASK, 128
    clr RES
0:  add RES, MASK
    mul RES, RES
    cp  QIN,   R0
    cpc QIN+1, R1
    brsh 1f
    sub RES, MASK
1:  lsr MASK
    brne 0b
    clr __zero_reg__
    mov R24, RES    
    ret

von Marko S. (markosurup)


Bewertung
0 lesenswert
nicht lesenswert
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.

von Johann L. (gjlayde) Benutzerseite


Bewertung
0 lesenswert
nicht lesenswert
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.

von Marko S. (markosurup)


Bewertung
0 lesenswert
nicht lesenswert
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 ;)

von Johann L. (gjlayde) Benutzerseite


Bewertung
0 lesenswert
nicht lesenswert
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"?

von Stephan H. (stephan-)


Bewertung
0 lesenswert
nicht lesenswert
na dann wartet mal bis sich der PeDa meldet. Da bin ich gepsannt.

von Marko S. (markosurup)


Bewertung
0 lesenswert
nicht lesenswert
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 :)

von Johann L. (gjlayde) Benutzerseite


Bewertung
0 lesenswert
nicht lesenswert
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. :-(

von Marko S. (markosurup)


Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
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.

von Marko S. (markosurup)


Bewertung
0 lesenswert
nicht lesenswert
!!!Letzte Post bitte ignorieren, falscher Code!!!!

von Johann L. (gjlayde) Benutzerseite


Bewertung
0 lesenswert
nicht lesenswert
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.

von Marko S. (markosurup)


Bewertung
0 lesenswert
nicht lesenswert
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

von Marko S. (markosurup)


Bewertung
0 lesenswert
nicht lesenswert
Bin bei 50 Takten. frustrierend... mein eigener Algorithmus verarscht 
mich

von Thomas O. (kosmos)


Bewertung
0 lesenswert
nicht lesenswert

von Marko Surup (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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.

von MWS (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Thomas O. schrieb:
> hier gibts auch ein paar Infos dazu
> http://www-user.tu-chemnitz.de/~heha/Mikrocontroll...

Thomas,

danke für den interessanten Link.

von Johann L. (gjlayde) Benutzerseite


Bewertung
0 lesenswert
nicht lesenswert
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
    qstep 1 << 6
    mul     RES, RES
    qstep 1 << 5
    mul     RES, RES
    qstep 1 << 4
    mul     RES, RES
    qstep 1 << 3
    mul     RES, RES
    qstep 1 << 2
    mul     RES, RES
    qstep 1 << 1
    mul     RES, RES
    qstep 1 << 0
    ;; for avr-gcc ABI
    clr     __zero_reg__
    mov R24, RES    
    ret

Wobei die Logik im qstep-Makro steckt. Das erste qstep expandiert zu
    ldi  RES,   hi8 (9*\M*\M)
    cpi  QIN+1, hi8 (4*\M*\M)
    brsh 0f
    ldi  RES,   hi8 (\M*\M)
0:  cp   QIN+1, RES
    brsh 0f
    subi RES,  64
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)
.if \M >= 16
    cp  QIN+1, R1
.else
    cp  QIN,   R0
    cpc QIN+1, R1
.endif
    
.if \M == 1
    sbci RES, 0 
.else
    brsh 0f
    subi RES, \M
0:  subi RES, -\M/2
.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.

von Fabian G. (kjion) Benutzerseite


Bewertung
0 lesenswert
nicht lesenswert
Wie aufwendig wäre es eigentlich die Routine noch so abzuändern, dass 
auf das letzte Bit gerundet wird?

von Marko S. (markosurup)


Bewertung
0 lesenswert
nicht lesenswert
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

von Läubi .. (laeubi) Benutzerseite


Bewertung
0 lesenswert
nicht lesenswert
Stell den code lieber direkt hier rein und die Erklärung ins Wiki, sonst 
sind die infos wieder überall verstreut.

von Marko Surup (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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.

von Fabian G. (kjion) Benutzerseite


Bewertung
0 lesenswert
nicht lesenswert
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.

von Johann L. (gjlayde) Benutzerseite


Bewertung
0 lesenswert
nicht lesenswert
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:
    ldi     RES, 1 << 7
    mul     RES, RES
    qstep 1 << 7
    mul     RES, RES
    qstep 1 << 6
    mul     RES, RES
    qstep 1 << 5
    mul     RES, RES
    qstep 1 << 4
    mul     RES, RES
    qstep 1 << 3
    mul     RES, RES
    qstep 1 << 2
    mul     RES, RES
    qstep 1 << 1
    mul     RES, RES
    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:
#define RES 23
#define QIN 24 // input

;; Das Ergebnis hat BB Bits d.h. es ist die Wurzel
;; aus einer Zahl mit 2*BB Bits zu berechnen.
#define BB 8

.macro qstep M
;; if (Qin >= R1:R0)
;;    RES += M/2
;; else
;;    RES -= M/2
    cp  QIN,   R0
    cpc QIN+1, R1
    brsh 0f
    subi RES, \M
0:  subi RES, -\M/2
.endm

Die nächste Verfeinerung ist dann, diese Vergleiche smarter zu machen 
und auszunutzen, daß das Multiplikationsergebnis u.U. low-Teil 0 hat:
.macro qstep M
;; if (Qin >= R1:R0)
;;    RES += M/2
;; else
;;    RES -= M/2
.if \M >= 1 << (BB/2)
    ;; low-Teil (R0) ist 0 nach MUL
    cp  QIN+1, R1
.else
    cp  QIN,   R0
    cpc QIN+1, R1
.endif
    
.if \M == 1
    sbci RES, 0 
0:  
.else
    brsh 0f
    subi RES, \M
0:  subi RES, -\M/2
.endif
.endm

Schliesslich fasst man die beiden ersten qsteps zusammen, um 
Multiplikationen zu sparen:
.macro qstep M
.if \M == 1 << (BB-2)
    ldi  RES,   9 * \M/4
    cpi  QIN+1, \M
    brsh 0f
    ldi  RES,   \M/4
0:  cp   QIN+1, RES
    brsh 0f
    subi RES,   \M
0:  subi RES,   -5 * \M/4
.else

.if \M >= 1 << (BB/2)
    cp  QIN+1, R1
.else
    cp  QIN,   R0
    cpc QIN+1, R1
.endif
    
.if \M == 1
    sbci RES, 0 
0:  
.else
    brsh 0f
    subi RES, \M
0:  subi RES, -\M/2
.endif
.endif
.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:
DEFUN sqrt16
    qstep 1 << 6
    mul     RES, RES
    qstep 1 << 5
    mul     RES, RES
    qstep 1 << 4
    mul     RES, RES
    qstep 1 << 3
    mul     RES, RES
    qstep 1 << 2
    mul     RES, RES
    qstep 1 << 1
    mul     RES, RES
    qstep 1 << 0
    ;; for avr-gcc ABI
    clr     __zero_reg__
    mov R24, RES    
    ret
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-Menge

Lä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.

von Läubi .. (laeubi) Benutzerseite


Bewertung
0 lesenswert
nicht lesenswert
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.

von Johann L. (gjlayde) Benutzerseite


Bewertung
0 lesenswert
nicht lesenswert
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).

von Marko S. (markosurup)


Bewertung
0 lesenswert
nicht lesenswert
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 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 
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.

von Marko S. (markosurup)


Bewertung
0 lesenswert
nicht lesenswert
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.

von Klaus W. (mfgkw)


Bewertung
0 lesenswert
nicht lesenswert
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?

von Klaus W. (mfgkw)


Bewertung
0 lesenswert
nicht lesenswert
PS für die Mitleser, damit nicht jeder suchen muß:
Es geht um http://www.mikrocontroller.net/articles/AVR_Arithmetik

von Marko Surup (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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.

von Willi (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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!

von Marko Surup (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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...

von Frank M. (ukw) (Moderator) Benutzerseite


Bewertung
0 lesenswert
nicht lesenswert
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...

von Marko Surup (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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)

von Hans (Gast)


Bewertung
0 lesenswert
nicht lesenswert
> Ich verteidige mein geistiges Eigentum!

LOL :)

> Ich geh besser in die USA.

Winke! Winke!

von Frank M. (ukw) (Moderator) Benutzerseite


Bewertung
0 lesenswert
nicht lesenswert
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.

von Willi (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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!

von spess53 (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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

von ... (Gast)


Bewertung
0 lesenswert
nicht lesenswert
@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.

von Marko Surup (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Alles klar. Und Tschüsss...!,,

von ... (Gast)


Bewertung
0 lesenswert
nicht lesenswert
@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. ;-)

von uwe (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Nennt sich Sukzessive Approximation

von Gastino G. (gastino)


Bewertung
0 lesenswert
nicht lesenswert
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.

von Karl H. (kbuchegg) (Moderator)


Bewertung
0 lesenswert
nicht lesenswert
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.

von MWS (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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.

von Klaus W. (mfgkw)


Bewertung
0 lesenswert
nicht lesenswert
Der macht wohl schon lange sinnvollere Dinge, z.B. die avr-gcc-Bugs 
aktualisieren.

von Johann L. (gjlayde) Benutzerseite


Bewertung
0 lesenswert
nicht lesenswert
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.c

Karl 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.

von MWS (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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.

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]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [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.