2

I recently stumbled on this Project Euler Problem #25:

The 12th term, F12, is the first term to contain three digits.

What is the first term in the Fibonacci sequence to contain 1000 digits?

I just know C++98 and no other programming language. I have tried to solve it, making changes to get support of c++11.

Working:

#include <iostream>
#include<cstdio>
long len(long);              //finding length
int main()
{
    /* Ques: What is the first term in fibonacci series to contain 1000 digits? */
    
    int ctr=2;
    unsigned long first, second, third, n;
    first=1;
    second=1;
    std::cout<<"\t **Project EULER Question 25**\n\n";
    for(int i=2;;++i)
    {
        third=first+second;
        //  cout<<" "<<third;
        int x=len(third);
        //  cout<<" Length: "<<x;
        //  cout<<"\n";

        first=second;
        second=third;
        ctr++;
            if(x>1000)        // for small values, program works properly
        {
            std::cout<< " THE ANSWER: "<< ctr;
            system("pause");
            break;
        }

    }
}

long len(long num)
{


    int ctr=1;

    while(num!=0)
    {
        num=num/10;
                if(num!=0)
            {
                ctr++;
            }
    }

    return(ctr);
}

I know this is brute force, but can i make it more efficient so that i get the answer ?

Any help will be greatly appreciated.

EDIT:

By using Binet's Formula, as suggested by PaulMcKenzie and implementing it as:

#define phi (1+sqrt(5))/2
int main(void)
{
   float n= ((999 + (1/2)*log10(5))/(log10(phi)));     //Line 1
   cout<<"Number is  : "<<n;
   return 0;
}

Output: 4780.187012

Changing Line 1, above, to :

float n= ((999 + log10(sqrt(5)))/(log10(phi)));

OUTPUT: 4781.859375

What could be possibly the error here?

Community
  • 1
  • 1
CS101
  • 145
  • 5
  • 2
    Note that a `long` can't hold a 1000-digit number, so this code probably won't work correctly. As a hint, look up Binet's formula and take log base 10 of it to get the number of digits in the nth Fibonacci number. – templatetypedef Feb 13 '14 at 05:19
  • Of course it "works" for small numbers. What is the INT_MAX for your integer type? I bet it doesn't come anywhere close to a 1,000 digit number. – PaulMcKenzie Feb 13 '14 at 05:20
  • @templatetypedef : how? please help me with it. I don't know how to proceed. – CS101 Feb 13 '14 at 05:22
  • @templatetypedef - There is a way to approximate the nth Fibonacci number by using a closed formula, and not through iteration. Look up "golden ratio", as well as Binet's formula. Also, you know the number of digits any positive number has by doing a log base 10. – PaulMcKenzie Feb 13 '14 at 05:26
  • @PaulMcKenzie (I think you meant to direct that to MathGeek?) – templatetypedef Feb 13 '14 at 05:33
  • @PaulMcKenzie : I got the answer using: $$\displaystyle F(n) = \left[\frac{\phi^n}{\sqrt{5}}\right]$$ and, $$\frac{\phi^n}{\sqrt{5}}>10^{999}$$ and then, [this](https://www.google.com/search?q=%28999%2Blog%28sqrt%285%29%29%29%2Flog%28phi%29+%2B1&ie=utf-8&oe=utf-8&aq=t&rls=org.mozilla:en-US:official&client=firefox-a&channel=fflb) – CS101 Feb 13 '14 at 05:49
  • @PaulMcKenzie Sorry, those math symbols display oddly. But how to implement this in my program? – CS101 Feb 13 '14 at 05:54
  • @templatetypedef - yep, meant MathGeek. – PaulMcKenzie Feb 13 '14 at 06:02
  • @MathGeek - So you're not able to write a C++ program that loops and calls basic C++ math functions such as sqrt() and log10()? – PaulMcKenzie Feb 13 '14 at 06:07
  • @MathGeek -- Remember that you're using C++. I suggest you put decimal points in your numerical constants so as to not (by accident) perform integer arithmetic. – PaulMcKenzie Feb 13 '14 at 10:02

1 Answers1

2

unsigned long simply can't hold 1000-digit number. So you will get the overflow in your code when first and second will reach the unsigned long limit. If you want a brute force solution - consider use of something like biginteger library or write one by yourself.

Community
  • 1
  • 1
tkhomas
  • 103
  • 1
  • 8