Hallo zusammen
Ausgangslage:
Es soll die Zahl Pi möglichst schnell auf die 5. Nachkommastelle genau
berechnet bzw. angenähert werden.
Ich habe einige Ideen, so z.B. die Ramanujan methode
http://numbers.computation.free.fr/Constants/Pi/piramanujan.html
Aber ich kenne das Forum nun schon länger und es gibt hier immer wieder
sehr spannende Ideen. Deshalb würde ich mich über eine offene Diskussion
freuen.
Es ist klar, dass in der Praxis dies eigentlich nicht gemacht wird,
sondern dafür eine Kostante verwendet wird.
Achja, Zielplatform: Atxmega128.
Danke schonmal
[K]ein Sohn [des] Admins (frei nach Lk 3,33) schrieb im Beitrag
#5797450:
> Arcustangens
Ja, damit geht es sehr schnell:
1
#include<math.h>
2
3
floatpi;
4
5
intmain(void){
6
pi=4*atan(1);
7
}
Der Compiler liefert:
1
main:
2
ldi r24,lo8(-37)
3
ldi r25,lo8(15)
4
ldi r26,lo8(73)
5
ldi r27,lo8(64)
6
sts pi,r24
7
sts pi+1,r25
8
sts pi+2,r26
9
sts pi+3,r27
10
ldi r25,0
11
ldi r24,0
12
ret
Für nur fünf Nachkommestellen lohnt es sich nicht, sich Gedanken zum
optimalen Algorithmus zu machen. Interessant wird es frühestens bei
ein paar Hunderttausend Nachkommastellen.
Holger K. schrieb:> Es soll die Zahl Pi möglichst schnell auf die 5. Nachkommastelle genau> berechnet bzw. angenähert werden.
pi = 3.14159
Wozu rechnen ? Pi ist nicht variabel.
Michael B. schrieb:> Holger K. schrieb:>> Es soll die Zahl Pi möglichst schnell auf die 5. Nachkommastelle genau>> berechnet bzw. angenähert werden.>> pi = 3.14159>> Wozu rechnen ? Pi ist nicht variabel.
Einfach zum Spaß um zu sehen wie es geht? Aber klar man könnte auch
einfach M_PI aus der math.h nehmen...
S. R. schrieb:> Und wenn man als Ingeneur mit ein paar Prozent Abweichungen zufrieden> ist, dann tut es auch sqrt(10) ~ 3.162.
Ein so designtes Auto möchte ich aber nicht fahren!
Ich weiß zwar auch nicht, warum der TO das berechnen will, aber
2*arccos(0) etc. Ist für mich dann eher ein taschenspielertrick, was ja
auch
Yalu X. schrieb:> Der Compiler liefert
zeigt. Das ist nahe an "einfach den Kehrwert von 1/Pi".
Oder ging es dem TO eher um Taschenrechner, wo mangels Tasten die
Konstanten so abruft? Also z.b. e^1 wenn man e braucht.
Tim T. schrieb:> Einfach zum Spaß um zu sehen wie es geht? Aber klar man könnte auch> einfach M_PI aus der math.h nehmen...
M_PI gehört aber nicht zum Standard.
Holger K. schrieb:> Es ist klar, dass in der Praxis dies eigentlich nicht gemacht wird,> sondern dafür eine Kostante verwendet wird.
Klaro:
Die deutsche Straßenverkehrszulassungsordnung bestimmt für die
Berechnung des (für die Kfz-Steuer relevanten) Hubraums eines
Verbrennungsmotors: „Für pi wird der Wert von 3,1416 eingesetzt.“
(wikipedia)
Hab mal was rumgespielt und mit den Kettenbrüchen von Lambert ist Pi mit
einem 10-fach Kettenbruch mit maximaler float Genauigkeit und mit einem
22-fach Kettenbruch mit maximaler double Genauigkeit berechenbar.
Und dazu noch extrem einfach zu implementieren:
Vielen Dank für all eure, teils sehr interessanten Ansätze!
Nochmals kurz zum Sinn bzw. Unsinn.
Es geht nicht darum, dies für etwas "produktives" einzusetzen.
Es geht mehr darum, sich mit Mathematik und den eventuellen
Vereinfachungen zu beschäftigen.
Sich mit möglichen Optimierungen oder Stolpperfallen bei uCs
auseinanderzusetzen.
Natürlich möchte ich dann auch einen Algorithmus als "Beweis"
implementieren.
Dies aber mehr als spielerei.
Natürlich würde ich bei etwas "produktiven" die benötigte Genauigkeit
auf einem PC rechnen lassen oder aus dem Netz holen und als Konstante
ablegen.
Harald W. schrieb:> Vielleicht reicht ja auch dieser "gesetzliche" Wert:> https://de.wikipedia.org/wiki/Indiana_Pi_Bill
PI=4, stimmt doch? Die Distanz zwischen 2 Punkten berechnen, einfach die
X und Y Distanz addieren, keine nervigen Wurzeln und Quadrate nötig! Ein
Kreis zeichnen ist auch viel einfacher, 4 Linien und man ist fertig! Und
es gibt auch nicht immer nur den einen schnellsten Weg, der zum Ziel
führt, sondern ein ganzes Rechteck an schnellsten wegen! Die
Manhattan-Metrik ist der Euklidischen Geometrie massiv überlegen!!!
https://en.wikipedia.org/wiki/Taxicab_geometry
Archimedes' Verfahren in Visual Basic
' Erstellt Pi aufgrund des Archimedes-Verfahren
' mit einem 2 ^ 26 Eck.
Private Function Pi() As Double
Dim a As Double
Dim b As Double
a = 2 * Sqr(3)
b = 3
Do Until a = b
a = 2 a b / (a + b)
b = Sqr(a * b)
Loop
Pi = a
End Function
Archimedes' Verfahren in Visual Basic
' Erstellt Pi aufgrund des Archimedes-Verfahren
' mit einem 2 ^ 26 Eck.
Private Function Pi() As Double
Dim a As Double
Dim b As Double
a = 2*Sqr(3)
b = 3
Do Until a = b
a = 2*a*b/(a + b)
b = Sqr(a*b)
Loop
Pi = a
End Function
Tim T. schrieb:> Nico W. schrieb:> Ohne Division wenn man Integermathematik ausnutzen möchte.>> 201 >> 6>> = 3>> Tolle Wurst^^
Ein bisschen Grips wird beim Anwenden davon erwartet. Würde ich bei
Fließkommarechnungen auch nicht einsetzen. Daher auch der Hinweis auf
Integermathematik.
Bei Fixedpoint geht das dann aber Ratzfatz mit einem Fehler unter 0,1%.
Nico W. schrieb:>> Ein bisschen Grips wird beim Anwenden davon erwartet. Würde ich bei> Fließkommarechnungen auch nicht einsetzen. Daher auch der Hinweis auf> Integermathematik.>>> Bei Fixedpoint geht das dann aber Ratzfatz mit einem Fehler unter 0,1%.
Wie willst du das bitte sinnvoll einsetzen? Ich sehe da so garkeine
Möglichkeit.
Wofram_Draht schrieb:> Archimedes' Verfahren in Visual Basic>> ' Erstellt Pi aufgrund des Archimedes-Verfahren> ' mit einem 2 ^ 26 Eck.> Private Function Pi() As Double> Dim a As Double> Dim b As Double>> a = 2*Sqr(3)> b = 3>> Do Until a = b> a = 2*a*b/(a + b)> b = Sqr(a*b)> Loop>> Pi = a>> End Function
Dürfte immernoch Faktor 3 langsamer sein als es mit Kettenbrüchen zu
rechnen.
Ausgleich
der
vielen
Zitatzeilen
Tim T. schrieb:> Int verschoben um Int, ergibt ein Int, kein Float oder Double...
Der wahre Kenner vom Windows Taschenrechner stellt sofort fest, dass es
Nachkommastellen nur bei Dezimalzahlen, aber nicht bei Binär- oder
Hexadezimalzahlen gibt :-(
Tim T. schrieb:>> Bei Fixedpoint geht das dann aber Ratzfatz mit einem Fehler unter 0,1%.>> Wie willst du das bitte sinnvoll einsetzen? Ich sehe da so garkeine> Möglichkeit.
Weil du keine Fixpointrechnung kennst?
Darstellung mit 10bit für die Nachkommastelle:
leo schrieb:> Nico W. schrieb:>> int umkreis = 2 radius 201 >> 6; // 12864 / (1 << 10) = 12.5625>> Ja, wenn du dann noch Klammern setzt, funktioniert das auch.>> leo
sorry fuer den falschen Einwurf, es wuerde funktionieren, wenn die ints
lang genug (32 bit) sind.
leo
Nico W. schrieb:> Ohne Division wenn man Integermathematik ausnutzen möchte.>> 201 >> 6
Wie bereits geschrieben wurde, geht des so direkt nicht. Man kann aber
auch den Ausdruck 201.0/64 (in Floating-Point) ohne Division und
Multiplikation berechnen:
1
#include<stdio.h>
2
#include<stdint.h>
3
#include<math.h>
4
5
floatz=201.0;// global, um Berechnung zur Laufzeit zu erzwingen
6
7
intmain(void){
8
floatpi;
9
10
// pi = z / 64
11
12
# if defined __STDC_IEC_559__ || defined __AVR_ARCH__
13
union{floatf;uint8_tc[4];}u={z};// u.f = z;
14
# if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__
15
u.c[3]-=3;// u.f /= (1<<(2*3));
16
# elif __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__
17
u.c[0]-=3;// u.f /= (1<<(2*3));
18
# else
19
# error cannot determine endianess
20
# endif
21
pi=u.f;// pi = u.f;
22
# else
23
pi=ldexp(z,-6);// pi = z / (1<<6);
24
# endif
25
26
printf("%f\n",pi);
27
}
Stellt der Compiler float-Zahlen gemäß ISO/IEC/IEEE 60559 (IEEE 754)
dar, reduziert sich die Division auf eine einfache 8-Bit-Subtraktion.
Sonst kann dafür auch die ldexp-Funktion genutzt werden, die allerdings
auch potentielle Überläufe und denormalisierte Zahlen berücksichtigt
(was hier nicht nötig ist) und deswegen weniger effizient ist.
Pi in hexadecimal ausrechnen:
https://de.m.wikipedia.org/wiki/Bailey-Borwein-Plouffe-Formel
Eine Berechnung jeder Stelle von Pi ohne die Berechnung der
vorhergehenden (im 16er System) ist möglich. Persönlich finde ich das
unheimlich, und ist m.M.n. der direkteste Hinweis, dass der Film die
Matrix in Wirklichkeit eine Dokumentation ist.
leo schrieb:> sorry fuer den falschen Einwurf, es wuerde funktionieren, wenn die ints> lang genug (32 bit) sind.
Das ist allgemein bei Fixedpoint immer zu beachten und kann einem auf
die Füße fallen.
Yalu X. schrieb:> Wie bereits geschrieben wurde, geht des so direkt nicht.
Mir ging es um den Verzicht um floats und co.
>> Bei Fixedpoint geht das dann aber Ratzfatz mit einem Fehler unter 0,1%.>> Wie willst du das bitte sinnvoll einsetzen? Ich sehe da so garkeine> Möglichkeit.
Pi selbst ausrechnen, ist ja sinnlos. Es kommt aber häufig (meist?)
als Faktor vor und dann kommt man mit Brüchen (x*22/7, x*355/113,
x*201/64, usw) weiter als mit x*3. Wie weit, kommt drauf an, wieviele
Bits man für das Zwischenergebnis übrig hat - einige Sprachen (CPUs?)
bietet dafür sogar extra eine muldiv-Funktion mit doppelt genauem
Zwischenergebnis an.
foobar schrieb:>>> Bei Fixedpoint geht das dann aber Ratzfatz mit einem Fehler unter 0,1%.>>>> Wie willst du das bitte sinnvoll einsetzen? Ich sehe da so garkeine>> Möglichkeit.>> Pi selbst ausrechnen, ist ja sinnlos. Es kommt aber häufig (meist?)> als Faktor vor und dann kommt man mit Brüchen (x*22/7, x*355/113,> x*201/64, usw) weiter als mit x*3. Wie weit, kommt drauf an, wieviele> Bits man für das Zwischenergebnis übrig hat - einige Sprachen (CPUs?)> bietet dafür sogar extra eine muldiv-Funktion mit doppelt genauem> Zwischenergebnis an.
Mein Einwand bezog sich mehr darauf, welche Vorteile das bieten soll.
Wenn ich Pi als Float Konstante ablege, kostet mich das 4 Byte, als Int
Operation bin ich ebenfalls ab 4 Byte dabei. Die Genauigkeit als Float
ist höher, bleibt also nur noch die Geschwindigkeit und da kostet eine
Float Multiplikation, je nach CPU etwa die 3-fache Zeit wie eine mit
32-Bit Int, mit FPU noch weniger. Dafür sparst man aber die Verschiebung
(ok, das geht fix wenn die Zielhardware die nativ auf mindestens 32-Bit
unterstützt) und sobald man das Endergebnis irgendwann doch als
richtigen Wert braucht, ist der Geschwindigkeitsvorteil komplett dahin.
Aber selbst wenn nicht am Ende umgewandelt wird, man tauscht nicht
gerade wenig Genauigkeit gegen einen minimalen Geschwindigkeitsvorteil
und macht es sich zusätzlich unnötig schwer.
Setz Pi=1. Machen wir Wissenschaftler auch, wenn die Rechnungen schnell
gehen sollen, siehe Anhang.
Das Ergebnis hat dann halt eine andere Einheit, aber da gewöhnt man sich
dran...
?
Dumdi D. schrieb:> Pi in hexadecimal ausrechnen:>> https://de.m.wikipedia.org/wiki/Bailey-Borwein-Plouffe-Formel>> Eine Berechnung jeder Stelle von Pi ohne die Berechnung der> vorhergehenden (im 16er System) ist möglich.
...und im Wiki sogar implementiert (C99) und ausführich kommentiert:
4000 Stellen von Pi mit ATtiny2313
Übersetzbar mit einem avr-gcc für ATtiny2313 und Ausgabe via USART, und
das Programm lässt sich auch ganz normal für einem Host übersetzen und
ausführen :-)
Eben mal mit avrtest durchlaufen lassen. Für 100 Nachkommastellen
(Basis 16) von pi braucht's ca. 38E6 Ticks, für 5 Nachkommstellen also
(1/20)^2 = 1/400 mal so viel, und für Basis 10 nur das log 10 / log 16 =
0.83-fache.
Um das Äquivalent von 5 dezimalen Nachkommastellen zu berechnen
braucht's also ca. 38E6 / 400 * 0.83 ~ 80000 Ticks. Damit ist es das
bislang aufwändigste Verfahren — und genau das war vom TO gewünscht :-)
Wofür soll die Geschichte denn sein? Wenn man PI genau berechnen will,
bringt es nur etwas, wenn man eine höhere G berechnet, die bisher schon
bekannt ist und selbst die übersteigt, alles, was man braucht.
Solche schlauen iterativen Verfahren brauchen wir doch eigentlich nur
für Funktionen Y(X), also einem unbekannten Werdt, wie z.B: LOG.
Frage schrieb:> Nico W. schrieb:>> Von Basis 16 auf Basis 10 benötigst du die vorhergehenden Stellen.>> Wozu braucht man eigentlich die dezimalen Stellen von Pi?
Und warum liegt hier überhaupt Stroh rum?
Jürgen S. schrieb:> Wofür soll die Geschichte denn sein?
Das steht weiter oben im Thread.
Es geht darum, an einem an sich einfachen Beispiel, optimierungen im
Bereich Mathe und Prozessoren anzuwenden.
Es macht einen unterschied ob man alles mit integer "zu gross" rechner
oder ob man von beginn an float verwendet.
So auch ob man evtl. einen HW-Multiplier verwendet oder nicht etc...
Tim T. schrieb:> Frage schrieb:>> Wozu braucht man eigentlich die dezimalen Stellen von Pi?>> Und warum liegt hier überhaupt Stroh rum?
Zur Erläuterung meiner Frage:
BCD-Arithmetik wird ja nur im kaufmännischen Bereich verwendet.
Und dort braucht man Pi nicht.
Im MINT-Bereich, wo man Pi braucht, rechnet man binär.
Thread beobachten
Seitenaufteilung abschalten