Finding Modulo of Large Fibonacci Number

Fibonacci Numbers increase very rapidly as the sequence progresses, but is there a way to compute the modulo of the Fibonacci number that you are interested in. In this article I'll be explaining how I had to find this in order to complete a problem in a programming competition.

In a coding competition there was a problem, which was essentially to find,

$$ {Fib}(n) \ {mod} \ 10 \ {for} \ n \le 10^9 $$

As you may know fibonacci numbers increase very rapidly, given below is the $100^{th}$ fibonacci number.

$$ {Fib}({100}) = {354224848179261915075} $$

So you can see that for an input about $10^9$ it would be impossible to represent int a 64-bit integer value and it would also take a very long time.

To bypass this bottleneck I needed to find a way to compute the ${Fib}(n) \ mod \ m \ \forall(m\gt1)$ without having to compute very large fibonacci numbers. To do that we need to first get to know The Pisano Period

The Pisano Period

Pisano Period, $\pi(m)$ is defined as the period which the fibonacci sequence modulo $m$ repeats.

For example lets take $m = 2$

$n$	$Fib(n)$	$Fib(n) \ mod \ 2$
0	1	1
1	1	1
2	2	0
3	3	1
4	5	1
5	8	0
6	13	1
7	21	1
8	34	0

As you can see there is a pattern of period 3.

So essentially for a given number $m$ there is a number $\pi(m)$ which is the period at which the fibonacci sequence repeats itself.

If you need to know more about the Pisano Period, feel free to google it!

So lets code the get_pisano_period function

def get_pisano_period(m):
    a = 0
    b = 1
    for i in range(0, m*m):
        c = (a + b) % m
        a = b
        b = c
        if a == 0 and b == 1:
            return i + 1

Applying to the Problem

So how does the Pisano Period helps us in finding the modulo of fibonnaci number. Let me demonstrate,

Let $Fib(n) \ mod \ m$ be the value we want to find

Let $p = \pi(m)$, where $\pi(x)$ is the Pisano Period of $x$

Then we know that the $Fib(x) \ mod \ m$ function repeats after every $p$ iterations.

We can express that as $n = a*p + b \ (a,b \in \mathbb{N})$. So we only need to compute the $Fib(b) \ mod \ m$.

The python code for that is as follows,

def fib(n):
    if n == 0:
        return 1
    n1 = 0
    n2 = 1
    for i in range(0, n):
        t = n1 + n2
        n1 = n2
        n2 = t
    return n2

def fibmod(n, m):
    p = get_pisano_period(m)
    b = n % p
    return fib(n) % m

So I hope you guys understood this article, if you have any doubts or you can think of a quicker way to find the modulo of fibonacci numbers please feel free to comment on it!

Finding Modulo of Large Fibonacci Number

Comments

More from this blog

Exploring the Infinite Rolling Median

Authenticating Jitsi Meetings using Keycloak

PyTorch Lightning Basics

Introduction to MapReduce - Filter > Map > Reduce

The Pisano Period

Applying to the Problem

$n$	$Fib(n)$	\(Fib(n) \ mod \ 2\)
0	1	1
1	1	1
2	2	0
3	3	1
4	5	1
5	8	0
6	13	1
7	21	1
8	34	0

Command Palette

Comments

More from this blog

The Pisano Period

Applying to the Problem