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

Question

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 << 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.

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 05:14
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 05:16
@Micheal: Are you hinting at the fact there is another way to compute the stuff without actually having the actual number? — Dair, Jul 11 '11 at 05:22
c is not an ideal language when doing these computation. you need something more suited for number crunching (possibly fortran, or matlab) — Rasman, Jul 11 '11 at 05:25
i should mention, that you can get an approximation for your answer if you use the quadruple type and check for when your number is greater then 1e1000 — Rasman, Jul 11 '11 at 05:28
http://en.wikipedia.org/wiki/Quadruple_precision_floating-point_format — Rasman, Jul 11 '11 at 05:32
For C bigint libraries, see ["'BigInt' in C?"](http://stackoverflow.com/questions/565150/bigint-in-c) and ["What is the simplest way of implementing bigint in C?"](http://stackoverflow.com/questions/3340511/what-is-the-simplest-way-of-implementing-bigint-in-c) — outis, Jul 11 '11 at 05: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 05:58
@anon: there is a way to more or less directly determine which fibonacci number will reach x number of digits (once x is large enough). However, my hint was more along the lines of implementing your own bignum routines - all you really need to implement is initialization, addition, and output (or at least getting the number of digits the bignum value represents). Whether you want to use a bignum library (or a language that supports bignum natively) or implement your own depends entirely on what you want to get out of working the project problem. — Michael Burr, Jul 11 '11 at 06:25
already answered but for project euler newbies like me mine result took[17.765 ms] on 3.2GHz machine using own 3328 bit integer arithmetics (brute force) no funky stuff like multi threading or CUDA just raw 32bit C++ App — Spektre, Jul 09 '14 at 09:30

score 4 · Accepted Answer · answered Jul 11 '11 at 05:15

4

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.

answered Jul 11 '11 at 05:15

Petar Ivanov

91,536
11
82
95

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. – Dair Jul 11 '11 at 23:19

Gurpreet Singh · Answer 2 · 2011-07-12T06:30:07.900

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.

A description of the above method is given [here](http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibFormula.html) — poorvank, Oct 28 '12 at 17:15

aroth · Answer 3 · 2011-07-11T05:24:41.407

1

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.

edited Jul 11 '11 at 05:24

answered Jul 11 '11 at 05:19

aroth

54,026
20
135
176

score 0 · Answer 4 · answered Apr 07 '16 at 10:09

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;
}

Please just explain in brief, the approach you have taken to solve questioner's problem. — Sendhilkumar Alalasundaram, Apr 07 '16 at 10:34
Instead of reversing a copy of both input strings, it would be *much* more efficient to just iterate backwards over the inputs. Or even just store your strings in reverse order all the time. And make them `uint8_t`, not char, so you don't need to convert to/from ASCII at every step. Basically, you should be storing little-endian BCD in vectors of `uint8_t`, with one decimal digit per byte. That removes all the reversing, and the add/subtracting of `'0'` — Peter Cordes, Apr 07 '16 at 20:00
And you should add an explanation that this is just BigNum implementation using ASCII strings. — Peter Cordes, Apr 07 '16 at 20:01

score 0 · Answer 5 · answered Apr 10 '16 at 05:29

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;
}

You don't need `int` arrays when you're only storing at most the sum of two decimal digits in each element. `uint8_t` would work, like @June's answer. Also, why do you need a whole array for `temp`? Surely it's not that hard to implement carry with just a single extra local variable? — Peter Cordes, Apr 11 '16 at 07:16
You're right about the temp array, I definitely didn't think of that at the time. I'm not familiar with 'uint8_t' however, as I'm pretty new to code. I'm also not exactly sure how June's string addition function works. — Ethan Lewis, Apr 12 '16 at 15:18

score 0 · Answer 6 · answered Jul 11 '11 at 05:16

0

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.

answered Jul 11 '11 at 05:16

i0exception

372
4
12

score 0 · Answer 7 · answered Jul 11 '11 at 17:58

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

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

7 Answers7