Unendlich viele Nachkommastellen

[Crazy Driver]

Hallo Leute,
Ich hab heute mal ein Programm zur Berechnung von PI geschrieben , jedoch gibt es jetzt
noch das Problem, dass double mir maximal 16 Nachkommastellen ausgibt.
Gibt es vielleicht eine Möglichkeit die Anzahl der Nachkommastellen bis ins Unendliche zu
erhöhen?

[oetzn]

Naja, ein 32-bit Betriebssystem kann nur mit 32bit langen Zahlen rechnen, sprich maximal 32 Nachkommastellen berechnen, OHNE spezielles Verfahren. Wenn du mehr haben willst, müssest du das in deinem Programm berücksichten. Einfach so kann man die Anzahl der Nachkommastellen nicht erhöhen ;)

[Zeroflow]

die "einfachste" Methode is : du speicherst das als String ab und nicht als Zahl.

schau dir da mal die http://de.wikipedia.org/wiki/Kreiszahl#BBP-Reihen an - da kannst du beliebige Stellen berechnen

ist zwar vl. nicht das optimale aber funktioniert

[IceMatrix]

Ins Unendliche sicher nicht. Denn Unendlich ist ziemlich unhandlich für eine Rechenmaschine ;)

Eine endliche Zahl von Nachkommastellen ist aber möglich. Das geht aber nicht mit float oder double, sondern dazu sind mathematische Bibliotheken nötig, die meist auf Integer-Basis arbeiten.

Ich habe dazu mal die GNU MP (http://gmplib.org/) Library verwendet.

Ergänzung vom 14.03.2011 22:16 Uhr:

Naja, ein 32-bit Betriebssystem kann nur mit 32bit langen Zahlen rechnen, sprich maximal 32 Nachkommastellen berechnen, OHNE spezielles Verfahren.


Deine "Bits" haben absolut nichts mit Nachkommastellen zu tun!

[oetzn]

Na gut das ich Halbwissen hinzugeschrieben hab, danke für die Aufklärung ;)

[LinuxMcBook]

Ja, ein Bit hat ja 2 Zustände. Also kann die Zahl 2^32 groß sein. Dürfen ungefähr 4 Mrd. sein. Oder die Hälfte, wenn es auch negative Zahlen sind. Vorzeichen hat ja auch ein Bit.

[platin91]

Du könntest auch die Zahlen nacheinander in ein Textdokument schreiben, dann fällt das Problem auch weg. HDD-Speicher gibts normal ja genug, oder ist C dazu nicht in der Lage?

Edit:
Nur der Vollständigkeit halber: Ein Integer hat in C auch nicht immer 32 Bit...

[NemesisFS]

klar ist c dazu in der lage. das programm sollte ohnehin immer die nächsten nachkommastelle berechnen, die kann man dann an eine beliebige ausgabe anhängen.


Ja, ein Bit hat ja 2 Zustände. Also kann die Zahl 2^32 groß sein. Dürfen ungefähr 4 Mrd. sein. Oder die Hälfte, wenn es auch negative Zahlen sind. Vorzeichen hat ja auch ein Bit.

ist so auch nicht richtig: stimmt für ganze zahlen, wie integer. float und double speichern zahlen über exponenten, was auf kosten der genauigkeit geht, dadurch sind aber enorm große zahlen darstellbar.

[quwieorp]

Unendlich viele Nachkommastellen sind unmöglich, weil man dafür unendlich viel Speicher braucht (in Form von RAM, Festplatten, Papier, ...), und unendlich lange rechnen müsste. Nach meinem jetzigen Kenntnisstand gibt es Ersteres nicht und Letzteres will sich niemand antun.

Schluss mit dem Geschwafel: Ich würde dir genau wie IceMatrix auch die GMP-Library empfehlen.

[NemesisFS]

unendlich lang ist genausounmöglich wie unendlich viel. aber ich denke, das wird nicht das gewesen sein, was der TE gemeint hat...

[Xetoxyc]

naja weis garnicht was da soviel zu sagen gibt

wie willst du unendlich darstellen ?
bzw wo ?
hast du einen unendlich großen bildschrim?
undendlich großen speicherplatz?

ne festplatte mit unlimitedByte statt TerraByte ?
also die frage is eigentlich mehr als peinlich wenn man es schafft ein programm zur berechnung von pi zu schreiben ;P

[quityper]

Naja, ein 32-bit Betriebssystem kann nur mit 32bit langen Zahlen rechnen, sprich maximal 32 Nachkommastellen berechnen, OHNE spezielles Verfahren. Wenn du mehr haben willst, müssest du das in deinem Programm berücksichten. Einfach so kann man die Anzahl der Nachkommastellen nicht erhöhen ;)


Einfach ausgedrückt:
Naja, zwei z.B. 32-bit Register der CPU können je 32bit lange Werte (0100...1) aufnehmen, das ALU Schaltnetz (arithmetic logic unit) berechnet dann aus den 2 Registern bit für bit das gewünschte Ergebnis.

