Take the 2-minute tour ×

Here is my implementation of Problem 25 - Project Euler (see comments in code for explanation of how it works):

#include <iostream> //Declare headers and use correct namespace
#include <math.h>

using namespace std;

//Variables for the equation F_n(newTerm) = F_n-1(prevTerm) + Fn_2(currentTerm)
unsigned long long newTerm = 0;
unsigned long long prevTerm = 1; //F_1 initially = 1
unsigned long long currentTerm = 1; //F_2 initially = 2

unsigned long long termNo = 2; //Current number for the term

void getNextTerms() { //Iterates through the Fib sequence, by changing the global variables.
    newTerm = prevTerm + currentTerm; //First run: newTerm = 2
    unsigned long long temp = currentTerm; //temp = 1
    currentTerm = newTerm; //currentTerm = 2
    prevTerm = temp; //prevTerm = 1
    termNo++; //termNo = 3

unsigned long long getLength(unsigned long long number) //Returns the length of the number
    unsigned long long length = 0;
    while (number >= 1) {
        number = number / 10;
    return length;

    while (true) {
        getNextTerms(); //Gets next term in the Fib sequence
        if (getLength(currentTerm) < 1000) { //Checks if the next terms size is less than the desired length
        else { //Otherwise if it is perfect print out the term.
            cout << termNo;

This works for the example, and will run quickly as long as this line:

        if (getLength(currentTerm) < 1000) { //Checks if the next term's size is less than the desired length

says 20 or lower instead of 1000. But if that number is greater than 20 it takes a forever, my patience gets the better of me and I stop the program, how can I make this algorithm more efficient?

If you have any questions just ask in the comments.

share|improve this question
The max value of an 128bit unsigned long long is something like 3*10^38. That's much too small to hold a thousand-digit number. –  Mat Jul 11 '11 at 5:14
@Mat: Do you have any suggestion on what to do about that? –  Bair Jul 11 '11 at 5:15
Generally speaking, a long long will be 64-bits - the largest number that can be represented by such a type (if it's unsigned) is 18446744073709551615, which has 20 digits. There's no way to represent a number that has 1000 digits with that type (which is why it's taking your program forever - it can't be done). To find a fibonacci number with 1000 digits, you won't be able to just use long long types - you'll need represent the numbers in some other way, –  Michael Burr Jul 11 '11 at 5:16
For C bigint libraries, see "'BigInt' in C?" and "What is the simplest way of implementing bigint in C?" –  outis Jul 11 '11 at 5:34
The goal of project euler is to have fun while looking for a solution, asking for help will just spoil the fun IMHO, for your problem, quick way is to use python which handles big number natively –  Bruce Jul 11 '11 at 5:58

5 Answers 5

up vote 3 down vote accepted

There is a closed formula for the Fibonachi numbers (as well as for any linear recurrent sequence).

So F_n = C1 * a^n + C2 * b^n, where C1, C2, a and b are numbers that can be found from the initial conditions, i.e. for the Fib case from

F_n+2 = F_n+1 + F_n

F_1 = 1

F_2 = 1

I don't give their values on purpose here. It's just a hint.

share|improve this answer
Just to let people know: I decided to port to Python. And up-voted the answers that helped with efficiency and accepted this one because it helped me the most. –  Bair Jul 11 '11 at 23:19

nth fibonacci number is =

where g1 = (1+sqrt(5))/2 = 1.61803399
      g2 = (1-sqrt(5))/2 = -0.61803399

For finding the length of nth fibonacci number, we can just calculate the log(nth fibonacci number).So, length of nth fibonacci number is,

 log((g1^n-g2^n)/sqrt(5)) = log(g1^n-g2^n)-0.5*log(5).
 you can just ignore g2^n, since it is very small negative number.

Hence, length of nth fibonacci is


and we need to find the smallest value of 'n' such that this length = 1000, so we can find the value of n for which the length is just greater than 999.


n*log(g1)-0.5*log(5) > 999
n*log(g1) > 999+0.5*log(5)
n > (999+0.5*log(5))/log(g1)
n > (999.3494850021680094)/(0.20898764058551)
n > 4781.859263075

Hence, the smallest required n is 4782. No use of any coding, easiest way.

Note: everywhere log is used in base 10.

share|improve this answer
fyi, your formula yield 4787 –  Rasman Jul 11 '11 at 17:48
I wrote wrong value. I have editted it now. Hope it helps. –  Gurpreet Singh Jul 12 '11 at 6:36
A description of the above method is given here –  poorvankbhatia Oct 28 '12 at 17:15

This will probably speed it up a fair bit:

int getLength(unsigned long long number) //Returns the length of the number when expressed in base-10
    return (int)log10(number) + 1;

...but, you can't reach 1000 digits using an unsigned long long. I suggest looking into arbitrary-precision arithmetic libraries, or languages which have arbitrary-precision arithmetic built in.

share|improve this answer

You could try computing a Fibonacci number using matrix exponentiation. Then repeated doubling to get to a number that has more than 1000 digits and use binary search in that range to find the first one.

share|improve this answer

using doubles, you can come to a solution knowing the highest exponential is 308:

get the sequence to the exp of 250, then divide your two numbers by 1e250. Restart the algorithm with those two numbers

if you do this 4 times, you'll get the right answer

share|improve this answer

Your Answer


