Diskussion: Pi möglichst schnell berechnen

Die Fortran Gemeinde macht

[K]ein Sohn [des] Admins (frei nach Lk 3,33) schrieb im Beitrag 
#5797448:
> Die Fortran Gemeinde machtπ=4∗arcsin1\pi=4*\arcsin{1}

Schuldigung, es ist der Arcustangens.

Joe G. schrieb:
> Pi ist doch 180 Grad, also 2*arcsin(1)

Genau

Wenn man Pi in Ganzzahlarithmetik braucht, ist 355/113 ne gute Näherung 
- 3.1415929.

Lambert hat sich 1770 dafür die Kettenbrüche ausgedacht:

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

https://www.youtube.com/watch?v=zBBqglRfUpI&;

Heutzutage macht man das natürlich mit einer WebAPi:

curl 'https://api.pi.delivery/v1/pi?start=0&numberOfDigits=100';

Und schon hat klappt das... Und das tolle ist das funktioniert mit allen 
Programmiersprachen ;) ;)

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.

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:

1

double Kettenbruch( int n_max ) {

2

3

  int n;

4

  double nenner = 2 * n_max - 1;

5

6

  for ( n = n_max - 1; n > 0; n-- ) nenner = 2 * n - 1 + n * n / nenner;

7

8

  return nenner;

9

10

}

11

12

double pi( void ) {

13

14

  return ( 4 / Kettenbruch( 22 ) );

15

16

}

Wie ein Nerd eine Näherung für Pi berechnet:

1

              -----

2

 9     --    /  9  

3

--- +    \  /  ---  ~ Pi

4

 5        \/    5

Warum willst du Pi schnell berechnen?

Yalu X. schrieb:
> #include <math.h>

Gibt es die math.h auch für AVR-Controller und wenn ja, ist irgendwo 
verständlich dokumentiert, was sie kann?

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

> Und wenn man als Ingeneur mit ein paar Prozent Abweichungen zufrieden
> ist, dann tut es auch sqrt(10) ~ 3.162.

22/7= 3,1428...

Nico W. schrieb:
> Ohne Division wenn man Integermathematik ausnutzen möchte.
>

1

201 >> 6

= 3

Tolle Wurst^^

Int verschoben um Int, ergibt ein Int, kein Float oder Double...

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

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 :-(

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

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

3217>>10;

reicht fuer 5 Stellen!

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

Nico W. schrieb:
> Von Basis 16 auf Basis 10 benötigst du die vorhergehenden Stellen.

Wozu braucht man eigentlich die dezimalen Stellen von Pi?

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?

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.