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 109, 2 M 106).
Yeah... they ask to calculate up to 1 billion... I believe φ109 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 109 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
Exceeded time limit can indicate that the time is not acceptable for large entries. Already tried with extreme entries?
– Jefferson Quesado
You’ve also tested the
ctrl+d
to simulate end of standard input?– Jefferson Quesado
Taking advantage, the secret is in the module, to optimize the calculation
– Jefferson Quesado
Hello Jefferson entries I just tested the ones that the question provided, as so the secret is in the module, would have another way to do without using the operator rest ?
– rafael marques
"How so the secret is in the module?" == > Through module operation (or otherwise, if you prefer to call it that), you get very interesting results that allow you to do a much smaller amount of operations and arrive at the same result. See my answer for more details
– Jefferson Quesado
In fact, Rafael Marques, the fastest way to calculate is by using a mathematical program to calculate to the point that it overflows and then, knowing the sequence as far as the values are valid, save the sequence in a constant array. Thus, one can only access the Fibonacci number in the memory instead of calculating. If using type
int
, like thefib(46)
fits in typeint
whilefib(47)
gives overflow, so no 50 cells will be needed to save valid values.– RHER WOLF