Monte Carlo trifft PI

[Delphi-Padawan]

Hallo zusammen,

wir behandeln in der Schule zur Zeit die Monte Carlo-Methode.
Dazu möchte ich ein Programm schreiben:
Folgendes habe ich schon:
Zunächst wird ein Quadrat gezeichnet, darin ein Kreis mit maximaler Größe. Dieses Gebilde wird in vier Teile geteilt. Rechts oben in das Viertel werden n-Punkte gezeichnet.

was ich noch brauche:
Nun soll mir der PC ausgeben, wie viele der Punkte auf dem Kreis gelandet sind und wie viele auf dem Rest des Quadrates! Ich habe mir das so überlegt: wenn ich den Abstand der Punkte zum Mittelpunkt des Kreises errechnen könnte, wäre das meine Lösung, denn
Wenn Länge von Mittelpunkt zu Punkt < Radius dann ist der Punkt auf dem Kreis.

Ich zeichne mit Canvas.Ellipse, Canvas.Rectangle und Canvas.Pixels
Ich habe sie auch schon verbinden gelassen, kann aber nicht abfragen, wie lange diese Strecken jeweils sind!
Ich brauche das dringend!

Bitte helft mir!

[Nikolas]

Den Abstand zum Ursprung kannst du doch sehr einfach über den Satz des Pythagoras errechnen lassen...

[CalganX]

Hi,
lässt es sich nicht mathematisch ausrechnen, ob ein Punkt innerhalb einer bestimmten Fläche liegt? :gruebel: Ich weiß, dass ich das mal gemacht habe und das geht, aber leider weiß nicht mehr wie. Jedenfalls wäre das wesentlich effektiver, als über Canvas irgendwas zu lösen.

Chris

[Delphi-Padawan]

Hi Toxman,

das klingt gut, ich erinnere mich an etwas...
Aber wie ging das noch?
Kannst du mir das sagen?
BITTE!

[CalganX]

Hi,
Satz des Pythagoras sollte man als Schüler schon wissen bzw. wissen, wo man ihn nachschlagen kann:

Code:

a² + b² = c²
Wobei a und b die Katheten des rechtwinkligen Dreiecks ABC sind und c die Hypothenuse ist (die dem rechten Winkel gegenüberliegende Seite).

Chris

[yankee]

Ein anderer Thread mit Progrmm zum Problem
Ich musste für den Entwickler den Tester spielen.
Das Programm ist leider nicht OpenSource, aber du kanst dir ansehen, wie er es gelöst hat und dich gegebenenfalls mit dem Autor in Verbindung setzen. Er muss es ja wissen....

[axelf98]

Zitat:

Zitat von Delphi-Padawan

Ich habe mir das so überlegt: wenn ich den Abstand der Punkte zum Mittelpunkt des Kreises errechnen könnte, wäre das meine Lösung, denn
Wenn Länge von Mittelpunkt zu Punkt < Radius dann ist der Punkt auf dem Kreis.

Im Grunde hast du die Lösung schon selbst genannt... Man verwendet die Abstandsformel. Siehe Anhang!

[Binärbaum]

Also wenn der Kreis den Radius r hat, und der Punkt die Koordinaten P(x,y), dann kann man mit

Delphi-Quellcode:

if (sqrt(x*x+y*y)<=r) then begin
  //Punkt im Kreis
  ...
end
else begin
  //Punkt außerhalb des Kreises
  ...
end;

testen, ob der Punkt im Kreis ist. dazu braucht man auch keinen Canvas o.ä. .

MfG
Binärbaum

[Edit] Dabei wird davon ausgegangen, dass der Kreis den Mittelpunkt M(0;0) hat.
Ansonsten müsste man die if Abfrage ändern:

Delphi-Quellcode:

if (sqrt(sqr(x-c)+sqr(x-d))<=r) then //Fortsetzung wie oben...

Dabei hat der Mittelpunkt des kreises die Koordinaten M(c;d).
[/Edit]

[Jelly]

Zitat:

Zitat von Binärbaum

Delphi-Quellcode:

if (sqrt(x*x+y*y)<=r)

Statt über die Wurzel zu verfahren geht das hier auch, und hat den Vorteil, daß es wesentlich schneller läuft. Ist bei Monte Carlos immer zu berücksichtigen, da das Verfahren sehr oft durchgeprüft werden muss.

Delphi-Quellcode:

x*x+y*y<=r*r

[Nicolai1234]

Ich habe mal eine Frage zum Verständnis. Das ganze mit Canvas zu machen bringt doch rein garnichts oder?
Wenn ich so ein Viertelkreis habe, dann könnte ich doch auch gleich die Pixel auszählen, um zu gucken, wie groß Pi unefähr ist, oder? Das wäre zwar nicht sehr genau, aber es käme auf dauer doch das gleiche raus wie bei der Monte Carlo Methode.
Sehe ich da was falsch?
Beispiel:
Das obige Bild hat 71x71 Pixel. Das sind dann insgesamt 5041 Pixel.
Davon liegen 1605 Pixel außerhalb des Kreises und 3436 Pixel innerhalb. Dann käme ich auf ein Pi von ungefähr 3,1408.
Das Ergebnis wird doch fast genauso bleiben, wenn ich da jetzt ein paar Punkte zufällig raufmale, oder?

