CODEWITHSUNDEEP
c++recursionfibonacci
Juan Sierra
Juan Sierra

Reputation: 75

Finding the nth term of large Fibonacci numbers

I have to write a program where I am given the last three digits of an nth term. For Example, the 20th term is 6765 and the last three digits are '765'. Now I need to find the 1st digit of the Fibonacci sequence which has '321' as the last three digits.

I looked online and found that the nth term is 479 and the program I wrote cannot even go that high. I could not find anyone that has a program that goes higher than the 100th term either.

As of right now is their no way to find a term higher than 100? Any other ideas you guys have other than recursion to find the first digit of the number ending with '321'?

My recursion code is pretty basic:

long long fibNum(long long nth)
{
    if (nth == 1)
        return 1;
    else if (nth == 2)
        return 1;
    else
        return fibNum(nth - 1) + fibNum(nth - 2);
}

By the time I get to the 43th term it begins to slow down.

Upvotes: 1

Views: 4688

Answers (1)

fede1024
fede1024

Reputation: 3098

The 479th number is 5696323922575865414847061494575945648081290145228607189038829076215134884313127297923138542545712321

that will not fit even in a long long variable. I suggest you to implement it taking in consideration just the lowest part of the number. You don't need to store the complete number just to calculate the last 3 digits, and then approximate the whole number.

#include <stdlib.h>
#include <stdio.h>
#include <math.h>

#define PHI 1.61803399

int main(int argc, char *argv[]){
    int pos;
    int x = 0, y = 1, tmp = 0;
    long double num=0;

    int searched = atoi(argv[1]);

    printf("Looking for a fibonacci number ending with: %03d\n", searched);

    for(pos = 2; y != searched; pos++){
        tmp = x+y;
        x = y;
        y = tmp%1000;
    }

    pos--;
    printf("Found at position: %d\n", pos);

    num = (powl(PHI, pos) - powl(1-PHI, pos))/sqrt(5);
    printf("Approximated number %Le\n", num);

    while(num >= 10) num /= 10;

    printf("First digit: %d\n", (int)num);

    return 0;
}

Output:

> ./finbonacci 321
Looking for a fibonacci number ending with: 321
Found at position: 479
Approximated number 5.696326e+99
First digit: 5

This code first calculate the position of the number we are looking for in the sequence, than uses the Binet's formula that can approximate the nth number of the Fibonacci sequence. Since we need just the first digit, we can tolerate the approximation error.

Upvotes: 6

Related Questions