An die Mathematiker / Informatiker: Spirograph ohne Gleitkomma

[Ralph S. (jjflash)]

Nachdem ich jetzt Ewigkeiten Dateien gesichtet und gesäubert habe, 
Ordner neu sortiert, Doku's zu meinen Projekten geschrieben und 
Schaltpläne gezeichnet habe mußte jetzt etwas programmieren zur 
Entspannung her.

Also habe ich mir die Aufgabe gestellt, endlich einmal einen 
Spirographen für kleine Spielereien auf einem Mikrocontroller ohne 
Gleitkommaunterstützung zu machen (so entspannt war es nicht, weil ich 
endlich auch ein ST7789 Display sauber an einem CH32V003 zum Laufen 
bringen wollte und das SPI hierfür etwas gezickt hat, bis ich ie 
richtige Einstellung hierfür gefunden hatte).

Der Hintergrund also ist, dass das auf einem Controller mit sehr wenig 
Flash (V003 hat nur 16 kByte) laufen soll und ein Aufruf der 
Sinusfunktion aus math.h schon alleine nicht in den Speicher passt. Dann 
habe ich eine Lösung für einen komfortableren Spirographen, der mit 
Festkommaarithmetik aber Sinus berechnet, aber im Spirographen dann doch 
Gleitkomma benötigt.

Also mal das Hirn anstrengen und überlegen wie das im Flash knapper geht 
(soll ja auch im CH32V003 noch laufen).

Das Ergebnis kann man in der angehängten Source sehen. Sinus wird aus 
einer LookUp-Tabel entnommen und der Spirograph wird hieraus gefüttert. 
Display hat hier Auflösung 240x240.

Eine Erhöhung der scale in der LookUp-Table von 3 auf 4 feste 
Nachkommastellen bringt keine Verbesserung der Qualität des Graphen.

Insgesamt benötigt der Spirograph inkl. eines einzelnen Aufrufs 740 Byte 
im Speicher (inkl. der LookUp-Table die alleine schon 180 Byte 
benötigt).

Jetzt weiß ich, dass manche Informatiker / Mathematiker nahezu magische 
Fähigkeiten haben sehr ausgefeilte Methoden zu präsentieren.

Hier jetzt die Frage an die Mathematiker / Informatiker: Das geht doch 
bestimmt noch kürzer, vllt. ohne LookUp-Table, oder ?

[Klaus W. (mfgkw)]

CORDIC ist wohl das richtige Stichwort zum Suchen.
Aber da ist man mit den Datentypen schon recht eingeschränkt, und ob es 
unterm Strich kürzer wird, ist nicht gesagt. Nur etwas schneller 
vielleicht und viel aufwendiger auf jeden Fall.

[Bruno V. (bruno_v)]

Keine Ahnung, was Spirographen sind oder wie sie sich berechnen.

Aber wenn der Sinus nur zur Kreisberechnung da ist, dann gäbe es was mit 
Pythagoras und dann weiter optimiert mit Bresenham und Auflösung der 
Quadrat/Wurzelrechnung:
https://de.wikipedia.org/wiki/Bresenham-Algorithmus#Kreisvariante_des_Algorithmus

(ist grade Thema in Beitrag "Kleine c-routine um auf Pixelbasis Kreise und Striche zu zeichnen" und 
zerfällt für Kreise in absurd kleine und schnelle Codeschnipsel)

[Ralph S. (jjflash)]

... ich sollte manchmal mehr in digitalen Zahlen denken: Wenn man die 
LookUp-Table nicht auf 1000 skaliert, sondern auf 1024 kann im 
Spirographen die Division / 1000 eingespart werden (in Ermangelung einer 
Multiplikations- Divisionseinheit in der CPU des CH32V003), kann dann 
durch eine Schiebeoperation >> 10 die Division durch 1024 erfolgen und 
die Division muß nicht in Software gemacht werden. Ergebnis ist dann, 
dass der Spirograph im Flash dann 708 Byte benötigt.

[Torsten B. (butterbrotstern)]

Sehr schön, die nächste Frage ist dann, ob die 90° eine so kluge Wahl 
sind.
128 oder gleich 256 liegen da ganz in der Nähe.

[Ralph S. (jjflash)]

Torsten B. schrieb:
> Sehr schön, die nächste Frage ist dann, ob die 90° eine so kluge Wahl
> sind.
> 128 oder gleich 256 liegen da ganz in der Nähe.