Das heißt (denk ich mal) dass man eine so große Fläche bräuchte, die mit einem Canvas nicht mehr zu bewältigen ist. Aber auch sp ist doch der Effekt mit den Pixelzählen immer schneller ung genauer als ein paar zufällige Punkte...

Naja, vielleicht kann mich ja einer eines Besseren belehren...
Gruß
Nicolai

[Jelly]

Zitat:

Zitat von Nicolai1605

als ein paar zufällige Punkte...

Mit der Monte Carlo Methode kannst du Pi beliebig genau bestimmen. Musst nur die Anzahl deiner Tests erhöhen :-D
Beim Zählen der Pixel klappt das nicht, da du nur x*y Pixel hast.

[Nicolai1234]

Aber wenn die Punkte gegen unendlich laufen, ist doch der Wert genau der, der bei meiner Pixelrechnung rauskommt, oder?

[Jelly]

Zitat:

Zitat von Nicolai1605

Aber wenn die Punkte gegen unendlich laufen

Hast du denn auch unendlich Speicher um dein Schachbrett im Speicher zu halten ?

[Nicolai1234]

Zitat:

Zitat von Jelly

Zitat:

Zitat von Nicolai1605

Aber wenn die Punkte gegen unendlich laufen

Hast du denn auch unendlich Speicher um dein Schachbrett im Speicher zu halten ?

?

Erlär doch mal, warum meine Annahme falsch ist. Wenn ich das oben genannte Beispiel durchrechnen lasse, dann komme ich wirklich nur auf den Wert, der auch bei den Pixeln rauskommt. egal wie viele Millionen mal ich da Punkte raufmache...
WO liegt denn da mein Denkfehler?

[Jelly]

Stell dir ein Kasten von 10x10 vor, sprich 100 Pixel. Selbst wenn du alle Pixel zählst, wirst du nur 31 schwarze (damit mein ich Pixel innerhalb des Kreises) und für den Rest weisse finden. Damit wirst du Pi NIE genauer wie 3.1 bestimmen können. (Pi=schwarze/Gesamtzahl)

Oder hab ich dich falsch verstanden, wie du über das Canvas Pi bestimmen willst. :gruebel:

[Nicolai1234]

Ne, hast du nicht, aber ganz oben hat eienr gefragt, wie er das mit Canvas macht...


Was brauch man denn für eine Größe um Pi genauer zu bestimmen?

[Tortus]

Zitat:

Zitat von Nicolai1605

Zitat:

Zitat von Jelly

Zitat:

Zitat von Nicolai1605

Aber wenn die Punkte gegen unendlich laufen

Hast du denn auch unendlich Speicher um dein Schachbrett im Speicher zu halten ?

?

Erlär doch mal, warum meine Annahme falsch ist. Wenn ich das oben genannte Beispiel durchrechnen lasse, dann komme ich wirklich nur auf den Wert, der auch bei den Pixeln rauskommt. egal wie viele Millionen mal ich da Punkte raufmache...
WO liegt denn da mein Denkfehler?

Ich glaube, deine Lösung ist auch richtig.
Dein Denkfehler (und gleichzeitig der Vorteil der Monte-Carlo-Methode) besteht darin, das bei deiner Pixelbasierenden Lösung das Canvas seeehr groß sein müsste, um ein brauchbares ergebnis zu liefern, da ein Pixel ja bekanntlich entweder schwarz oder weiß ist, aber nicht halb schwarz, halb weiß oder so.
Bei der Monte-Carlo-Methode hingegen kann man Dezimalzahlen einsetzen, die die Ergebnisse des Zufallszahlengenerators sind.

/E: Herrlich, bin ich wieder zu langsam gewesen, und ich glaube sogar am Thema vorbei.

Dafür gibts hier jetzt mal eine ganz einfache Übersetzung des Vorschlags von Wikipedia zur Monte-Carlo Methode:

Delphi-Quellcode:

procedure TForm1.Button1Click(Sender: TObject);
var
  tropfenzahl,
  innerhalb,
  gesamt: Integer;
  dotx,
  doty,
  piwert: Extended;
begin
  tropfenzahl := StrToInt(Edit1.Text);
  innerhalb := 0;
  gesamt := tropfenzahl;
  Progressbar1.Max := tropfenzahl;
  while(tropfenzahl>0) do
  begin
    Randomize;
    dotx := 2 * Random-1;
    doty := 2 * Random-1;
    if(Sqrt(dotx*dotx + doty*doty) <= 1) then
    begin
      innerhalb := innerhalb +1;
    end;
    tropfenzahl := tropfenzahl -1;
    Progressbar1.Position := Gesamt - tropfenzahl;
    Application.ProcessMessages;
  end;
  Edit2.Text := FloatToStr(4*innerhalb/gesamt);
