The thing is that if we have a look at the Fibonacci sequence after applying to each element a modulo operator, we would notice that we always get periodic sequences.

Modulo 2 leads to a infinite repetition of three elements: 0, 1, 1

Modulo 3 to eight elements: 0, 1, 1, 2, 0, 2, 2, 1

Modulo 10 to sixty, et cetera.

There is no known way to get the length period given the modulo - called Pisano period - but we know that each Pisano period starts with "0, 1" and this signature is found just at the beginning of a period.

On this fact, the edX MOOC Algs200x Algorithmic Design and Techniques by the UC San Diego, week 2, proposes three problems. I strongly suggest you to take the course before going on reading this post, getting back here to compare your solution with mine.

Here is the first one,

**Calculate Fibonacci modulo m**.

Given two integers ๐ and ๐, output ๐น๐ mod ๐.

The issue is that n could be up to 10^18. Less preoccupying the upper limit for m, fixed in 10^5.

A first naive solution would consist in calculating the required Fibonacci number, applying the modulo operator to it, return the result. Easy-peasy. However my naive python implementation started to get too slow for mere values about 10^5.

To use the Pisano period we have firstly to get its length. The only reasonable way I could think of, was looking for the modulo sequence checking for first repetition of the starting signature "0, 1".

def pisano(modulo): previous = 1 current = 1 result = 1 while not (previous == 0 and current == 1): # 1 buffer = (previous + current) % modulo # 2 previous = current current = buffer result += 1 return result1. Loop until the starting signature is found

2. Get the next Fibonacci-modulo number

Let's now write a function to get a Fibonacci-modulo number. We could use instead a plain Fibonacci function and then apply the modulo operator to its result. This custom function saves the cost of adding big numbers between them.

def fibonacci(number, modulo): if number < 2: return number results = [1, 1] for _ in range(number - 2): results.append((results[-1] + results[-2]) % modulo) return results[-1]Now, the solution itself is almost trivial.

def solution(number, modulo): return fibonacci(number % pisano(modulo), modulo)Full python code, for both the trivial and Pisano case, and test case on GitHub.

## No comments:

## Post a Comment