Name:
Anonymous
2013-01-02 4:58
This isn't that different from the exponentiation by squaring algorithm.
f_{2n+1} = f_{n}^2 + f_{n+1}^2
f_{2n} = f_{2n+1} - f_{2n-1}
= (f_{n}^2 + f_{n+1}^2) - (f_{n-1}^2 + f_{n}^2)
= f_{n+1}^2 - f_{n-1}^2
= f_{n+1}^2 - (f_{n+1} - f_{n})^2
= f_{n+1}^2 - (f_{n+1}^2 - 2f_{n+1}f_{n} + f_{n}^2)
= f_{n+1}^2 - f_{n+1}^2 + 2f_{n+1}f_{n} - f_{n}^2
= 2f_{n+1}f_{n} - f_{n}^2
Two successor functions:
(f_{n},f_{n+1}) -> (2f_{n+1}f_{n} - f_{n}^2, f_{n}^2 + f_{n+1}^2) = (f_{2n},f_{2n+1})
(f_{n},f_{n+1}) -> (f_{n+1},f_{n}+f_{n+1}) = (f_{n+1},f_{n+2})
(n, f1, f2) -> (2n, (2f2 - f1)f1, f1f1 + f2f2)
(n, f1, f2) -> (n+1, f2, f1 + f2)
exponentiation algorithm:
(n, acc) -> (2n, acc*acc)
(n, acc) -> (n+1, acc*x)