Pi

Hi,
folgende Aufgabe kommt von Jon2:

Es ist die Kreiszahl Pi zu berechnen,und zwar so GENAU wie möglich.
Außerdem gilt je schneller desto besser .

Happy Coding,
Xalon


P.S:Ob das jetzt Schwierigkeit 2 oder 3 ist,keine Ahnung,ich habs selber nie versucht
zu berechnen ;-)
 
Hi

danke erstmal das mein Vorschlag angenommen wurde.
Ich habs auch nocht gemacht aber 1ch versuchs gleich.

Wenn einer das programm geschrieben hat kann er ja mal vergleichen ->klick

mfg Jon2

EDIT: mein problem bei der Aufgabe ist das Windows nur eine Begrenzte anzahl nachkomma stellen rechnet. Hat je mand eine idee was man dagegen machen kann?
 
Original von Xalon
Es ist die Kreiszahl Pi zu berechnen,und zwar so SCHNELL und GENAU wie möglich.
Kurze Frage... schließen sich deine Kriterien nicht aus? :p
Bei der Frage der Genauigkeit, viele Datentypen sind diesbezüglich sehr begrenzt X(
(Ich geh mal davon aus, dass keine eigenen Typen zu entwerfen sind...)
Außerdem sind genaue Zeitmessungen vom Betriebssystem/Compiler/... abhängig.

Original von Jon2
danke erstmal das mein Vorschlag angenommen wurde.
Ich hab auch noch einen Vorschlag eingereicht :)
@Xalon Wo bleibt der eigentlich?! :]

Code:
#include <iostream>
#include <iomanip>
#include <math.h>
#include <sys/time.h>

using namespace std;

/* Johann Heinrich Lambert */
long double pi1()
{
	unsigned long i = 25;
	long double r = i * 2;
	for(; i > 0 ; --i)
		r = (i * 2 - 1) + i * i / r;
	return(4.0 / r);
}

/* Leibniz */
long double pi2()
{
	long double r = 4.0;
	for(unsigned long i = 3 ; i < 350000000 ; i += 4)
		r += 4.0 / (long double) (i + 2) - 4.0 / (long double) i;
	return(r);
}

/* John Wallis */
long double pi3()
{
	long double r = 2.0;
	unsigned long a = 1, b = 2;
	for(; b < 30000000 ; b += 2, a += 2)
		r *= (b / (long double) a) * (b / ((long double) a + 2));
	return(r);
}

/* Bailey-Borwein-Plouffe */
long double pi4()
{
	long double r = 0;
	for(unsigned long i = 0 ; i <= 13 ; ++i)
		r += 1 / powl(16, i) * (4 / (8 * (long double) i + 1) - 2 / (8 * (long double) i + 4) - 1 / (8 * (long double) i + 5) - 1 / (8 * (long double) i + 6));
	return(r);
}

/* Archimedes */
long double pi5()
{
	long double r = 2 * sqrtl(3), b = 3;
	while (r != b) {
		r = 2 * r * b / (r + b);
		b = sqrtl(r * b);
	}
	return(r);
}

int main()
{
	struct timeval a, b;
	long long t;
	cout << "pi          = 3.1415926535897932384626433832795028841971693993751058209749" << endl;

	gettimeofday(&b, 0);
	cout << "Lambert     ~ " << setw(26) << setprecision(25) << pi1() << "   ";
	gettimeofday(&a, 0);
	t = (a.tv_sec - b.tv_sec) * 1000000 + a.tv_usec - b.tv_usec;
	cout << t << " ?s" << endl;

	gettimeofday(&b, 0);
	cout << "Archimedes  ~ " << setw(26) << setprecision(25) << pi5() << "   ";
	gettimeofday(&a, 0);
	t = (a.tv_sec - b.tv_sec) * 1000000 + a.tv_usec - b.tv_usec;
	cout << t << " ?s" << endl;

	gettimeofday(&b, 0);
	cout << "BBP         ~ " << setw(26) << setprecision(25) << pi4() << "   ";
	gettimeofday(&a, 0);
	t = (a.tv_sec - b.tv_sec) * 1000000 + a.tv_usec - b.tv_usec;
	cout << t << " ?s" << endl;

	gettimeofday(&b, 0);
	cout << "Leibniz     ~ " << setw(26) << setprecision(25) << pi2() << "   ";
	gettimeofday(&a, 0);
	t = (a.tv_sec - b.tv_sec) * 1000000 + a.tv_usec - b.tv_usec;
	cout << t << " ?s" << endl;

	gettimeofday(&b, 0);
	cout << "Wallis      ~ " << setw(26) << setprecision(25) << pi3() << "   ";
	gettimeofday(&a, 0);
	t = (a.tv_sec - b.tv_sec) * 1000000 + a.tv_usec - b.tv_usec;
	cout << t << " ?s" << endl;

	return(0);
}
Beispielausgabe:
Code:
pi          = 3.1415926535897932384626433832795028841971693993751058209749

