Fibonacci number: Python and C program execution time comparison


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

Solution with C/C++


// @BEGIN_OF_SOURCE_CODE

#include <stdio.h>
#include <string.h>

#define N 1000 + 100

using namespace std;

int firstTerm [N];
int secondTerm [N];
int result [N];

int summation(int length)
{
    int carry = 0;

    for ( int i = 0; i < length; i++ ) {
        carry = firstTerm [i] + secondTerm [i] + carry;
        result [i] = carry % 10;
        carry /= 10;
    }

    while ( carry ) {
        result [length++] = carry % 10;
        carry /= 10;
    }

    return length;
}

void copyArray(int *a, int *b)
{
    for ( int i = 0; i < N; i++ ) {
        a [i] = b [i];
    }
}

int main (int argc, char *argv [])
{
    firstTerm [0] = 1;
    secondTerm [0] = 1;

    int term = 2;
    int length = 1;

    while ( length < 1000 ) {
        length = summation(length);     // result = firstTerm + secondTerm;
        copyArray(firstTerm, secondTerm);
        copyArray(secondTerm, result);
        term++;
    }

    printf ("%d\n", term);

    return 0;
}
// @END_OF_SOURCE_CODE

Execution time: 0.083 seconds

Solution with Python


i, j, term = 0, 1, 2
while True:
    fib = i+j
    if len(str(fib)) >= 1000:
        print term
        break
    i, j, term = j, fib, term+1

Execution time: 0.188 seconds

Lets go to the next level

Problem: What is the first term in the Fibonacci sequence to contain 10000 digits?

Solution with C/C++


// @BEGIN_OF_SOURCE_CODE

#include <stdio.h>
#include <string.h>

#define N 10000 + 100

using namespace std;

int firstTerm [N];
int secondTerm [N];
int result [N];

int summation(int length)
{
    int carry = 0;

    for ( int i = 0; i < length; i++ ) {
        carry = firstTerm [i] + secondTerm [i] + carry;
        result [i] = carry % 10;
        carry /= 10;
    }

    while ( carry ) {
        result [length++] = carry % 10;
        carry /= 10;
    }

    return length;
}

void copyArray(int *a, int *b)
{
    for ( int i = 0; i < N; i++ ) {
        a [i] = b [i];
    }
}

int main (int argc, char *argv [])
{
    firstTerm [0] = 1;
    secondTerm [0] = 1;

    int term = 2;
    int length = 1;

    while ( length < 10000 ) {
        length = summation(length);     // result = firstTerm + secondTerm;
        copyArray(firstTerm, secondTerm);
        copyArray(secondTerm, result);
        term++;
    }

    printf ("%d\n", term);

    return 0;
}
// @END_OF_SOURCE_CODE

Execution time: 6.986 seconds

Solution with Python


i, j, term = 0, 1, 2
while True:
    fib = i+j
    if len(str(fib)) >= 10000:
        print term
        break
    i, j, term = j, fib, term+1

Execution time: 59.078 seconds

System used for comparison:

Processor: Intel(R) Core(TM) i3 CPU 530 @ 2.93GHz
Installed memory (RAM): 4.00 GB
System type: 64-bit Operating System (Windows 8), x64-based processor

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s