Ciąg fibonacciego - dla dużych wyrazów

Jak w temacie, mam za zadanie stworzyć program obliczający dowolny wyraz ciągu fibonacciego. Zakres wyrazów od 0-100000. Mój program oblicza jedynie trochę ponad 23000 wyrazów, a dalej kończy się skala typu danych i nie bardzo mam pomysł jak ten problem rozwiązać.

#include<iostream>
#include<cstdlib>
#include<iomanip>
using namespace std;
  long double f(int n)
{
	 long double *fib = new  long double[n];

	fib[0] = 1;
	fib[1] = 1;

	for(int i=2;i<n; i++)
	{
		fib[i] = fib[i-1] + fib[i -2];
	}

	return fib[n-1];
	delete [] fib;

};

int main()
{
	int n;
	cin>>n;
	cout<<setprecision(10000);
	cout<<f(n)<<endl;
	return 0;
};

GMP lub własny rodzaj bignumów.
PS

    return fib[n-1];
    delete [] fib;

Zdajesz sobie sprawę, że delete[] fib nigdy nie zostanie wykonane i masz przez to wyciek pamięci?

Zajrzyj do sąsiedniego wątku ;) http://4programmers.net/Forum/C_i_C++/259157-nty_wyraz_ciagu_sumowanie_komorek_dwoch_tablic

Nie wiem co masz na myśli pisząc 23000 wyrazów.
long double pozwala na poprawne zapisanie liczby całkowitej o długości 18 dziesiętnych cyfr znaczących.
(Prawie) Wszystkie twoje wyniki dłuższe niż 18 cyfr są tylko przybliżeniem.

Żeby dobrze to policzyć potrzebujesz kod na długie liczby. Tablica intów, gdzie każda komórka trzyma 9 cyfr dziesiętnych, będzie najlepszym rozwiązaniem (jakby obliczenia w systemie o podstawie miliard). Czemu miliard? Bo to jest największa potęga 10, która mieści się w int.
Wykorzystaj dodawanie pisemne, którego uczyli cię w szkole.

MarekR22 napisał(a):

Nie wiem co masz na myśli pisząc 23000 wyrazów.
long double pozwala na poprawne zapisanie liczby całkowitej o długości 18 dziesiętnych cyfr znaczących.
(Prawie) Wszystkie twoje wyniki dłuższe niż 18 cyfr są tylko przybliżeniem.

Żeby dobrze to policzyć potrzebujesz kod na długie liczby. Tablica intów, gdzie każda komórka trzyma 9 cyfr dziesiętnych, będzie najlepszym rozwiązaniem (jakby obliczenia w systemie o podstawie miliard). Czemu miliard? Bo to jest największa potęga 10, która mieści się w int.
Wykorzystaj dodawanie pisemne, którego uczyli cię w szkole.

Ok tylko po co to dodawanie, bo tej idei jakoś nie rozumiem.

tak dla pewności: czy na pewno twój program ma podać pełną wartość ciągu Fibonacciego dla dużych argumentów (n>90)?
Czy może masz podać tylko pierwsze x cyfr albo ostatnie x cyfr, albo wartość modulo m?
Wbrew pozorom to, są o wiele prostsze problemy.

Oto treść zadania:
Ciąg Fibonacciego zdefiniowany jest w następujący sposób: F1 = 1, F2 = 1, Fn = Fn−2 + Fn−1, dla n > 2.

Napisz program, który otrzymawszy numer wyrazu ciągu obliczy jego wartość.

Wejście:
W pierwszej (i jedynej) linii wejścia znajduje się liczba n (1 ≤ n ≤ 100000) — numer wyrazu ciągu.

Wyjście:
Na wyjściu należy wypisać wartość n-tego wyrazu ciągu.

Przykład

Wejście:
500
Wyjście:
139423224561697880139724382870407283950070256587697307264108962948325571622863290691557658876222521294125

fib(100000) ma 20898 cyfr.
http://www.wolframalpha.com/input/?i=fibbonacci%28100000%29
Licznie tego przez sumowanie to niezbyt dobry pomysł.
Trzeba skorzystać z właściwości ciągu Fibonacciego. Na polskiej wiki znajdziesz kilka możliwości.
Implementacji wielkich liczb nie unikniesz (chyba, że wolno ci korzystać z zewnętrznych bibliotek).

