Berechnung von PI - Genauigkeitsproblem

[ComSubVie]

Ok, "Berechnung" ist vielleicht nicht ganz das richtige Wort. Ich habe einen Viertelkreis der in einem Quadrat ist. Die Seitenlänge des Quadrates bzw. der Radius des Kreises sei 1. Ich kann nun per Zufallsgenerator Punkte in dieses Quadrat fallen lassen, und kann anhand der Anzahl der Punkte die innerhalb des Kreises sind ( x²+y² < r²) auf Pi rückrechnen (Pi=4*Anzahl_quadrat/Anzahl_kreis).

Nach 2 Milliarden Punkten bekomme ich immer 3,141559 heraus. 'n Kollege von mir hat das Programm mit Visual C (ich verwende natürlich gcc) getestet und bekommt überhaupt nur 3,14 heraus, der erst schwankt....

Ist das ein Genauigkeitsproblem des Zufallsgenerators oder ein Problem mit der Genauigkeit der Varaiblentypen? Kann man das statistisch/numerisch irgendwie beweisen das es nicht genauer als [ergebnis des beweises hier einsetzen] gehen kann? Gibt es Verbesserungsvorschläge für mein Programm? (Kompiliert mit gcc -o pi pi.c -lm)

Anmerkung: wenn ich statt random() rand() verwende sollte das Ergebnis eigentlich das gleiche sein, ich muss das aber erst noch testen...

#include <stdio.h>
#include <stdlib.h>
#include <math.h>


int main()
{
  double x = 0;
  double y = 0;
  double anz_i = 0; //Anzahl Punkte im Kreis
  double anz_o = 0; //Anzahl Punkte im Quadrat
  double rad = 0;
  double pi = 0;
  int z = 0;

  while ( z < 2147000000 )
  {
    x = (double)( random() );
    y = (double)( random() );

    x /= (double)( RAND_MAX );
    y /= (double)( RAND_MAX );

    anz_o++;
    z++;

    rad = sqrt( x*x + y*y );

    if ( rad <= 1 )
      anz_i++;

    if ( ( z % 1000000 ) == 0 )
    {
      pi = ( 4. * anz_i ) / anz_o;
      printf( "z: %6d, pi: %f\n", z/1000000, pi );
    }
  }

  return 1;
}

[anda_skoa]

rand und radnom liefnern unter Linux ansich Werte nach dem selben Algorithmus.
random hat auf anderen Systemen oder alten Linuxsystemen aber einen besseren Algorithmus.

Eine Idee:
Wenn du das sqrt wegläßt, wird es vielleicht besser.
Also, wenn du direkt x^2 + y^2 <= r^2 vergleichst (r^2 ist ja auch 1)

Alternativ vielleicht nicht mit RAND_MAX normieren sondern x und y so lassen und mit
r= RAND_MAX vergleichen. Mit und ohne sqrt probieren.

Ciao,
_

[ComSubVie]

rand und random liefern das gleiche ergebnis (was ich vorher aufgrund der man-page von rand bereits angenommen habe).

Wenn ich das sqrt weglasse krieg ich das gleich raus. die werte die ich rauskriege (ab etwa 1,5 milliarden punkten) schwanken zwischen 3,14175 und 3,141559. Wenn das Programm beendet ist der letzte Wert aber immer 3,141559.

ich werd das noch mit RAND_MAX probieren - oder zumindest mit einem hohen wert, je nachdem ob RAND_MAX² in double passt oder nicht

aber für mich ist das irgendwie unlogisch das am ende IMMER das gleich rauskommt. Hm, ok, mal Genauigkeit erhöhen, weiter hinten müsst es schwanken. Aber trotzdem ist das irgendwie komisch. Ein Programmfehler?

[anda_skoa]

du sollteste auf jedenfall noch versuchen, das Resultat anders auszugeben.

%f macht glaub ich float aus deinem double.
probier mal %lf

Ciao,
_

P.S: wie hast du in deiner code Sektion im obersten Posting so schönes Syntaxhighlighitng geschafft?

[The Ripper]

Original geschrieben von ComSubVie
aber für mich ist das irgendwie unlogisch das am ende IMMER das gleich rauskommt. Hm, ok, mal Genauigkeit erhöhen, weiter hinten müsst es schwanken. Aber trotzdem ist das irgendwie komisch. Ein Programmfehler?

der zufallsgenerator muss erst mit srandom() initialisiert werden.

Beispiel:

#include <stdio.h>
#include <sys/time.h>
#include <time.h>

int main(void)
{
        struct timeval tv;
        int i;

        // Zufallsgenerator initialisieren
        gettimeofday(&tv, NULL);
        srandom(tv.tv_usec);

        // 10 Zufallszahlen erzeugen
        for (i=0; i < 5; i++)
                printf("%d\n", random());

        return 0;
} 

wenn du den Aufruf von srandom() auskommentierst werden bei jedem Start des Programms die 5 selben Zufallszahlen erzeugt.

[Sion]

Original geschrieben von ComSubVie
Gibt es Verbesserungsvorschläge für mein Programm?

Ich selbst hab' keine Vorschläge, aber schau dir doch mal ein paar Varianten zur Berechnung von pi an (kommt von snippets.org).
Vielleicht kommst du ja damit weiter...

Gruß

[nobody0]

Ich habe verschiedenste Tests über random u. urandom laufen lassen und die wurden alle bestanden; die sind ok.
Die Genauigkeit kann nach dem zentralen Grenzwertsatz nur mit 1/sqrt(n) besser werden und ein n von zwei Millarden bringt weniger als 6 Stellen Genauigkeit.

[ComSubVie]

Danke! Werd wohl mal nach dem Grenzwertsatz google'n