What is the fastest way to calculate the sequence of Fibonacci

Question

I’m asking a question that is Fibonacci de Novo! the tests give the expected result only that gives Time limit exceeded, wanted if you have a faster way to calculate

My code

#include <stdio.h>

int fat(int num);

int main()
{
  int numero, resto;
  while(scanf("%d %d", &numero, &resto) != EOF)
  {
    printf("%d\n", fat(fat(numero))%resto);
  }
}

int fat(int num)
{
  int numero1 = 0, numero2 = 1, soma;

  for(int i = 0; i < num; i++)
  {
    soma = numero1 + numero2;
    numero2 = numero1;
    numero1 = soma;
  }
  return numero1;
}

Answer 1

First point, we need to know the behavior of the function to calculate Fibonacci of a number. We have several alternatives. First, start with the recursive definition of the Fibonacci function:

def fib(n):
  if n == 1 or n == 2:
    return 1
  else:
    return fib(n-1) + fib(n-2)

If you analyze in depth, you will realize that the only option of a value being added to the return number is when we have in recursion the call to fib(1) or fib(2). But how many function calls are made in all? To answer this question, I created a function that I named meta_fib. In addition to counting the same Fibonacci return function calls, I also add one to each recursive call. Then, meta_fib is described as:

def meta_fib(n):
  if n == 1 or n == 2:
    return 1
  else:
    return 1 + meta_fib(n - 1) + meta_fib(n - 2)
        

meta_fib(i), then, will return how many function calls are made. I decided to compare how much meta_fib grew in comparison to fib. So apparently, meta_fib(a) = 2*fib(a) - 1. But Fibonacci’s function has exponential growth. @Ricardo Ribeiro put the formula in your answer (we’ll return to her later):

Then, the number of calls to the function fib is:

Okay, we have a strategy. Let’s look at the statement to see if the strategy can be minimally feasible. Perhaps with a few tens of millions of operations I can successfully do the calculation... note that (1 - φ) is a value between 0 and 1, so raising it to a number greater than 1 will bring it closer to zero.

