Ich habe eine Aufgabe gestellt bekommen und muss Pi mit Hilfe des Monte-Carlo-Verfahrens berechnen. Ich habe mich mal an wikipedia gehalten:
http://de.wikipedia.org/wiki/Kreiszahl#Programm
Ich habe beide Programme in VBS übersetzt und ausprobiert, jedoch sind die Ergebnisse nicht wirklich zufriedenstellend.
Erste Methode
Quellcode:Function MyPi(shots As Long)
Dim x As Long
Dim y As Long
Dim t As Long
Dim o As Long
t = 0
o = (2 * shots + 1) ^ 2
For x = -shots To shots
    For y = -shots To shots
        If x ^ 2 + y ^ 2 <= shots ^ 2 Then
            t = t + 1
        End If
    Next y
Next x
MyPi = 4 * t / o
End Function
Zweite Methode
Quellcode:Function EstimatePi(shots As Long)
Dim x As Double
Dim y As Double
Dim t As Long
Dim i As Double
t = 0
For i = 0 To shots
    Randomize
    x = Rnd()
    Randomize
    y = Rnd()
    If x ^ 2 + y ^ 2 <= 1 Then
        t = t + 1
    End If
Next i
EstimatePi = 4 * t / shots
End Function
Bei der erstn Methode "MyPi" kann ich _maximal_ 1000 shots machen, es gehen zwar mehr aber der Rechner rechnet schon so recht lange (sind immerhin 2 * 1000 ^ 2 durchläufe in der For-schleife)
Das Ergebnis ist dafür mehr oder weniger akzeptabel:
Ausgabe MyPi(x)
Quellcode:x     Pi
1     2.2222
10    2.875283447
100   3.110517066
1000  3.138409806
10000 3.141276395
Beid er zweiten Methode "EstimatePi" kann ich einen Wert bis zu 10'000'000 angeben um noch eine akzeptable geschwindigkeit zu erhalten (er rechnet 5 - 10 Sekunden) Dafür schwankt das Ergebnis stark und ist IMO nicht wirklich besser, insbesondere da ein hörerer shots-Wert die genaugigkeit eigentlich nicht steigert..
Ausgabe EstimatePi(x)
Quellcode:x    Pi
1        4
10       3.2
100      3.36
1000     3.38
10000    3.604
100000   3.07272
1000000  3.139072
10000000 3.1372516
Wie könnte man diese Algorithmen noch verbessern? Der Artikel auf wikipedia "verspricht" ja eigentlich mit der ersten Methode "MyPi" bereits mit 100 shots eine gute genauigkeit von 3.1717. Ich habe "nur" 3.1105 .. Ich habe mal 10'000 shots versucht, aber mein Excel hat sich dabei aufgehängt ^^ naja, sind immerhin 200 millionen for-schleifen durchgänge... ich hab dabei auf ein genaueres Pi gehofft.
#edit, nach etwa 5 Minuten kam 3.141276395 raus

Kennt jemand noch bessere/andere Wege für eine Pi berechnung? Meine Aufgabenstellung sagt zwar mittels Monte-Carlo, aber irgendwie scheint mir das doch sehr unbefriedigend (oder ich hab was verbockt im Code)

Gruss

Also die erste Methode ist schonmal nicht Monte-Carlo, weil sie nicht mit Zufallszahlen, sondern mit einem Raster arbeitet. Daher ist dein Ergebnis auch genauer, aber mit höherem Rechenaufwand verbunden, wie du ja gemerkt hast.

Musst du denn die Berechnung unbedingt in VBS schreiben? Eine simple C-Konselenanwendung ohne Zwischenausgaben ist sicher um einiges schneller. Aber ich denk mal, dass das leider vorgegeben ist.

Sonst kannst du auch die Monte-Carlo-Methode mit 1'000'000 ein paar Mal laufen lassen und dann den Mittelwert aus den verschiedenen Ergebnissen berechnen. Das könnte einen Vorteil gegenüber der Erhöhung der Shots um den Faktor 10 geben, vor allem was die Geschwindigkeit betrifft.

Da ich gerade nicht viel zu tun habe, hab ich das mal ausprobiert - ich komm mit dem folgenden Code immer auf PI von ~3.1622, dauert aber auch ein paar Sekunden. Die Mittelwertberechnung bringt aber auch nur in der 3. Nachkommastelle was, also nicht so viel wie erwartet.
Quellcode:#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

double estimate();

int main(int argv, char** argc) {
    unsigned int seed = time(0);
    srand(seed);
    printf("seed: %d\n", seed);

    double pi = 0;
    for(int i = 0; i < 20; i++)
        pi += estimate();
    pi /= (double)20;

    printf("PI: %lf\n", pi);
    
    getchar();
}

double estimate() {
    int count = 1000000;
    int hit = 0;

    double x, y;
    for(int i = 0; i < count; i++)
        if(sqrt(pow((double)(rand() % 1000), (double)2) + pow((double)(rand() % 1000), (double)2)) <= 1000)
            hit++;

    return 4 * hit / (double)count;
}


Methode 1 kannst erstmal wegwerfen: Nicht Monte-Carlo (nicht zufällig gewählte Werte) und O(n^2).
Mir ist schleierhaft, wie die Menschen auf Wikipedia auf 3.1417 mit shots = 100 kommen wollen. Das Ding liefert auch in PHP/C/C++/C# 3.1105...

