Fibonacci Sequence

[danno704]

I'm trying to find the first term of the fibonacci sequence that has 1000 digits. When I print the terms, the first 40 are positive, but then some of them begin to turn negative.


#include <iostream>
using namespace std;

int main()
{
int i,j,k,count;
count = 1;
i = 0;
j = 1;
while (k < 10^(999))
{
k = i + j;
i = j;
j = k;
count++;
cout << k << ", " << count << endl; //included this line because it wasn't working before
}
cout << endl << count << endl;
return 0;
}

[Duthomhas]

You do know that there is an upper limit on the number of digits representable by an int, right?

You need a bignum library to handle numbers with 1000 digits.
Two very good libraries, in order of ease of use, are:

  ■ http://www.ttmath.org/ttmath
  ■ http://gmplib.org/

Hope this helps.

[helios]

No current computer system that I know of has a native integer type capable of holding such a large value. Since this looks like homework, you're probably meant to represent the values using arrays of integers and implement in C++ the addition algorithm you learnt in elementary school.

By the way, look up the meaning of ^ in C/++. It doesn't mean exponentiation.

[Raggers]

Fn = Fn-1 + Fn-2 is a way to calculate Fibonacci but there is a formula to get Fn without knowing Fn-1 or Fn-2: Fn = ( (1 + sqrt(5))^n - (1 - sqrt(5))^n) / (2^n * sqrt(5))

Int can't hold a number that big. No C++ implementation can, not even in a long int.

but then some of them begin to turn negative

This is a overload, meaning you number is bigger then the int can hold and overloads. In doing so a int will overflow in to the sign bit of the int and turn negative. Not only negative, but it's value is rubbish.

If this is homework, as helios was saying, you need a array of int's to represent your value. It's not to hard to make something like this. I suggest you take a look in to that and come back here if you hit a problem.

[R0mai]

Raggers wrote:

overload

You mean overflow.

[Browni3141]

The largest integer data type I know of in C++ is uint64_t. It is a 64 bit data type and can hold data up to 2^64-1. It can also be called __hyper or long long. However these still won't be big enough for a 1000 digit number.

[Raggers]

@Romain:
Yes sorry, I mean overflow, typo :p

[EzwRko23]

Hint: this is the 4782st term of the Fibonacci sequence.

[Catamaran]

It's depands on what you need it for. If only to show on the screen or write to the file, you could use string array to do it. You need only to add single digits.

[EzwRko23]

It looks like the Euler project #25.

[Athar]

If this is for said Euler project, then there is no need to actually compute the number in full precision, so no bignum library is needed. double (or even float) is sufficient.

[Raggers]

It's not that hard to extend the number of digits a int can hold. Just write your own class...
Something that holds an array of bytes, if byte 0 overflows, increase byte 1 by one and so on.
You can do this by testing if the last bite of the byte is 0, if not increase the next byte by one and put the bite back to 0 and else do nothing. All you need to do is some binary logic and math, if you make the array size variable you can hold a int as big as your ram supports.
My 1st project was something like this but the other way around, I had to hold a fixed of "infinite" precision.