[HaBo]

Xalon · 20.08.06, 15:23

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 ;-)

Jon2 · 20.08.06, 15:50

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?

Anzeige

- Anzeige -

lagalopex · 20.08.06, 16:29

Zitat:

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?

Bei der Frage der Genauigkeit, viele Datentypen sind diesbezüglich sehr begrenzt

(Ich geh mal davon aus, dass keine eigenen Typen zu entwerfen sind...)
Außerdem sind genaue Zeitmessungen vom Betriebssystem/Compiler/... abhängig.

Zitat:

Original von Jon2
danke erstmal das mein Vorschlag angenommen wurde.

Ich hab auch noch einen Vorschlag eingereicht

@Xalon Wo bleibt der eigentlich?! :]

Lösung in C++ mit long double Genauigkeit

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

Xalon · 20.08.06, 21:42

Zitat:

Original von lagalopex

Zitat:

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?

Naja ein Programm das x Stellen in y Sekunden errechnet is besser als eins das x in y*2 errechnet

Zitat:

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

lagalopex · 20.08.06, 22:14

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...

mig · 21.08.06, 23:37

Java

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

lagalopex · 22.08.06, 02:56

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

1000 Nachkommastellen von Pi in 70ms

Heinzelotto · 22.08.06, 09:32

hat jemand schon die Monte-Carlo-Methode ausprobiert? Bei der muss nicht viel herumgerechnet werden und sie ist trotzdem sehr genau.

mig · 22.08.06, 22:40

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!

Anzeige

- Anzeige -

20.08.06, 15:23	#1 (permalink)
Xalon Registriert seit: 23.05.05 Likes: 0	Pi Anzeige 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 ;-)

20.08.06, 15:50	#2 (permalink)
Jon2 Registriert seit: 02.08.06 Likes: 0	RE: Pi 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?

Themen-Optionen
Druckbare Version zeigen Jemanden per E-Mail auf dieses Thema hinweisen
Ansicht
Linear-Darstellung Zur Hybrid-Darstellung wechseln Zur Baum-Darstellung wechseln

20.08.06, 22:14	#5 (permalink)
lagalopex Registriert seit: 01.11.03 Likes: 0	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...

22.08.06, 09:32	#8 (permalink)
Heinzelotto Senior Member Registriert seit: 29.07.05 Likes: 0	hat jemand schon die Monte-Carlo-Methode ausprobiert? Bei der muss nicht viel herumgerechnet werden und sie ist trotzdem sehr genau.

22.08.06, 22:40	#9 (permalink)
mig Registriert seit: 12.08.06 Likes: 0	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!

[HaBo]

Pi