Dass die Berechnung von Pi mittels Monte-Carlo ungenau ist, ist gewollt. Dafür kannst du aber auch eine statistische Sicherheit für den Fehler/die Korrektheit des ermittelten Wertes angeben.
VBS ist der Performance btw sicher nicht unbedingt zuträglich. Aber da du ja schon schreibst, dass Excel abgestürzt ist, nehme ich an ist das Teil der Aufgabe.

edit:
Args hatt ich den Thread jetz schon über ne viertel Stunde offen -.- Verdammte Arbeit hält einem vom Posten ab :D
Wie Jean schon schreibt wirst wohl mit mehreren Durchläufen + Mittel nen ordentlichen Wert in annehmbarer Zeit erreichen.

edit2:
Da du ja noch nach anderen Methoden gefragt hast:
http://de.wikipedia.org/wiki/Kreiszahlberechnung_nach_Leibniz
Hier lohnt es sich nach nem gewissen Schwellwert Epsilon einfach abzubrechen. Die Floating-Point-Darstellung gibt ohnehin nur ne gewisse "Genauigkeit" her.

The C language combines all the power of assembly language with all the ease-of-use of assembly language.
"humorig is n blödwort :>" by -CarniGGeLjumpR-

Das beruhigt mich sehr, dass ihr ähnliche Ergebnisse erhaltet. Sind eben meine ersten Schritte mit VBS. Es muss auch in VBS gemacht werden, da die Vorlesung "Finance mit Excel und VBS" heisst :D
aber gut, wenn's nicht genauer geht. Die Aufgabe hiess:

Zitat:

Programmieren Sie eine Funktion, die Pi mit Hilfe des Monte-Carlo
Verfahrens abschätzt. Die Funktion nimmt ein Argument entgegen
(eine positive ganze Zahl) welche angibt, wie viele "Pfeile auf das
Quadrat abgeschossen werden."

@LeJean
Der Ansatz mit dem Mittelwert hab ich in Excel auch ma versucht, aber bringt bei mir keine Verbesserungen. streut immernoch wild umher. -> Ich hab au wie du ne zweite Funktion geschrieben, die die erste 20 mal aufruft und die Summe durch 20 teilt, aber hat nix gebracht..

danke für die Antworten und Denkansätze

Du solltest eventuell den Pseudozufallsgenerator nicht fuer jede neue Zufallszahl neu initialisieren.

\o tanz den naziprau! o/

And more than ever, I hope to never fall,
Where enough is not the same it was before

Zitat:

theDon postete
Du solltest eventuell den Pseudozufallsgenerator nicht fuer jede neue Zufallszahl neu initialisieren.

#edit
ein einmaliges aufrufen der funktion mit 10'000'000 shots bringt jeweils ein ergebnis von 3.141x
also schon recht gut finde ich

du findest es gut, mit 10mio (bzw 20mio^2) iterationen pi auf ~4 stellen genau zu berechnen?
klingt nicht grad effizient

caedes

Deutschland rückt nach Einschätzung der Sicherheitsbehörden im Superwahljahr verstärkt ins Visier von Terroristen.

nein, effizient ist anders ^^
aber so will es die Aufgabe nun mal. Drum wie gesagt, falls jemand noch nen besseren Ansatz hat im Rahmen der Aufgabenstellung das Teil ein wenig performanter und präziser zu gestalten, dann wär ich froh drum. Aber ich schätze da ich nur den Einen Ansatz brauchen darf, is des Ok so..

FYI:
Ich habe die Funktion MyPi etwas umgeschrieben:
Quellcode:Function MyPi(shots As Long)        ' Keine echte Monte-Carlo-Simulation, aber bringt genauere
Dim x As Long                       ' Ergebnisse. Jedoch sehr rechenaufwändig.
Dim y As Long                       ' Erträgliche Ergebnisse werden mit Argumenten bis 10'000 ausgerechnet
Dim t As Long                       ' MyPi(10000) = 3.1414
Dim o As Long
Dim z As Long
t = 0
o = (2 * shots + 1) ^ 2
For x = 0 To shots
    z = 0
    If x < shots Then               ' Das Dreieck (0,0)-(shots,0)-(0,shots) muss nicht
        z = shots - x               ' berechnet werden, da dieses Dreieck vollständig im
    End If                          ' Kreis liegt.
    For y = z To shots
        If x ^ 2 + y ^ 2 <= shots ^ 2 Then
            t = t + 1
        End If
    Next y
Next x
t = t + (shots * shots / 2)         ' Das Dreieck muss wieder dazuaddiert werden
MyPi = 4 * 4 * t / o                ' hochrechnen auf den ganzen Kreis
End Function
Bringt viel schneller Ergebnisse, da ich das Dreieck, welches komplett im Kreis liegt nicht unnötigerweise durchrechne. Nur etwas kapier ich nicht:
warum muss ich in der zweitletzten Zeile 4 * 4 * t / o machen und nicht nur 4 * t / o damits stimmt? eigentlich rechne ich ja das fehlende Dreieck in der 3. letzten Zeile bereits dazu... Wo hab ich da den Denkfehler?

Gruss