Wie mache ich meine Fibonacci mit Modular Arithmetic effizienter, um den Pisano-Zyklus zu finden?

Question

Durch pädagogische Zwecke, ich einen Code in Python3 um den Aufbau dieses Ziel zu erreichen:

ich, dass ich für dieses Problem eine sehr gute Arbeit geleistet haben denke, da ich in einem Anfänger/Mittelstufe am . Dieses Problem ist fortgeschritten und nicht obligatorisch.

Ich habe Stresstests mit einer Slow-Aber-Safer-Funktion als "Kontrollgruppe" durchgeführt. Danach konnte ich eine schnellere Funktion erstellen.

Allerdings ist meine Implementierung problematisch für einige Pisano-Zyklen. Wie Sie hier sehen in vielleicht: http://webspace.ship.edu/msrenault/fibonacci/fiblist.htm einige Mods riesige Pisano periodischen Zyklen schaffen ...

Meine Funktion für Mods wie < 249 ... aber wirklich schnell funktioniert, ich weiß nicht, wie zu tun mit Mods wie 1570, die ein Muster/Zyklus mit einer Gesamtlänge von 4740-Nummern erzeugt ... das ist das ein ciclical Muster nicht 001 unsere 12.113 aber 4740 Zahlen beteiligt ...

ich versuchte Suche nach einem Weg, dies zu lösen . Ich konnte verschiedene Ansätze finden, die das Problem lösen würden. Nichtsdestotrotz möchte ich versuchen, meine Implementierung zu reparieren, indem ich sie schneller auf dem Zyklus-Erkennungsteil mache - wenn das überhaupt möglich ist ....

Das ist mein 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)) 

Wenn Sie den Eingang so etwas wie:

2816213588 30524 

Es wird die richtige Ausgabe:

10249 

Aber es dauert länger als 5 Sekunden ...

Ein weiteres Problem, passiert, wenn ich eine riesige Zahl als Eingabe für den Mod habe, zB:

fehlgeschlagen Fall # 12/22: (Falsche Antwort)

Eingang: 99999999999999999 100000

Ihre Ausgabe: 69026

korrekte Ausgabe: 90626

(Zeit verwendet: 0.04/5.00, Speicher verwendet. 24100864/536870912)

Mein Code gibt einen falschen Ausgang aufgrund dieses Teils:

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

ich den Bereich des Pisano Zyklus in einem Bereich von 60000 Zahlen zu begrenzen, und einige Pisano Zyklen, anscheinend kann, gehen Sie wirklich, dass über ...

Answer 1

Sie sollten Fibonacci berechnen Zahl mit Modulo-Arithmetik anstelle von Rechen die Zykluslänge, für die es einen logarithmischen Algorithmus gibt.

Die Gesamtzahl der dafür erforderlichen Iterationen ist sicherlich niedriger als die, die für die explizite Berechnung der Pisanozykluslänge erforderlich ist.

Die Beziehung Sie ausnutzen müssen, ist

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

Wenn Sie die Multiplikationen und Additionen in Moduloarithmetik tun können Sie Integer-Datentypen (10^5 < 2^17) für ein genaues Ergebnis verwenden.