How to make my Fibonacci with Modular Arithmetic more efficient to find the pisano cycle?

Question

Due to educational purposes, I am building a code in Python3 in order to accomplish this goal:

I think I did a very good job for this problem since I am in a beginner/intermediate level. This problem is an advanced and not obligatory one.

I did stress testing using a slow-but-saffer function as "control group". After that, I was able to create a faster function.

However, my implementation is problematic for some pisano cycles. As you might see in here: http://webspace.ship.edu/msrenault/fibonacci/fiblist.htm some mods can create huge Pisano periodic-cycles...

My function works really fast for mods like <249... However, I don't know how to deal with mods like 1570, which generates a pattern/cycle with a total length of 4740 numbers... That's the a ciclical pattern involving not 001 our 12113 but 4740 numbers...

I tried searching for a way to solve this. I was able to find different approaches that would solve the problem. Nonetheless, I would like to try fixing my implementation, making it faster on the cycle-recognition part - if this is possible at all....

That's my code.

coursera_input = (input())
coursera_input = (coursera_input.split())
n_in = int(coursera_input[0])
mod_in = int(coursera_input[1])

import random

def my_fibo_iter(x):
    if x<=1:
        return x
    else:
        bef_previous_elem = 0
        previous_elem = 1
        current = 0
        count = 1
        while count<x:
            count = count + 1
            current = bef_previous_elem + previous_elem
            bef_previous_elem = previous_elem
            previous_elem = current
        return (current)

def fibo_iter_mod_slow(n,mod):
    if n==0:
        return n%mod
    elif n==1:
        return n%mod
    else:
        previous = 1%mod
        bef_previous = 0%mod 
        count = 1
        while count<(n):
                current = bef_previous%mod + previous%mod 
                bef_previous = previous%mod 
                previous = current%mod 
                count = count + 1
        return current%mod 

#preciso construir um algoritmo para identificar a pisano period/cycle

def pisano_cycle(big_list):
    promising_list = []
    for i in big_list:
        promising_list.append(i)
        p_l_len = len(promising_list)
        p_l_final_index = 2*p_l_len
        if promising_list == big_list[p_l_len:p_l_final_index]:
            break
    return promising_list

def generate_big_pisano_list(mod):
    big_list = []
    if mod<249:
        limit = 700
    if 249<=mod<1000:
        limit = 3001
    else:
        limit = 6000
    for i in range(0,limit):
        big_list.append(fibo_iter_mod_slow(i,mod))
    return big_list

#agora eu sei gerar uma lista pisano
#sei identificar uma lista de pisano
#preciso de uma outra função
#ela deve, sabendo o padrão CÍCLICO, identificar o nth elemento desse padrão


def fibo_iter_mod_fast(n,mod):
    big_pisano_list = generate_big_pisano_list(mod)
    pattern = pisano_cycle(big_pisano_list)
    length_patt = len(pattern)
    index_analogous = (n%length_patt)
    output_in_mod = pattern[index_analogous]
    return output_in_mod

print (fibo_iter_mod_fast(n_in,mod_in))

If you input something like:

2816213588 30524

It gets the correct output:

10249

But it takes more than 5 seconds...

Another problem that happens is when I have a huge number as an input for the mod, like:

Failed case #12/22: (Wrong answer)

Input: 99999999999999999 100000

Your output: 69026

Correct output: 90626

(Time used: 0.04/5.00, memory used: 24100864/536870912.)

My code returns an incorrect output due to this part:

   def generate_big_pisano_list(mod):
        big_list = []
        if mod<249:
            limit = 700
        if 249<=mod<1000:
            limit = 3001
        else:
            limit = 6000

I am limiting the range of the pisano cycle in a range of 60000 numbers, and some pisano cycles, apparently, can go really beyond that...

Answer 1

You should compute Fibonacci number with modulo arithmetic instead of computing the cycle length, for which there is a logarithmic algorithm.

The total number of iterations required for that is certainly lower than the one required to compute explicitly the pisano cycle length.

The relation you have to exploit is

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

If you do the multiplications and additions in modulo arithmetic you can use integer data types (10^5 < 2^17) for an exact result.