Return Styles: Pseud0ch, Terminal, Valhalla, NES, Geocities, Blue Moon. Entire thread

Why don't you code in assembly?

Name: Anonymous 2012-12-30 1:55

 

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)

Newer Posts
Don't change these.
Name: Email:
Entire Thread Thread List