Berechnung von Pi
Posted on 19. Okt, 2009 by Markus Schabel in Informatik
Hier ist bereits der erste Artikel der Programmier-Rätsel/Aufgaben-Serie (diesmal von Programming Praxis). Eine sehr beliebte Aufgabe ist die Berechnung von Pi, eine Ãœbung die ich auch meinen Schülern gerne gebe – oft mit der Zusatzaufgabe zu bestimmen, wie viele Iterationen man benötigt, um eine entsprechende Genauigkeit zu erreichen. Hier ein kurzer Auszug der ersten Aufgabe des Beispiels (Berechnung von Pi mittels Monte Carlo Simulation, d.h. mit Hilfe von Zufallszahlen):
An interesting method for calculating π uses Monte Carlo simulation. If a circle of radius r is inscribed in a square with sides of length 2r, the area of the circle will be πr2 and the area of the square will be (2r)2, so the ratio of the area of the circle to the area of the square will be π/4. Another way of looking at this, [..] is to consider just the first quadrant of the circle; the square has an area of r 2, and the portion of the circle within the square has an area of πr2/4.
By taking a large number of points randomly distributed throughout the square and counting how many are within the inscribed circle, we can estimate the value of π. We could do that by building a model, scattering sand over it, and counting the individual grains of sand, but since we are programmers, it is easier to write a program to do the counting for us.
Eine alternative Lösung ist es, einen Kreis zu nehmen, und diesen mit einem umlaufenden und einem eingebundenen Polygon zu versehen, und bei diesen Polygonen die Seitenanzahl möglichst hoch zu wählen. Je höher die Seitenzahl wird, desto ähnlicher werden die Polygone einem Kreis, bzw. desto ähnlicher werden die Umfänge der beiden Polygone, wobei der Kreisumfang zwischen beiden Werten liegt. Diese Aufgabe wird hier ebenfalls gestellt:
The second method is due to Archimedes (287–212 BC), a Greek mathematician who lived in Syracuse, who famously bounded the value of π within a small range by measuring the perimeters of inscribed and circumscribed regular polygons with ninety-six sides: 223/71 < π < 22/7.
Consider a circle with radius 1 and circumference 2π in which regular polygons of 3 × 2n-1 sides are inscribed and circumscribed; [..]. If bn is the semiperimeter of the inscribed polygon, and an is the semiperimeter of the circumscribed polygon, then as n increases, b1, b2,b3, … defines an increasing sequence, and a1, a2, a3, … defines a decreasing sequence, each with limit π.
Given K = 3 × 2n-1, the semiperimeters are an = K tan(π/K) and bn = K sin(π/K) by the definitions of sine and tangent. Likewise, an+1 = 2K tan(π/2K) anda n+1 = 2K sin(π/2K).
Then, simple trigonometry allows us to calculate (1/an + 1/bn) = 2/an+1 and an+1bn = (bn+1)2. Archimedes started with a1 = 3 tan(π/3) = 3√3 and b1 = 3 sin(π/3) = 3√3/2 and calculated b6 < π < a6.
Letztendlich kann man Pi auch noch mit Hilfe von verschiedenen Reihen berechnen (diese Aufgabe findet sich jedoch nicht im entsprechenden Programming Praxis Artikel). Die bekannteste Reihe zur Berechnung von Pi dürfte die folgende sein:
Ï€/4 = 1/1 – 1/3 + 1/5 – 1/7 + 1/9 – 1/11 + 1/13 – 1/15 + 1/n – 1/(n+2)
Viel Erfolg beim Nachprogrammieren! Entsprechende Lösungen werden gerne als Kommentare gesehen, bzw. werde ich selber bei Gelegenheit den einen oder anderen Lösungsvorschlag bringen.
Verwandte Literatur (amazon):
C: Programmieren von Anfang anDieser Grundkurs führt anhand einfacher Beispiele schrittweise in die C-Programmierung ein. Neben den Sprachgrund-lagen werden Themen wie Enumerations, rekursives Programmieren Prozesskommunikation, Multithreading und das Einbinden von Assemblercode vermittelt.
Christoph
Nov 18th, 2009
Monte-Carlo Simulation für 100000 Sandkörner (einfach per copy/paste in die Adresszeile kopieren:)
javascript:n=100000;m=0;for(i=0;i<n;++i){x=Math.random()*2-1;y=Math.random()*2-1;m+=(x*x+y*y<1)?1:0};alert(4*m/n)
Markus Schabel
Nov 21st, 2009
Vielen Dank für das Beispiel. Ich glaub viel kürzer (und trotzdem lesbar) geht es wohl nicht.