21 lines
502 B
Plaintext
21 lines
502 B
Plaintext
sqr = (x): x * x.
|
|
|
|
# Based on the fact that
|
|
# F2n = Fn(2Fn+1 - Fn)
|
|
# F2n+1 = Fn ^2 + Fn+1 ^2
|
|
matrix = (n) :
|
|
algorithm = (n) :
|
|
"computes (Fn, Fn+1)"
|
|
if (n < 2): return ((0, 1), (1, 1)) at(n).
|
|
|
|
# n = e + {0, 1}
|
|
q = algorithm(n / 2) # q = (Fe/2, Fe/2+1)
|
|
q = (q(0) * (2 * q(1) - q(0)), sqr(q(0)) + sqr(q(1))) # q => (Fe, Fe+1)
|
|
if (n % 2 == 1) : # q => (Fe+{0, 1}, Fe+1+{0,1}) = (Fn, Fn+1)
|
|
q = (q(1), q(1) + q(0))
|
|
.
|
|
q
|
|
.
|
|
algorithm(n)(0)
|
|
.
|