end;

Wie gesagt, einfach aus meinem Testprogrämmle kopiert, und ohne weiteres Tuning

[Binärbaum]

@jelly
@Nicolai

Wenn man das Ergebnis möglichst genau haben will, muss man sich vom Canvas loslösen und die Sache rein arithmetisch/analytisch betrachten. Damit könnte man auch die Genauigkeit beliebig erhöhen, vorausgesetzt man lässt das Programm lang genug laufen.

MfG
Binärbaum

//Edit: Rechtschreibfehler korrigiert

[Jelly]

Zitat:

Zitat von Binärbaum

Damit könnte man auch die Genauigkeit beliebig erhöhen, vorausgesetzt man lässt das Programm lang genug laufen.

Hab ich was anderes behauptet :wiejetzt:

[Binärbaum]

Zitat:

Zitat von Jelly

Zitat:

Zitat von Binärbaum

Damit könnte man auch die Genauigkeit beliebig erhöhen, vorausgesetzt man lässt das Programm lang genug laufen.

Hab ich was anderes behauptet :wiejetzt:

Irgendwie schon, weil du da von Canvas geredet hast, und ein Canvas -auch wenn er noch so groß ist und noch so viele Pixel hat- begrenzt ist, und damit sind der Genauigkeit gewisse Grenzen gesetzt (vom Speicherbadarf des Canvas mal abgesehen).

[mung]

Ich glaub nicht das es wirklich genauer wird, denn die Pixel werden zufällig gesetzt.....
Wir haben des letztens auch in der Schule geproggt und da hats sogar ganz selten 3,14 ergeben, aber will mir wegen sowas jetzt keine Feinde machen :mrgreen: .

Ps: Approximation durch Unter- und Obersumme rult ^^

mfg

[Jelly]

Die Monte Carlo Methode funktioniert erst dann, wenn die Zufallswerte, die du dir erzeugst, unendlich viele UNTERSCHIEDLICHE sein können. Delphi bietet die die Random Funktion an, welche eine Zufallszahl zwischen 0 und 1 liefert. Und zwar nicht nur 10 oder 100 oder 1000 unterschiedlich mögliche, sondern unendlich viele unterschiedliche, mal abgesehen von der Genauigkeit deines zugrunde liegenden Datentyps. (N=inf)

Der Canvas bietet dir aber nur ein N=x^2 großes Raster- bzw- Schachbrett. Es gibt also nur N Zufallspunkte=Zufallszahlen.

Die Genauigkeit deines Ergebnisse liegt in der Größenordnung von 1/N. Also bist du bei einem 10x10 Canvas auf eine Genauigkeit von 1/100 beschränkt. Auch wenn du dein Ergebnis mit 30 Nachkommastellen hinschreibst, ist das Ergebnis trügerisch, weil du einfach nur eine Genauigkeit von 1/100=0,01 hast.

Ich hoffe, jetzt ist das Prinzip klar geworden. Das ist vergleichbar mit einem Notendurchschnitt von 3 Schülern. noten 1;2;2 macht auch keinen Schnitt von 1,6666666666... da du nicht genug Messpunkte hast :zwinker:

[Binärbaum]

Da Mung gerade von Unter- /Obersumme spricht:
Man könnte das auch durch ein Integral lösen. Wenn man die Funktion
f(x)= sqrt(1-x*x)
integriert und das bestimmte Integral dieser Funktion in den Grenzen von null bis 1 berechnet kann man Pi auch ermitteln:
Pi:= bestimmtesIntegral *4;
Wobei die Variable bestimmtesIntegral das oben erwähnte Integral als Wert hat.

Das aht zwar nichts mehr mit MonteCarlo zu tun, aber Pi hat man trotzdem ermittelt (und das war ja das eigentliche Ziel).

MfG
Binärbaum

[mung]

@Jelly: Jo stimmt . Wenn ich das richtig verstanden habe -> auf einem verdammt großen Canvas mit verdammt vielen Zufallspunken, wird Pi verdammt genau ermittelt :zwinker: !

[Jelly]

Zitat:

Zitat von mung

@Jelly: Jo stimmt . Wenn ich das richtig verstanden habe -> auf einem verdammt großen Canvas mit verdammt vielen Zufallspunken, wird Pi verdammt genau ermittelt :zwinker: !

Da wird aber irgendwann dein Speicher aus allen Nähten platzen...

Wenns interessiert, mit Monte Carlo Methode kann man aber noch viel mehr simulieren als die Zahl Pi. Dafür gibt es eh andere und bessere Methoden. Siehe hier