Lambert     ~ 3.141592653589793238512809   3 ?s
Archimedes  ~ 3.141592653589793238512809   3 ?s
BBP         ~ 3.141592653589793238295969   5 ?s
Leibniz     ~ 3.141592659304079603347845   1686080 ?s
Wallis      ~ 3.141592601229915733595036   292409 ?s
 
Original von lagalopex
Original von Xalon
Es ist die Kreiszahl Pi zu berechnen,und zwar so SCHNELL und GENAU wie möglich.
Kurze Frage... schließen sich deine Kriterien nicht aus? :p
Naja ein Programm das x Stellen in y Sekunden errechnet is besser als eins das x in y*2 errechnet ;)
danke erstmal das mein Vorschlag angenommen wurde.
Ich hab auch noch einen Vorschlag eingereicht :)
@Xalon Wo bleibt der eigentlich?! :]

Es waren sogar 3 Stück,einen hab ich bereits eingestellt,ein anderer wurde von Elderan
eingestellt und den 3. werd ich noch einstellen aber der is net grade schwer zu lösen ;)

Xalon
 
Es geht ja auch nicht darum, möglichst schwere Aufgaben zu stellen. Sie sollen zu lösen sein, und wenn es zu mindest eine Übung für einen Anfänger ist...
 
Code:
  import java.lang.Math;

public class Pi{
	// Archimedes
	public void archimedes() {
		double pi = 2* Math.sqrt(3);
		double b = 3;
		while (pi != b) {
			pi = 2*pi*b/(pi+b);
			b = Math.sqrt(pi*b);
		}
		System.out.print("Archimedes: 			"+pi);
	}
	
	// Streifenmethode
	public void streifenmethode() {
		long streifen = 10000;
		double pi;
		double breite = 1./streifen;
		double speicher=0;
		
		for(long i=1;i<streifen;i++) 
			speicher = speicher + Math.sqrt(1-Math.pow((i*breite),2))*breite;			
		
		pi=(speicher+breite/2)*4;
		System.out.print("Streifenmethode: 		"+pi);
	}
	
	// Monte-Carlo-Algorithmus
	public void statisch() {
		int tropfenzahl = 10000;
		double pi = 0;
		int innerhalb = 0;
		int gesamt = tropfenzahl;

  		while (tropfenzahl > 0) {
		    double dotx = 2 * Math.random() - 1;
		    double doty = 2 * Math.random() - 1;
		    
		    if (dotx*dotx + doty*doty <= 1) {
		      innerhalb++;
		    } else {
		    }
		    tropfenzahl--;
		}
		pi = 4*(double)innerhalb/gesamt;
		System.out.print("Statisch: 			"+pi);
	}
	
	// John Wallis
	public void wallis() {
		double pi=1.;
		for(int i =1; i < 10000; i++) 
			pi = pi * (1.+1./(4.*Math.pow(i,2.)-1));
		
		System.out.print("Wallis: 			"+(2*pi));
	}
	
	// Gottfried Wilhelm Leibniz
	public void leibniz() {
		double pi=0;
		for(int i = 0; i<10000;i++) 
			pi = pi + (Math.pow(-1,i)/(2*i+1));

		System.out.print("Leibnizp: 			"+(pi*4));
	}
	
	// Johann Heinrich Lambert 
	// Implementierung von lagalopex übernommen.
	public void lambert() {
		int i = 10000;
		double r = i * 2;
		for(; i > 0 ; --i)
			r = (i * 2 - 1) + i * i / r;
		System.out.print("Lambert: 			"+(4./r));
	}
	
	// Bailey-Borwein-Plouffe-Formel
	public void bbp() {
		double pi = 0.;
		for(int k = 0;k<10000;k++) 
			pi = pi + 1/Math.pow(16.,k)*((4./(8.*k+1.)-2./(8.*k+4.)-1./(8.*k+5.)-1./(8.*k+6.)));
		System.out.print("Bailey-Borwein-Plouffe-Formel:  " +pi);
	}
	
