`while` döngüsü kullanmadan fonksiyon ile `while True:` döngüsüne benzeyen yaptım

Python
8

Merhaba,

Daha önce karşılaştınız mı bilmiyorum ama önce aşağıdaki bağlantılara bir göz atmanızı tavsiye ederim:

Fibonacci serisinin karakteristik polinomu: \phi^2 - \phi - 1 .
Bu polinomu açtığımızda şöyle bir indüksiyon elde ederiz: \phi^n = F_{n}\phi + F_{n-1} .
F_n , n . sıradaki fibonacci sayısını veren fonksiyondur.
Bu sonuca nasıl ulaştığımız yukarıdaki linklerde yer alıyor. Ama tekrar hatırlayıp polinomu modüler aritmetiğe göre temsil edelim.

\phi^2 = \phi + 1
x^2 \equiv x + 1 \pmod{x^2 - x - 1}
x^2 \pmod{x^2 - x - 1} = x + 1

Kanıt: x’in yerine herhangi bir sayı yazın ve karakteristik polinomu kullanarak modüler aritmetik işlemini sonuçlandırın.

x = 10
10^2 \pmod{10^2 - 10 - 1} = 10 + 1
100 \pmod{89} = 11

\phi^3 = 2\phi + 1
x^3 \equiv 2x + 1 \pmod{x^2 - x - 1}
x^3 \pmod{x^2 - x - 1} = 2x + 1

Kanıt: x’in yerine herhangi bir sayı yazın ve karakteristik polinomu kullanarak modüler aritmetik işlemini sonuçlandırın.

x = 5
5^3 \pmod{5^2 - 5 - 1} = 2 \times 5 + 1
125 \pmod{19} = 11

\phi^4 = 3\phi + 2
x^4 \equiv 3x + 2 \pmod{x^2 - x - 1}
x^4 \pmod{x^2 - x - 1} = 3x + 2

Kanıt: x’in yerine herhangi bir sayı yazın ve karakteristik polinomu kullanarak modüler aritmetik işlemini sonuçlandırın.

x = 4
4^4 \pmod{4^2 - 4 - 1} = 3 \times 4 + 2
256 \pmod{11} = 14
256 \pmod{11} = 3

\phi^5 = 5\phi + 3
x^5 \equiv 5x + 3 \pmod{x^2 - x - 1}
x^5 \pmod{x^2 - x - 1} = 5x + 3

Kanıt: x’in yerine herhangi bir sayı yazın ve karakteristik polinomu kullanarak modüler aritmetik işlemini sonuçlandırın.

x = 7
7^5 \pmod{7^2 - 7 - 1} = 5 \times 7 + 3
16807 \pmod{41} = 38

\phi^n = F_{n}\phi + F_{n-1}
x^n \equiv F_{n}x + F_{n-1} \pmod{x^2 - x - 1}
x^n \pmod{x^2 - x - 1} = F_{n}x + F_{n-1}

F_{n}x \pmod{x} = 0
F_{n-1} \pmod{x} = F_{n-1}
F_{n}x + F_{n-1} \pmod{x} = F_{n-1}
F_{n-1} = x^n \pmod{x^2 - x - 1} \pmod{x}
F_{n} = x^{n+1} \pmod{x^2 - x - 1} \pmod{x}

Büyük sayılarla çalışabilmek için formül şöyle olur:

\begin{align} x =& 2^{n+1} \\ F_{n} =& x^{n+1} \pmod{x^2 - x - 1} \pmod{x} \end{align} 
from timeit import timeit
from typing import Callable
from functools import lru_cache


@lru_cache(maxsize=None)
def fib_fast(n: int) -> int:
    return n if n <= 1 else fib_fast(n - 1) + fib_fast(n - 2)

    
def poly_mod_pow(n: int, f: Callable[[int], int]) -> int:
    return pow(x := 2 << n, n + 1, f(x)) % x
    

f1 = lambda x: x ** 2 - x - 1                   # Fibonacci serisinin karakteristik polinomu
f2 = lambda x: x ** 3 - x ** 2 - x - 1          # Tribonacci serisinin karakteristik polinomu
f3 = lambda x: x ** 4 - x ** 3 - x ** 2 - x - 1 # Tetrabonacci serisinin karakteristik polinomu

t1 = timeit(lambda: fib_fast(500), number=1)
t2 = timeit(lambda: poly_mod_pow(500, f1), number=1)
print(t1, t2)

for i in range(10):
    print(fib_fast(i), *map(poly_mod_pow, [i] * 3, (f1, f2, f3)))

Çıktı:

0.0003714870035764761 1.52790016727522e-05
0 0 0 0
1 1 0 0
1 1 1 0
2 2 1 1
3 3 2 1
5 5 4 2
8 8 7 4
13 13 13 8
21 21 24 15
34 34 44 29
2 Beğeni