CODEWITHSUNDEEP
algorithmfibonaccinumber-theorylargenumbermodulo
hack3r-0m
hack3r-0m

Reputation: 750

For a given value of n and m, find fib(n) mod m where n is very huge. (Pisano Period)

Input

Integers 'n' (up to 10^14) and 'm'(up to 10^3)

Output

Fib(n) modulo m

Sample Cases

Input: 239 1000 Output: 161 Input: 2816213588 239 Output: 151

Hint given in Question

As it is not possible to iterate 'n' times (because n is huge), consider using Pisano Period(repetition of remainders when every element Fibonacci series is divided by any integer)

Code which I wrote (maybe wrong, but passes above-mentioned cases)

n, m = map(int, input().split())
a, b = 0, 1

fib_rems = [0, 1] # remainders after diving 'm'
fib = [0, 1] # regular fibonacci series

while True:

  a, b = b, a+b # cotinuing to grow Fibonacci series
  fib.append(b)
  fib_rems.append(b%m)

  # checking if last two items in remainder are 0, 1 which is indication to pisano period
  if fib_rems[-2] == 0 and fib_rems[-1] == 1:

    # remving last two items in fib and fib_rems which are 1 and 0 so we get length equivalet excatly one period
    fib_rems.pop()
    fib_rems.pop()

    fib.pop()
    fib.pop()

    break

period = len(fib_rems)
rem = n % period
print(fib[rem]%m)

The first thing I did is found out the Pisano period(length of repetition of remainders) and have confusion in the rest of the parts.

  1. Why fib(n=2015) mod 3 is equivalent to fib(7) mod 3? (for 𝑚 = 3 the period is 01120221 and has length 8 and 2015=251*8 + 7)
  2. In general, after getting the remainder sequence, how(mathematical proof) it is used for computing Fib(n) mod m?
  3. Can I improve/optimize the above code?

(In short, I don't understand last two lines of above code)

Any hints/guidance/reference/solution is greatly appreciated!

Upvotes: 0

Views: 285

Answers (2)

hack3r-0m
hack3r-0m

Reputation: 750

Every number can be represented as ax + b

For n=2015 and m=3

2015 = (no_of_times_period_repeated)*(length_of_period) + leftover

0 =< leftover <= length_of_period

the value of the leftover is an index at which the remainder of fib(n) lies in the array of values_in_period.

2015 = 251*8 + 7

Also, 2015 % len(period) = 7

values_in_period = [0, 1, 1, 2, 0, 2, 2, 1]

As our leftover is 7(i.e index at which the remainder of fib(n) lies) in this case, the 7th index of values_in_period which is 1 is our answer!

fib(2015) mod 3 can be reduced to fib(7) mod 3 because at every 7th value in the Fibonacci series remainder is the same, so fib(7) mod 3 can be considered for the sake of simplicity but it is not needed and completely out of context.

Upvotes: 0

Samuel Vidal
Samuel Vidal

Reputation: 943

You can make it much faster by using binary exponentiation. It ultimately boils down to the following two quadratic recurrence relations:

F(2 n -1) = F(n)^2 + F(n -1)^2

F(2 n) = (2 F(n -1) + F(n)) F(n)

You can take the remainder modulo m at each step.

Upvotes: 1

Related Questions