Wie kann ich eine Zahl darstellen die den Wertebereich von 4 Byte übersteigt??

green-sound

Hallo allezusammen,

mir wurde von meinem Mathematik Lehrer die Aufgabe gestellte, die Billionste Zahl der Fibonacci-Folge herauszufinden.
Mein erster Gedanke war "Kein Problem, ich schreibe einfach ein kleines Programm das mir die Zahl herausgibt."

Leichter geasgat als getan:

Nachdem ich das Programm geschrieben habe, mußte ich feststellen das ich mir damit gerade einmal die 46. Zahl ausgeben kann. Das Problem ist das es keinen Variabeln Typ gibt welche mir so große Zahlen darstelen kann.

Also meine Frage....

Gibt es eine andere Möglichkeit, wie ich dies enorm große Zahl darstellen kann?

Hier noch mein kleiner Quellcode:

#include <stdio.h>

void main (void)
{
	unsigned int i,t,n=0,m=1;

	for (i=0;i<=100;i++)
	{
		t=m;
		n=n+m;
		m=n;
		n=t;
		printf("Fibonacci - Folge: %d. Zahhl: %d \n", i+1, n);
	}
}

Jay

Hi
hoffe das hilft dir --> http://www.swox.com/gmp/
http://de.wikipedia.org/wiki/GNU_Multiple_Precision_Arithmetic_Library

ten

oder das: http://www.mtholyoke.edu/courses/pdobosh/cs211/src/bigint.c
:xmas2:

Daniel E.

green-sound schrieb:

Mein erster Gedanke war "Kein Problem, ich schreibe einfach ein kleines Programm das mir die Zahl herausgibt."

Leichter geasgat als getan:

Nachdem ich das Programm geschrieben habe, mußte ich feststellen das ich mir damit gerade einmal die 46. Zahl ausgeben kann. Das Problem ist das es keinen Variabeln Typ gibt welche mir so große Zahlen darstelen kann.

Dir ist schon klar, wie groß das Ergebnis wird?

Man kann Fibonaccio-Zahlen abschätzen mit fib(n) ~= phi^n, wobei phi der goldene Schnitt ist (also = 1,618...).

fib(10^12) ~= phi⁽¹⁰12). Das ist in der Größenordnung von 2⁽¹⁰12), also werden zur Darstellung ca. 10^12 Bits benötigt, also ca. 10^11 Bytes. Ein GB sind sind ca. 10^9 Byte. Also ca. 100 GB pro Zahl in der relevanten Größenordnung.

Mein Tipp wäre, dieses Projekt nicht auf dem Heimcomputer durchzuführen.

Jay

btw.
es heißt "int main" und nicht "void main"

Rhombicosidodecahedron

green-sound schrieb:

Hallo allezusammen,

mir wurde von meinem Mathematik Lehrer die Aufgabe gestellte, die Billionste Zahl der Fibonacci-Folge herauszufinden.
Mein erster Gedanke war "Kein Problem, ich schreibe einfach ein kleines Programm das mir die Zahl herausgibt."

Warum über Rekrusion? Warum so kompliziert?

Mit freundlichen Grüßen und föhliche Weihnachten wünschend
Rhombicosidodecahedron