	public static void main(String[] args) {
		Pi p = new Pi();
		System.out.println("PI:				3.1415926535897932384626433\n");
		long a,b;
		
		a = System.nanoTime();
		p.archimedes();
		b = System.nanoTime();
		System.out.println("		"+(b-a)/1000000 + " ms");
		
		a = System.nanoTime();
		p.streifenmethode();
		b = System.nanoTime();
		System.out.println("		"+(b-a)/1000000 + " ms");
		
		a = System.nanoTime();
		p.statisch();
		b = System.nanoTime();
		System.out.println("				"+(b-a)/1000000 + " ms");
		
		a = System.nanoTime();
		p.wallis();
		b = System.nanoTime();
		System.out.println("		"+(b-a)/1000000 + " ms");
		
		a = System.nanoTime();
		p.leibniz();
		b = System.nanoTime();
		System.out.println("		"+(b-a)/1000000 + " ms");
		
		a = System.nanoTime();
		p.lambert();
		b = System.nanoTime();
		System.out.println("		"+(b-a)/1000000 + " ms");
		
		a = System.nanoTime();
		p.bbp();
		b = System.nanoTime();
		System.out.println("		"+(b-a)/1000000 + " ms");		
	}	
}

@lagalopex: Wie bist du auf diese Formel von Johann Heinrich Lambert gekommen?( (bzw zu dieser Umformung)
Hatte große Probleme diesen Kettenbruch umzuformen und hab es an sich auch bis jetzt nicht geschaft. Deswegen habe ich mir deine Implementierung ausgeliehen ;) von der ich zwar versteh was sie macht ... aber nicht warum das so sein muss?


so zu den Messergebnissen: (variiren)
Code:
PI:                             3.1415926535897932384626433

Archimedes:                     3.141592653589792               4 ms
Streifenmethode:                3.1415914776113167              2 ms
Statisch:                       3.1428                          7 ms
Wallis:                         3.1415141108281714              3 ms
Leibnizp:                       3.1414926535900345              2 ms
Lambert:                        3.141592653589793               1 ms
Bailey-Borwein-Plouffe-Formel:  3.141592653589793               12 ms

könnte man auch genauer machen ... nur alles wieder auf BigDouble umzuschreiben ... fehlt mir die Motivation.


mfg mig
 
Wenn man es rekursiv löst, kommt man auf das selbe (bei einer Abbruchbedingung von 25).
Setzt man dann alles rückwärts wieder zusammen, kommt man in etwa auf meine Formel :)

Code:
const int ARR_LEN = 1001;

void __divi(unsigned long x, unsigned short *y)
{
	unsigned long a = 0, b;
	for(int i = 0 ; i < ARR_LEN ; ++i) {
		b = y[i] + a;
		y[i] = b / x;
		a = 10 * (b - x * y[i]);
	}
}

void __muli(unsigned long x, unsigned short *y)
{
	unsigned long a = 0;
	for(int i = ARR_LEN - 1 ; i >= 0 ; --i) {
		a = y[i] * x + a;
		y[i] = a % 10;
		a /= 10;
	}
}

void calc_pi()
{
	unsigned short arr[ARR_LEN];
	int i;
	for(i = 0 ; i < ARR_LEN ; ++i)
		arr[i] = 0;

	for(i = ARR_LEN * 1.661; i > 0 ; --i) {
		__divi(8 * i * (2 * i + 1), arr);
		__muli((2 * i - 1) * (2 * i - 1), arr);
		arr[0] += 3;
	}

	for(i = 0 ; i < ARR_LEN ; ++i) {
		cout << arr[i];
		if(i == 0)
			cout << ".";
		if(i > 4 && i%100 == 0)
			cout << "\n  ";
		else if(i > 4 && i%5 == 0)
			cout << " ";
	}
	cout << endl;
}
Quelle
 
Hab ihn eigentlich in meinem Code von Wiki übernommen:

// Monte-Carlo-Algorithmus
public void statisch() {
int tropfenzahl = 10000;

Allerdings ist das Ergebnis mit 10000 Tropfen relativ ernüchternd:
siehe Ergebnis unter statisch;
Im vergleich zu den anderen Verfahren ist der Code relativ schlecht.

ps. @lagalopex den Code von dir muss ich mir morgen nochmal anschauen grad zu müde dafür. aber thx erstmal!
 
Zurück
Oben