How can I make my implementation of Project Euler 25 faster, so I can actually compute the answer?

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;
        length++;
    }
    return length;
}

int main (int argc, const char * argv[])
{
    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 <&开发者_如何学运维lt; termNo;
            break;
        }
    }
}

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.

---

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.

---

nth fibonacci number is =

(g1^n-g2^n)/sqrt(5). 
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

n*log(g1)-0.5*log(5)

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.

So,

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.

---

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.

---

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.

---

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

---

C++ code maybe as follows:

#include "iostream"
#include "string.h"
#include "algorithm"
using namespace std;

string addTwoString(string a, string b)
{
    if (a.length() == 0)
    {
        return b;
    }

    if (b.length() == 0)
    {
        return a;
    }
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());
    string result = "";
    string str_1, str_2;
    if (a.length() > b.length())
    {
        str_1 = b;
        str_2 = a;
    }
    else
    {
        str_1 = a;
        str_2 = b;
    }
    int index = 0;
    int value = 0, over_value = 0;
    for (; index < str_1.length(); ++index)
    {
        int temp_1 = (int)(str_1[index] - '0');
        int temp_2 = (int)(str_2[index] - '0');
        int temp = temp_1 + temp_2 + over_value;
        value = temp % 10; 
        over_value = temp / 10; 
        char c = (char)(value + '0');
        result += c;
    }
    for (; index < str_2.length(); ++index)
    {
        int temp_2 = (int)(str_2[index] - '0');
        int temp = temp_2 + over_value;
        value = temp % 10;
        over_value = temp / 10;
        char c = (char)(value + '0');
        result += c;
    }

    if (over_value > 0)
    {
        char c = (char)(over_value + '0');
        result += c;
    }
    reverse(result.begin(), result.end());
    return result;
}

int main()
{
    string a = "1";
    string b = "1";
    string c = addTwoString(a, b);
    int index = 3;
    while (c.length() < 1000)
    {
        a = b;
        b = c;
        c = addTwoString(a, b);
        ++ index;
    }
    cout << index << endl;
}

---

I just used a recursive function that adds arrays vertically to complete the problem. Basically zero run time, less than 50 lines of code. Enjoy:

#include <stdio.h>

int Calc_Fib (int numA[], int numB[], int temp[], int index) {
    int i = 0;

    //Check 1000th digit for non-zero value.
    if (numB[999] != 0) return index;

    //Add arrays A and B vertically.
    for (i = 0; i < 1000; ++i)   {
        temp[i] += (numA[i] + numB[i]);

        if (temp[i] > 9)   {
            temp[i + 1] = temp[i] / 10;
            temp[i] %= 10;
        }

        numA[i] = numB[i];
        numB[i] = temp[i];
        temp[i] = 0;
    }
    Calc_Fib(numA, numB, temp, ++index);
}

int main()  {
    int numA[1000];   //Holds previous term.
    int numB[1000];   //Holds current term.
    int temp[1000];   //Holds temporary number for vertical addition.
    int i        = 0;
    int indexVal = 2;

    for (i = 0; i < 1000; ++i)  {
        numA[i] = 0;
        numB[i] = 0;
        temp[i] = 0;
    }

    //Initialize first two terms.
    numA[0] = (numB[0] = 1);

    indexVal = Calc_Fib(numA, numB, temp, indexVal);

    printf("Tada: %d\n", indexVal);

    return 0;
}