Beispiel Addition für 8bit:
Register A = 10011010 (154)
Register B = 00110110 (54)

ALU berechnet daraus

Merker = 01111100
————————
Ergebnis = 11010000 (208)

und speichert das Ergebnis in einem anderen Register, der für weitere Berechnungen zur Verfügung steht.

Je nach Algorithmus kannst du damit auch 2^30000 berechnen (calc).

[IceMatrix]

Vorzeichen hat ja auch ein Bit.

nicht wirklich. vorzeichenbits gibts nur bei float/double (ieee 754) und der einerkomplementdarstellung (die aber niemand verwendet).
alle modernen prozessoren arbeiten mit zweierkomplement. da kannst du zwar am höchsten bit ablesen ob die zahl positiv oder negativ ist, jedoch ist das kein vorzeichenbit!

Ergänzung vom 15.03.2011 23:25 Uhr:
Einfach ausgedrückt:
Naja, zwei z.B. 32-bit Register der CPU können je 32bit lange Werte (0100...1) aufnehmen, das ALU Schaltnetz (arithmetic logic unit) berechnet dann aus den 2 Registern bit für bit das gewünschte Ergebnis.

Beispiel Addition für 8bit:

bezieht sich allerdings auf integer arithmetik. die registerlänge spielt bei big integer operationen hauptsächlich eine rolle bei der performance, besonders was multiplikation und division angeht.

Ergänzung vom 15.03.2011 23:27 Uhr:

Edit:
Nur der Vollständigkeit halber: Ein Integer hat in C auch nicht immer 32 Bit...

stimmt. allerdings gibts den unterschied nur bei 16-bit. ab 32-bit ist integer immer 32-bit.

[quityper]

...bezieht sich allerdings auf integer arithmetik. die registerlänge spielt bei big integer operationen hauptsächlich eine rolle bei der performance, besonders was multiplikation und division angeht...

Ist richtig, ALU nur fürs addieren, subtrahieren, und/oder-Verknüpfungen (logische Verknüpfungen). FPU (Floating Point Unit) mit noch breiteren Registern und speziellen Algorithmen für Berechnung. ALU und FPU sind getrennte Recheneinheiten in der CPU.

Ich hätte auch eine 64-Bit ALU beschreiben können, also, nur die Länge der Register ist ja nicht alleine ausschlaggebend für die Rechengeschwindigkeit, da die FPU intern auch nur ein Schaltnetz ist, aber wie du schon gesagt hast mit Registerbreiten von 80bit oder auch 128bit für mehr Geschwindigkeit, Genauigkeit und für Größere Werte.
Es bedarf aber auch verschiedener Algorithmen wie CORDIC oder fest implementierten Tabellen (siehe Pentium-Bug, heißt es), die als erste Näherung genommen werden. Register können speziell organisiert werden und die FPU hat feste Operationen für die Grundrechenarten mit hoher Genauigkeit auch für Wurzel-, Logarithmus-, Potenz-, trigonometrische Berechnungen und viele mehr.

[Timmey92]

Da ich bzw. unser Lehrer^^ das gerade im Mathe Unterricht behandelt: Welchen Algorithmus hast du verwendet?
Würde da auch gerne ein Programm schreiben und hänge bei meinen Planungen an zwei grundlegenden Stellen:

1. Welcher Algorithmus ist am besten geeignet?
2. Wie umgehe ich die begrenzung der Nachkommastellen?

Zu 1. habe ich an den hier gedacht: http://de.wikipedia.org/wiki/Bailey-Borwein-Plouffe-Formel

Verstehen tu ich den allerdings nicht - so kann man immer die benötigte Stelle von Pi berechnen (ohne Kenntniss der vorherigen!) und abspeichern in einem String oder einer Datei.

[ghorst]

BBP ist schon ein sehr guter Algorithmus für die Berechnung von pi. Den kannst du recht bedenkenlos benutzen. Es gibt zwar schnellere (Chudnovsky, Gauss-Legendre oder Borwein) aber die benötigen auch mehr Aufwand bei der Implementierung.

Was verstehst du an BBP nicht? (Abgesehen von der Herleitung und dem Beweis. Dafür musst du dir mal ein Büchlein über Reihenentwicklung durchlese.)

Das Problem der endlichen Nachkommastellen kannst du nicht lösen. Du kannst es nur umgehen, in dem du einen Algorithmus verwendest, der die Ziffern einzeln liefert, wie eben BBP und die Daten dann entweder, wie von du selber schon vorschlugst, in einem string speicherst oder die bei BBP anfallen Hex-Zahlen in dem oberen und unteren Nibble eines Bytes ablegst und die dann in einem Array speicherst. Spart die Hälfte des Platzes und lässt sich dann recht einfach in die übliche Floatingpointdarstellung umwandeln (natürlich Softwarefloatingpoint und entsprechend extrem langsam.).

[Timmey92]