[...] Your task is simple, calculate the value of the rest of Fib( Fib( N ) by M.

Entree

The input consists of several test cases and ends with EOF. Each test case consists of a line with two integers N and M (1 N 10⁹, 2 M 10⁶).

Yeah... they ask to calculate up to 1 billion... I believe φ¹⁰⁹ is slightly larger than my imaginary limit of a few million operations...

And if I do with memoisation? Well, with that I guarantee I won’t recursively descend twice by the same fib(n). With memoization, calculate fib(n + 2) is more or less like this (put with * the memoised values):

fib(n + 2) =
fib(n + 1) + fib(n)* =
fib(n)* + fib(n)* + fib(n - 1)*

And, in this calculation, the values and fib(n + 1) and fib(n + 2) are memoised when they are calculated. And how much memory would I need to memoise everything? It is an integer for each index... that is, it would need 10⁹ integer to try to memoize all entries to fib(n). But the point is we’re not calculating fib(n), but fib(fib(n)), which would require a little more memory... of all sorts, 1 billion integers would already require (for a 32-bit integer) 4GB of RAM only for the memoization vector. Well, I don’t know how much the URI makes available, but it sure is less than that...

So, this memoized alternative also is out of the question.

And calculate in a linear way? How did you, @rafael marques, suggest? Well, it’s done in a linear way. At worst, then, the input would be 1 billion, and to calculate Fibonacci alone, billions of operations would be required. So this alternative is also is not feasible...

A faster approach than o(n). Perhaps an approach o(log n) could be accepted, but I think an approach o(1) better.

Let’s take the formula again:

Pay attention to the term on the right side: (1 - φ)^n/sqrt(5). If you are going to calculate, you will see that the absolute value of that number is always less than 0.5. Then, we can get the value of fib(n) by the following formula:

Source

So I can calculate fib(n). But... is it? To do so, we need to ensure that the calculated number fits within the memory space reserved for this. A variable of type double There’s only 53 bits of mantissa. This is not enough even to store the entire input, which can reach 1 billion, so it will need 62 digits to be stored. So, the guy double is not appropriate. AND long double? Well, he’s guaranteed no less than a double (source), but at no time have I seen a guaranteed definition of it. Maybe it’s a Extended x86 floating point, that uses 64 bits of mantissa (see more). I mean, nothing done yet.

If only we could use that mod m somewhere...

But there is the Pisan period!!

The pisano period is the size of the interval at which the Fibonacci sequence numbers begin to repeat, mod m. The interesting thing about this period is that fib(n) % m = fib(n % π(m)) % m, being π(m) the Pisano period for the module m. And the interesting thing is π(m) <= 6*m. Hence, calculate fib(n) % m is no longer dependent on n, but it is o(π(m)), and how we have to π(m) = o(m), then the calculation of a Fibonacci sequence module m is o(m). And that is within our acceptable.

So with that, revising here our object of calculation:

Which is therefore equal to:

Which is therefore equal to:

Okay, with that, the iterative calculation of fib is good enough. Let’s go back to how to do this calculation soon, because first we need to define another loose end in the solution... the value of π(m).

Several other people have already come across the need to calculate the Fibonacci function for large numbers. How that boy from the article. And, yes, he was one of the references I found when I was looking into the calculus of π(m). In short, it is something very close to calculating the value of fib(n), but the idea is that when you get the value 0 and then get the value 1, you have entered into a loop. The number n ==> fib(n)%m == 0, fib(n + 1)%m == 1 is the size of the Pisano period; i.e., n <==> π(m).

So to calculate the π(m) it is necessary to calculate the Fibonacci function. For this, I will use the adaptation of the iterative calculus you made:

def pisano(m):
    if m == 1:
        return 1
        
    """
    toda sequência tem tamanho par, então posso começar de n = 2 e terminar quando
    obter:
    
    f_n_minus_1 == 0
    f_n == 1
    """
    
    f_n_minus_1 = 1
    f_n = 1
    n = 2
    
    while not(f_n_minus_1 == 0 and f_n == 1):
        f_n_plus_1 = (f_n + f_n_minus_1) % m
        f_n_minus_1 = f_n
        f_n = f_n_plus_1
        n += 1
    return n - 1

See it working on ideone. Note that, here, my validation is for fib(n - 1) % m == 0, fib(n) % m == 1, so here n is π(m) + 1 at the end of the loop; hence the return is n - 1, but of course this could be changed (but hence the names of the variables fib_n, fib_n_plus_1 and fib_n_minus_1 would not make sense, would have to rename).

So, how to proceed with the account? We could use memoization to avoid calculating twice the same value of π(x). For this, the memory vector should have the size of about 6 million integers (upper limit for π(m), m <= 1000000, to carry out the calculation of π(π(m))). I’ll leave this part with you. And the calculation of the sequence of Fibonacci module m, then? How would it look?

If you have noticed correctly, you must always go through all the values of the Fibonacci sequence smaller than the period to find the period. Perhaps it was the case to store these intermediate values in a vector and access them in o(1). I’ll let you figure out how to fix it.

To resolve the issue, we need to write fib(fib(n))%m, which I baptize of fib_fib_mod. She’d be like this:

def fib_fib_mod(n, m):
  return fib_mod(fib_mod(n, pisano(m)), m)

Already fib_mod:

def fib_mod(n, m):
  n = n % pisano(m)
  if n == 0:
    return 0
  f_x_minus_1 = 0
  f_x = 1
  x = 1
  while x < n:
    f_x_plus_1 = (f_x + f_x_minus_1) % m
    f_x_minus_1 = f_x
    f_x = f_x_plus_1
    x += 1
  return f_x

I left the code in Python so you need to adapt it to C. And, in addition, make the necessary changes to try to optimize the calculation, such as memoizing the various calculations along the way to avoid repeating previous calculations. See working for some entries in ideone.

Completion

• this problem is much more mathematical than programming, it would not be possible to think of resolution for it without knowing the sequences of Pisano
• always read the limits of the question; if the question said that the maximum for a variable is 1 billion, then the creators of the proof thought of an input case for 1 billion
• even if you have a solution o(n), it will be unnecessarily slow if the value of n be very large, like 1 billion
• test for cases beyond the cases in which the test creator showed
  those there are just mere examples for you to base, have a north, mainly in the format data input and output; much more than anything else, the people who create these proofs like to show in such a way as to have no doubt what the input format and expected output format
• sometimes the best optimization in a program is to get as far away from programming as possible and use magic formulas such as the calculation of the Pisano period

Answer 2

I do not know if it is the fastest, but I believe that this, if adapted to the problem, will be accepted!!

#include <stdio.h>

int main()
{
    double n, x, y, ans;
    scanf("%lf", &n);
    x = (1 + sqrt(5))/2.0;
    y = (1 - sqrt(5))/2.0;
    ans = (pow(x,n) - pow(y,n))/sqrt(5);
    printf("%.1lf\n", ans);
    return 0;
}

Answer 3

Try this code: recursive

#include <stdio.h>
int fib(int n)                            
{                                         
  if (n == 1) return 1;                   
    else 
      if (n == 2) return 1;                 
      else return fib(n - 1) + fib(n - 2);  
}                                         
int main(void)
{ 
  int n;
  scanf("%d", &n);
  printf("%d\n", fib(n));
  return 0;
}