MarekR22 napisał(a):

fib(100000) ma 20898 cyfr.
http://www.wolframalpha.com/input/?i=fibbonacci%28100000%29
Licznie tego przez sumowanie to niezbyt dobry pomysł.
Trzeba skorzystać z właściwości ciągu Fibonacciego. Na polskiej wiki znajdziesz kilka możliwości.
Implementacji wielkich liczb nie unikniesz (chyba, że wolno ci korzystać z zewnętrznych bibliotek).

Phi^n/sqrt(5)

zatem dla k cyfr limitem będzie:
log Phi^n/sqrt(5) = n log(Phi) - sqrt5 < k

zatem: n < (k+sqrt(5)) / logPhi
co dla double k = 53 daje:

n < (53 + sqrt5)/logPhi = 79,53

Phi^80/sqrt(5) = 23416728348467685

dla quad około 2 razy więcej cyfr, czyli:
Fib(160) = ...

 Wejście:
500
Wyjście:
139423224561697880139724382870407283950070256587697307264108962948325571622863290691557658876222521294125

N-ty wyraz ciagu Fibannociego i taka kobyła?? Przeciez to ledwie 500-tny wyraz...U mnie wg. mojego programu to daje liczbe 315178285.
Moze to wyjscie to jest suma wszystkich wyrazow do n-tego...

A ten twój program czasem nie przekręca się dla tak dużego inta? ;) Bo to jest przecież 345 bitów. Jak napisałeś to w C i lecisz jakimś 32 czy 64 bitowym intem to wiesz ;]

Świetny Samiec napisał(a):

Kopiuj

 Wejście:
500
Wyjście:
139423224561697880139724382870407283950070256587697307264108962948325571622863290691557658876222521294125

N-ty wyraz ciagu Fibannociego i taka kobyła?? Przeciez to ledwie 500-tny wyraz...U mnie wg. mojego programu to daje liczbe 315178285.
Moze to wyjscie to jest suma wszystkich wyrazow do n-tego...

Odkopałeś jakiś stary wątek, a go nawet nie przeczytałeś! Może wtedy byś odkrył, że coś nie tak jest z twoim wynikiem.
http://www.wolframalpha.com/input/?i=fibbonacci(500)

To znaczy, ze ten klasyk ponizej:

 public static int fibanoci1(int n)
		{
			if (n == 0) {
				return 0;
			} else if (n == 1) {
				return 1;
			}else {
				return fibanoci1 (n - 2) + fibanoci1 (n - 1);
			}
			
		}

...nie dziala dla n > 100..?
Na rekrutacji mialem problem z ciagiem Fibbannociego. Umiem napisac program sumujacy parzyste wyrazy ciagu Fibbanocciego, ale dla duzych liczb, to strasznie dlugo liczy. Nawet iteracyjna wersja kodu, teoretycznie troche szybsza, zwraca jakies dziwne wyniki...jezeli juz cokolwiek wyliczy..

http://www.wolframalpha.com/input/?i=log(fibbonacci(100))%2Flog(2)
http://www.wolframalpha.com/input/?i=log(fibbonacci(94))%2Flog(2)
http://www.wolframalpha.com/input/?i=log(fibbonacci(93))%2Flog(2)
Czyli największy element ciągu Fibonacciego jaki mieści się w long long unsigned int (64 bity) to 93.
A ty używasz int czyli 31 bitów (liczba ze znakiem) czyli ostatni reprezentowalny element tego ciągu to 46:
http://www.wolframalpha.com/input/?i=log(fibbonacci(46))%2Flog(2)

Czyli największy element ciągu Fibonacciego jaki mieści się w long long unsigned int (64 bity) to 93.
A ty używasz int czyli 31 bitów (liczba ze znakiem) czyli ostatni reprezentowalny element tego ciągu to 46 

Dzieki za wyjasnienie. W takim razie to zadanie na rekrutacji bylo wredne..