MonteCarlo....Optimierung des Grundgedankens?

[glkgereon]

Hi,

der Grundgedanke der Monte-Carlo-Simulation zur Berechnung ist ja folgender:

ganz viele zufällige punkte suchen und die zählen die im kreis sind...dann ist pi:=4*PunkteImKreis/PunkteGesamt

wäre nicht folgender Ansatz viel Performanter zu realisieren? (da kein zufallsgenerator...)
man nimmt keine zufälligen punkte sondern erstellt ein Raster (zB 256*256) und prüft jeden punkt.
Vorteile:
- kein zufall => weniger rechenaufwand (?)
- keine Abweichung (Die zufällige Abweichung die zwangsweise aus den zufälligen Punkten entsteht fällt weg)
- zwangsläufig nur Integer-Rechnung...

Die Genauigkeit könnte man durch ein einfaches vergrößern des Rasters erreichen...


Würde das funktionieren?
Wäre das theoretisch schneller?

[stoxx]

also es geht ja gerade um die Zufälligkeit bei der Sache

Zitat:

der Grundgedanke der Monte-Carlo-Simulation zur Berechnung ist ja folgender:

das ist nicht der Grundgedanke, sondern eine einzige kleine praktische Anwendung von Monte Carlo

[glkgereon]

Zitat:

Zitat von stoxx

also es geht ja gerade um die Zufälligkeit bei der Sache

Aber wenn man es oft genug macht nähert man sich der absolut gleichmäßigen verteilung unendlich nahe an (theoretisch^^)
und dann kann man doch gleich die komplett gleichmäßige verteilung nehmen, oder nicht?

[alcaeus]

Zitat:

Zitat von glkgereon

Aber wenn man es oft genug macht nähert man sich der absolut gleichmäßigen verteilung unendlich nahe an (theoretisch^^)
und dann kann man doch gleich die komplett gleichmäßige verteilung nehmen, oder nicht?

Du sagst es doch selbst: Theoretisch naehert sich das Ding der absolut gleichmaessigen Verteilung an, wird aber erst in der Unendlichkeit genau gleich sein. Das heisst aber nicht, dass ich deshalb gleich schon die gleichmaessige Verteilung nehmen kann, schliesslich wird immer ein Unterschied da sein, auch wenn er noch so verschwindend gering ist ;)

Greetz
alcaeus

[Jelly]

Da hast Du im Prinzip Recht, nur ist dein Gedankengang hier nicht wirklich begründet, aus mehreren Gründen:
Die Pi-Bestimmung über die Monte Carlo Methode ist nur ein simples Anwendungsbeispiel, das immer wieder gern herangezogen wird, um die Methode verständlich rüber zu bringen. Und weiter probier ich mal, die die Statistik etwas näher zu bringen. Du gibtst Dir ein 100x100 Raster, und nach deiner Methode kriegst Du ja 10.000 Testfälle. Über Zufall kann ich beliebig viele Testfälle generieren lassen, und krieg daduch natürlich auch irgendwann die gleiche Genauigkeit raus.

Es geht also nicht drum, zu zeigen dass die MCM performant, genau und schnell ist. Sie ist einfach nur eine Methode, über Zufälle gewisse Aussagen treffen zu können. In deinem Pi-Beispiel gibt es viele andere Methoden, die viel genauer sind und vor allem viel schneller sind, diese 3,1415... zu bestimmen. Das ist aber leider nicht bei allen physikalischen, biologischen, mathematischen... Vorgängen möglich, einen geeigneten, schnellen Algo zu finden, da zu oft viel zu viel Randwertprobleme einfliessen, die eine genau Bestimmung einfach unmöglich machen. Und genau da greift die MCM, da sie unabhängig von der Komplexität halbwegs vernünftige Aussagen machen kann. Voraussetzung ist aber immer wieder irgendein grundlegendes Modell, denn sonst nützt auch die MCM nichts. Beispiel aus meiner Diplomarbeit: Geht ein Lichtstrahl durch ein nicht transparentes Medium, so wird die Intensität geschwächt, und zwar exponentiell mit der Tiefe. Diese Kenntnis muss man haben, um über die MCM einen Lichtstrahl zu simulieren.

[glkgereon]

hmm....prinzipiell hat Jelly ja recht :?

Aber ich konnte es natürlich nicht lassen :)

Delphi-Quellcode:

function CalculatePi(Raster: Int64): Extended;
var i: Integer;
    Upper, Lower, T, RQuad: Int64;
    E: Currency; //Currency...selbe genauigkeit, 2 Byte weniger...die Nachkommastellen interessieren hier eh nicht
begin
  Upper:=0; Lower:=0;
  RQuad:=Raster*Raster; //Einmal Quadrieren reicht
  for i:=0 to Raster-1 do
    begin
    T:=i+1; // Wenns Integer bleibt gibts nen Overflow
    E:=Sqrt(RQuad - T*T);
    Inc(Upper,Ceil(E)); //Max und Min zählen
    Inc(Lower,Floor(E));
    end;
  Result:=2*(Upper+Lower)/RQuad; //Aus Durchschnitt PI berechnen 
end;

relevante rechenzeiten...
die gibts erst ab eine Rastergröße von ca. 1.000.000 (Athlon 2600+)

Übersicht:

Delphi-Quellcode:

Raster    Millisek Genauigkeit(Stellen) 
1000      0        2
10000     2        4
100000    21       5
1000000   214      6
10000000  2225     7
100000000 22681    8

gemessen mit QueryPerformanceCounter....

Sinnlos...aber es geht... :)