Verstehe das Prinzip von der Gleichung irgendwie nicht, also wie ich das dann anwenden kann.
Ich habe hier diesen Code gefunden (über Google in C), den schau ich mir dann mal an und probier den mit .Net umzusetzen, vielliecht hilft er dem TE ja irgendwie auch.



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

#define step 1
#define maxcol 50
#define sp 10


// funktion pow16
// berechnet 16 hoch x mod n
long double pow16(int x, int n)
{
int msb; //position des most significant bit von x
int mask; //eine bitmaske
double foo; //ohne diesen umweg macht mein compiler leider sche*** ...
long double result;

//speziealfälle
if(x==0&&n==1)return 0;
if(x==0)return 1;
if(x==1)
{
return 16-n*(int)(16/n);
}

foo=(log(x)/log(2)); //logarithmus von x zur basis 2, abgerundet:
//höchstwertige bitstelle von x
//(bei 0 anfangen zu zählen da 2 hoch 0 = 1)
msb=foo;

mask=1<<msb-1; //wir setzen bit msb-1 von x in unserer maske
result=16; //initialisierung square and multiply algorithmus

// es folgt square and multiply...
for(;mask;mask=mask>>1)
{
result*=result;//square ... bei jedem schleifendurchlauf
if(x&mask)
result*=16; //multiply ... nur wenn dass entsprechende bit im
//exponenten gesetzt ist (siehe mask)
result-=n*(int)(result/n);//mod
}
result-=n*(int)(result/n);//mod
return result;
}

// funktion reihe
// berechnet die reihenformel für die ziffern die auf die stelle d folgen
// j bezeichnet den index der BBP formel
long double reihe(int d, int j)
{
int k;
long double result,jk,term;

result=(long double)0;

for(k=0;k<d;k++)//erste summe
/*
anmerkung:
laut der summenformel sollte hier k<=d als bedinung stehen...
k<d liefert allerdings das korrekte ergebnis, von daher gehe
ich davon aus, dass sich in die formel im pdf ein tippfehler
eingeschlichen hat, und der laufindex nur bis d-1 laufen sollte
anstatt bis d ...
*/
{
jk=8*k+j;
result += pow16(d-k,jk)/jk;
result -= (int)result; // auf gebrochenen anteil reduzieren
}
term=1.;
for(;term>1e-20;k++)//zweite summe
{
jk=8*k+j;
term=pow(16.,(double)d-k)/jk;
result += term;
result -= (int)result; // auf gebrochenen anteil reduzieren
}
return result;
}

int main(int argc, char *argv[])
{
int d,idx,col;
long double frac,s1,s4,s5,s6,pi;
char hex[]="0123456789ABCDEF";

d=0; //wir hätten gerne die berechnung der stellen nach stelle 0
//also ab der ersten dezimalstelle...

printf("berechne die ersten 1000 hexadezimalen Nachkommastellen von Pi:\n\n");

putchar('3');
putchar(',');
col=0;
while(1)
{

//die Sj nach gleichung 6
s1=reihe(d,1);
s4=reihe(d,4);
s5=reihe(d,5);
s6=reihe(d,6);

frac=4*s1-2*s4-s5-s6;//ergebnis zusammenbauen nach gleichung 2

//ergebnis in den richtigen bereich verschieben...
frac-=(int)frac;
if(frac<0)
frac+=1;
/*
anmerkung:
unser ergebnis ist aus der modulorechnung hervorgegangen, repräsentiert also eine restklasse.
diese restklasse hat unendlich viele mögliche repräsentanten, also werte die bezüglich dieser
restklasse kongruent (umgangssprachlich bedeutet "kongruent" soviel wie "gleichbedeutend")
sind ... da wir das suchen was bei pi hinter dem komma steht, wissen wir: das gesuchte ergebnis
liegt zwischen 0 und 1 ... somit wählen wir den vertreter der restklasse, der zwischen 0 und 1
liegt ...
*/

for(idx=0;idx<step;idx++)
{

if(col%sp==0&&col!=0&&col!=maxcol)
{//alle 10 zeichen ein space
putchar(' ');
col++;
fflush(stdin);
}
if(col>maxcol)
{//zeilenumbruch
putchar('\n');
putchar(' ');
putchar(' ');
col=0;
fflush(stdin);
}
frac*=16;
putchar(hex[(int)frac]);
col++;
frac-=(int)frac;
}
d+=step;
if(d>=1000) break;
}
printf("\n\n");

system("PAUSE");
return 0;
}

[uncool]

Da musst du wohl mit Strings arbeiten oder selber Variablentypen erfinden.

[ghorst]

Bitte sag doch mal, was du nicht verstehst.
Ohne Kontext bin ich reichlich ratlos, was du nicht verstehst, da der BBP-Algorithmus dir direkt die Ziffern im hexadezimal System liefert und du sie nur noch speichern musst. Hexadezimal ist wie 4-Bit auf einmal und passen entsprechend in ein Nibble (Halbes Byte).

[IceMatrix]

nimm http://en.wikipedia.org/wiki/GNU_Multi-Precision_Library