Produktfreie Formel von Vieta

D4RKS0UL23

Hallo,

ich habe in C++ die Produktfreie Formel von Vieta programmiert. Zuersteinmal lautet diese Formel π = 2^n*sqrt(2-sqrt(2+sqrt(2+sqrt(...))) für n→∞

Es ist also eine rekursive Formel zur ermittlung von Pi. Des Interesse halber wollte ich diese Formel nachprogrammieren. Das Programm dazu sieht so aus:

#include <iostream>
#include <iomanip>
#include <math.h>

using namespace std;

long double Product2(int n) {
	if (n==0)
		return 0;
	else {
		return sqrt(2 + Product2(n-1));
	}
}
long double Product(int n) {
	return pow(2, n)*sqrt(2 - Product2(n-1));
}

int main() {
	cout << std::setprecision(100) << Product(10);

	getchar();

	return 0;
}

Für n = 10 sieht das noch ganz gut aus (Pi ist bis auf 5 Nachkommastellen korrekt).
Für n=26 gibt er aber plötzlich 3.16227... aus, was nicht korrekt ist.
Für n=28 gibt er glatt 4 aus, und alles was 29 oder größer ist, ist einfach 0.

Habe ich einen Bug im Code, oder kann c++ lediglich nicht mit solchen kleinen Zahlen umgehen? (Immerhin wird 26mal die Wurzel aus zwei gezogen)

Vielen Dank.

SeppJ

Ohne genau nachzurechnen, an welcher Stelle es liegt: Ja, das klingt nach einem Genauigkeitsproblem. Das liegt nicht direkt an C++, sondern ist einfach die Genauigkeit von double-precision und der Datentyp double sagt, dass du eine Rechnung mit dieser Genauigkeit wünscht, also wird sie auch genommen. long double ist auf den meisten Systemen nicht größer als double und es ist auch nicht genau definiert, was long double genau ausmacht; es heißt jedenfalls nicht unbedingt quadruple precision, sonst hieße es schließlich quadruple. Es gibt auch Bibliotheken, die Rechnungen mit beliebiger Genauigkeit (natürlich begrenzt durch den Speicher deines Computers) erlauben.

Deine Symptome klingen wie gesagt ganz typisch für ein Genauigkeitsproblem. Wobei ich im Moment nicht nachvollziehen kann, wieso Zahlen von der Größenordnung 2^29 ein Problem sein sollten, double ist eigentlich viel genauer. Ich habe nicht die ganze Rechnung nachvollzogen, will aber auch nicht vollkommen ausschließen, dass ein andere Problem vorliegt. Du kannst ja mal Zwischenergebnisse anzeigen lassen und prüfen, ob diese sinnvoll sind.

camper

Das Verhalten ist wenig überraschend.
Produkt2 liefert für große n einen Wert nahe 2.
In Produkt kommt es dann aber auf die Genauigkeit der Differenz zwischen dieser Zahl und 2 an. Es ist also ein Genauigkeitsproblem. Und diese Darstellung schlicht nicht dafür geeignet Pi zu berechnen.

D4RKS0UL23

Danke für die Antworten.

Ich werde mir morgen mal die gmplib anschauen, da diese Scheinbar exakte arithmetik ermöglicht. Ich hätte nämlich keine Lust mit Zettel und Stift 100 Wurzeln aus zwei zu addieren.

Sowas geht in der Regel einfacher mit Mathematica oder anderen Mathematiktools. (folgendes geht zum Beispiel auch in Mathics)

f2pf[1] = 0;
f2pf[n_] := 2+Sqrt[f2pf[n - 1]];
Table[{n, N[2^n*Sqrt[2-Sqrt[f2pf[n]]], 20]}, {n, 1, 8}] //TableForm
1 2.8284271247461900976
2 3.0614674589207181738
3 3.1214451522580522851
4 3.1365484905459392619
5 3.1403311569547529108
6 3.1412772509327728874
7 3.1415138011443011584
8 3.1415729403670918280