na ja, doch, 90° sind da schon in Ordnung (glaube ich), denn aus diesen 
90° kann man leicht den kompletten Sinus abbilden. Zudem bräuchte man 
hier dann 128 16-Bit Werte in der LookUp, was 72 Byte mehr wären, zudem 
komplizierter zu rechnen. Außerdem geschieht mit der 90, 180, 270, 360 
nur Additionen und das kann der RiscV-Kern (wie jede andere CPU auch) 
natürlich und man hat dann dadurch keinen Vorteil.

By the way: Cordic habe ich gerade ausprobiert (benötigt dann eine 
Arcus-Tangens-Tabelle), die wohl vom Ansatz her - bis jetzt - vllt. 70 
Byte kleiner ist, aber ich mache da wohl noch einen Fehler, denn es 
funktioniert noch nicht. Ich geh jetzt schlafen, gehabts euch wohl.

[Rainer W. (rawi)]

Bruno V. schrieb:
> Keine Ahnung, was Spirographen sind oder wie sie sich berechnen.

Dem kann abgeholfen werden:

https://de.wikipedia.org/wiki/Spirograph_(Spielzeug)

[Gunnar F. (gufi36)]

Klasse! Das erinnert mich an meine Kindheit, mit sechs hatte ich so 
einen. Das heißt, die meisten Teile habe ich noch immer, nur nicht mehr 
damit gespielt. Aber jetzt geht das ja nochmal viel schöner!

[Ralph S. (jjflash)]

Gunnar F. schrieb:
> Klasse! Das erinnert mich an meine Kindheit, mit sechs hatte ich
> so
> einen. Das heißt, die meisten Teile habe ich noch immer, nur nicht mehr
> damit gespielt. Aber jetzt geht das ja nochmal viel schöner!

:-) mittlerweile gibt es die verrücktesten Konstruktionen für 
Spielzeug-Spirographen.

Ob das jetzt viel schöner geht? Mag ich mich nicht zwingend befürworten. 
Letzens habe ich mit der Enkelin meiner Frau mit so etwas gespielt und 
das "analoge Spirographen" hatte eben auch etwas: Ganz ohne Strom, ganz 
ohne Rechnertechnik.

[Norbert (der_norbert)]

Ralph S. schrieb:
> Letzens habe ich mit der Enkelin meiner Frau mit so etwas gespielt und
> das "analoge Spirographen" hatte eben auch etwas: Ganz ohne Strom, ganz
> ohne Rechnertechnik.

Und – was noch viel wichtiger ist – die Kinder können es im wahrsten 
Sinne des Wortes ›begreifen‹ und die Linien selbst malen.

[Georg S. (randy)]

Ralph S. schrieb:
> By the way: Cordic habe ich gerade ausprobiert (benötigt dann eine
> Arcus-Tangens-Tabelle), die wohl vom Ansatz her - bis jetzt - vllt. 70
> Byte kleiner ist, aber ich mache da wohl noch einen Fehler, denn es
> funktioniert noch nicht. Ich geh jetzt schlafen, gehabts euch wohl.

Ich hab mal einen Cordic programmiert und festgestellt dass die meisten 
Anleitungen gern bei einigen Details ungenau sind (off-by-one Fehler 
u.ä.).
Eine gute Anleitung die ich gefunden habe:
https://1uffakind.com/pdf/CORDICForDummies.pdf

Und der Source Code:
https://gitlab.com/dg6rs/polar/-/blob/master/Src/polar_mod.c?ref_type=heads
In der Datei polar_mod.c ab Zeile 664 (Funktion: cordic)
Die Variablen sind alle int32. Der Winkel ist skaliert mit: 16777216 
entspricht einem Vollkreis (360 Grad).
Die Längen (x,y und out_abs) sind alle in "pixel", also ohne explizite 
Einheit.

[Georg S. (randy)]

Ralph S. schrieb:
> Ob das jetzt viel schöner geht? Mag ich mich nicht zwingend befürworten.
> Letzens habe ich mit der Enkelin meiner Frau mit so etwas gespielt und
> das "analoge Spirographen" hatte eben auch etwas: Ganz ohne Strom, ganz
> ohne Rechnertechnik.

Gute Idee. Sowas muss ich meinem 5-jährigen zu Weihnachten besorgen.