Forum: Compiler & IDEs Mathematiker vor: sqrt() mit Hilfe von sin() und atan2() "emulieren"


von Karl Kurzschluss (Gast)


Lesenswert?

Angenommen, ich habe nur die Math-Funktionen sin() und atan2() zur 
Verfügung. Kann ich mir damit ein sqrt() "basteln"?

von Sven B. (scummos)


Lesenswert?

Gefühlt eher nicht. Das trigonometrische und das gebrochenrationale Zeug 
ist ziemlich verschieden von der Struktur her.

von H. K. (spearfish)


Lesenswert?

Warum gehst du nicht einen, dokumentieren, Standardweg? Gibt doch 
genügend Algorithmen, wie man eine sqrt-Funktion implementieren kann, je 
nach Anforderungen.

Oder anders gefragt: Wofür brauchst du es denn?

von lalala (Gast)


Lesenswert?

Karl Kurzschluss schrieb:
> Angenommen, ich habe nur die Math-Funktionen sin() und atan2() zur
> Verfügung. Kann ich mir damit ein sqrt() "basteln"?

Hausaufgabe? Dann vermutlich ja. Ansonsten vermutlich nicht.

von Hp M. (nachtmix)


Lesenswert?

Wird wohl auf so etwas hinauslaufen: 
https://de.wikipedia.org/wiki/CORDIC

von M.N. (Gast)


Lesenswert?

Naiver Ansatz:

sin²x + cos²x = 1
sin²x = 1 - cos²x
sin x = sqrt(1 - cos² x)

jetzt "nur" noch (1 -cos²x) nach x auflösen und in sin x einsetzen.

von Karl Kurzschluss (Gast)


Lesenswert?

Danke, so weit war ich auch schon. ;)

Ich brauche das Ganze, um Platz zu sparen. asin() habe ich z.B. schon 
ersetzt, es hat gleich mal 100 Bytes gebracht...

...mein Gefühl sagt mir auch, dass ich gewisse Grundfunktionen brauche 
und sqrt() dazu gehört und es sich nicht ersetzen lässt. Daher die 
Frage, ob noch einer eine Idee hat. Könnte ja sein...
(es sind wirklich nur mathematische Umformungen gesucht, keine 
Näherungen)

von Mathegenie (Gast)


Lesenswert?

Karl Kurzschluss schrieb:
> ...mein Gefühl sagt mir auch, dass ich gewisse Grundfunktionen brauche
> und sqrt() dazu gehört und es sich nicht ersetzen lässt.

Man sollte nie seinem Gefühl vertrauen.

Mein Wissen sagt mir, dass es auch allein mit den Operationen + - * / 
geht.

Oder noch einfacher, du brauchst nichts außer der NAND-Funktion!

von Karl Kurzschluss (Gast)


Lesenswert?

...wie gesagt, keine Näherungen...

von Johann L. (gjlayde) Benutzerseite


Lesenswert?

Karl Kurzschluss schrieb:
> Danke, so weit war ich auch schon. ;)
>
> Ich brauche das Ganze, um Platz zu sparen. asin() habe ich z.B. schon
> ersetzt, es hat gleich mal 100 Bytes gebracht...

...also quasi nix gebracht.

Quadratwurzel ist nicht sooo schwer zu berechnen, und daher würd ich 
eher auf sqrt aufbauen anstatt auf asin.  Beispiel:
  

wobei a(x) analytisch ist mit Konvergenzradius 2 um 0, d.h. du behommst 
damit asin(z) für alle komplexeb z mit |1-z| < 2.

Der Konvergenzradius von a ist zwar 2, aber dennoch würd ich das nicht 
ausreizen weil Potenzreihen am Rand ihres Konvergenzradius schlecht 
konvergieren (hier z.B. für asin(-1)).  Stattdessen würd ich die 
Symmetrie von asin verwenden und den Fehler in der Entwicklung von a 
durch asin(0) nach obiger Formel verwenden.

Eine explizite Darstellung der Taylor-Koeffizienten von a ist mir nicht 
beklannt.

von Mark B. (markbrandis)


Lesenswert?

Karl Kurzschluss schrieb:
> Danke, so weit war ich auch schon. ;)
>
> Ich brauche das Ganze, um Platz zu sparen. asin() habe ich z.B. schon
> ersetzt, es hat gleich mal 100 Bytes gebracht...

Wenn es in Deinem Projekt möglich ist, dann nimm doch einen größeren 
Mikrocontroller mit mehr Speicher.

Ich sag ja nicht dass man Speicherplatz verschwenden soll. Aber diverse 
Stunden Arbeit investieren um ein paar Euro Kosten zu vermeiden - da 
kommt man schnell an den Punkt wo man eher draufzahlt, als das man was 
spart.

von visitor (Gast)


Lesenswert?


von Johann L. (gjlayde) Benutzerseite


Lesenswert?

visitor schrieb:
> Schau Dir das mal an:
>
> http://netstorage.iar.com/SuppDB/Public/SUPPORT/000419/AN-G-002.pdf

Das sind 3 Iterationen Newton-Raphson.  Gähn

von Mark B. (markbrandis)


Lesenswert?

Karl Kurzschluss schrieb:
> ...wie gesagt, keine Näherungen...

Was glaubst Du, was die C Standard Library berechnet?

von Karl Kurzschluss (Gast)


Lesenswert?

Genau eben weil die C-Lib Näherungen benutzt, will ich keine selbst 
implementieren. Wenn es keine Umformung gibt, dann nehme ich auch 
einfach die Standard-Funktionen, weil ich davon ausgehe, dass die schon 
optimiert sind.
Dass mit asin() 100 Bytes frei wurden, hat mich schon erstaunt. Die kann 
ich gut gebrauchen. Es soll eine weitere Displaysprache in ein 
bestehendes Projekt hinein, das braucht einfach Platz und es müssen die 
vorhandenen Controller weiterverwendet werden.

von Mark B. (markbrandis)


Lesenswert?

Nun, unter Umständen sind diese Anforderungen nicht alle gemeinsam 
gleichzeitig erfüllbar. (gleiche Hardware, größere Datenmenge als 
bisher, begrenztes Einsparpotenzial da die bisherigen Berechnungen 
weiterhin korrekt durchgeführt werden müssen)

von Eric B. (beric)


Lesenswert?

Karl Kurzschluss schrieb:
> ...wie gesagt, keine Näherungen...

Dann kannst du es vergessen. Du wirst nicht genügend RAM haben um zB 
sqrt(2) oder pi ohne Verluste abzubilden.

von Pieter (Gast)


Angehängte Dateien:

Lesenswert?

moin,

wie FRAU SQRT berechnen kann zeigt der Anhang.

Pieter

von Amateur (Gast)


Lesenswert?

>...wie gesagt, keine Näherungen...

Schon anno Tobak haben wir gelernt, dass die Si-Nuss, die Kokkus-Nuss 
und die Erd-Nuss auf unendlichen Reihen basieren.
Da ist nichts mit: "ist gleich" sondern nur mit: "wie genau hätten's 
denn gerne".

Bei den trigometrischen Funktionen kannst Du Dir einiges an Platz (Code) 
sparen, indem Du sie voneinander ableitest. Wie das geht, steht schon in 
deinem, alten Mathematikbuch.

Auch beim Wurzeln schlagen gilt: "wie genau hätte's denn gerne" und 
nicht ein "ist gleich". Sonderfälle natürlich ausgenommen.

von Yalu X. (yalu) (Moderator)


Lesenswert?

Johann L. schrieb:
> visitor schrieb:
>> Schau Dir das mal an:
>>
>> http://netstorage.iar.com/SuppDB/Public/SUPPORT/000419/AN-G-002.pdf
>
> Das sind 3 Iterationen Newton-Raphson.  Gähn

Pieter schrieb:
> wie FRAU SQRT berechnen kann zeigt der Anhang.

Auch hier wird das Newton-Raphson-Verfahren genutzt, allerdings mit ein
paar kleinen Verbesserungen:

- Die Wurzelberechnung wird auf das Intervall [1/2, 1) reduziert, indem
  das Argument entsprechend normiert wird -> höhere Genauigkeit

- Es wird ein besserer Startwert (k₁·x + k₂) verwendet -> höhere
  Genauigkeit

- Alle Divisionen werden zu einer einzigen zusammengefasst -> weniger
  Rechenaufwand

Wegen der höheren Genauigkeit liefern schon 2 statt 3 Iterationen ein
brauchbares Ergebnis, was zusätzlich Rechenzeit einspart.

@Mark, Eric und Amateur:

Mit "keine Näherungen" meint Karl einen exakten mathematischen
Ausdruck für sqrt(x), der außer den vier Grundrechenarten nur die
Funktionen sin und atan2 enthält. Dass die numerische Berechnung
dieses Ausdrucks nur näherungsweise erfolgen kann, ist ihm schon klar.

Er möchte aber vermeiden, dass zu den Rundungsfehlern, die in den
verwendeten Bibliotheksfunktionen unvermeidbar entstehen, noch ein
zusätzlicher Fehler durch einen mathematisch nicht exakten
Gesamtausdruck hinzukommt.

Ich glaube aber auch nicht, dass der gesuchte Ausdruck existiert (sonst
hätte ihn sicher Johann schon gefunden).

Allerdings heißt Glauben nicht Wissen :)

: Bearbeitet durch Moderator
von Mark B. (markbrandis)


Lesenswert?

Yalu X. schrieb:
> @Mark, Eric und Amateur:
>
> Mit "keine Näherungen" meint Karl einen exakten /mathematischen/
> Ausdruck für sqrt(x), der außer den vier Grundrechenarten nur die
> Funktionen sin und atan2 enthält. Dass die numerische Berechnung
> dieses Ausdrucks nur näherungsweise erfolgen kann, ist ihm schon klar.
>
> Er möchte aber vermeiden, dass zu den Rundungsfehlern, die in den
> verwendeten Bibliotheksfunktionen unvermeidbar entstehen, noch ein
> zusätzlicher Fehler durch einen mathematisch nicht exakten
> Gesamtausdruck hinzukommt.
>
> Ich glaube aber auch nicht, dass der gesuchte Ausdruck existiert (sonst
> hätte ihn sicher Johann schon gefunden).
>
> Allerdings heißt Glauben nicht Wissen :)

Sicher hast Du Recht.

Im Endeffekt ist ja die Aufgabe hier nicht die, die der Themenersteller 
uns beschrieben hat. Er will (Flash-)Speicher sparen um dort mehr Text 
unterbringen zu können. Eventuell kann man dieses Problem auf völlig 
andere Art lösen.

Je nachdem wie die Texte aufgebaut sind, könnte es Speicherplatz sparen 
die Texte in geeignete Bausteine zu zerlegen und aus diesen größere 
Textmeldungen zusammenzusetzen.

Unter Umständen ist das gegebene Problem unter Einhaltung aller 
gegebenen Randbedingungen auch gar nicht lösbar. Um das beurteilen zu 
können, wissen wir aber zu wenig über das System.

Also alles a Schmarrn, wie der Bayer sagt. ;-)

Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.