#!/usr/bin/env python3
def sicpfib(n):
"""Compute nth fibonacci number.
O(log(n)) steps, O(n) in memory (to hold the result)
Function Fib(count)
a ← 1
b ← 0
p ← 0
q ← 1
While count > 0 Do
If Even(count) Then
p ← p² + q²
q ← 2pq + q²
count ← count ÷ 2
Else
a ← bq + aq + ap
b ← bp + aq
count ← count - 1
End If
End While
Return b
End Function
See http://stackoverflow.com/questions/1525521/nth-fibonacci-number-in-sublinear-time/1526036#1526036
"""
a, b, p, q = 1, 0, 0, 1
while n > 0:
if n % 2 == 0: # even
oldp = p
p = p*p + q*q
q = 2*oldp*q + q*q
n //= 2
else:
olda = a
a = b*q + a*q + a*p
b = b*p + olda*q
n -= 1
return b
print(*[sicpfib(i) for i in range(10)])
IyEvdXNyL2Jpbi9lbnYgcHl0aG9uMwpkZWYgc2ljcGZpYihuKToKICAgICIiIkNvbXB1dGUgbnRoIGZpYm9uYWNjaSBudW1iZXIuIAogICAgCiAgICBPKGxvZyhuKSkgc3RlcHMsIE8obikgaW4gbWVtb3J5ICh0byBob2xkIHRoZSByZXN1bHQpCiAgICAKICAgIEZ1bmN0aW9uIEZpYihjb3VudCkKICAgICAgICBhIOKGkCAxCiAgICAgICAgYiDihpAgMAogICAgICAgIHAg4oaQIDAKICAgICAgICBxIOKGkCAxCiAgICAgICAgV2hpbGUgY291bnQgPiAwIERvCiAgICAgICAgICAgIElmIEV2ZW4oY291bnQpIFRoZW4KICAgICAgICAgICAgICAgICBwIOKGkCBwwrIgKyBxwrIKICAgICAgICAgICAgICAgICBxIOKGkCAycHEgKyBxwrIKICAgICAgICAgICAgICAgICBjb3VudCDihpAgY291bnQgw7cgMgogICAgICAgICAgICBFbHNlCiAgICAgICAgICAgICAgICAgYSDihpAgYnEgKyBhcSArIGFwCiAgICAgICAgICAgICAgICAgYiDihpAgYnAgKyBhcQogICAgICAgICAgICAgICAgIGNvdW50IOKGkCBjb3VudCAtIDEKICAgICAgICAgICAgRW5kIElmCiAgICAgICAgRW5kIFdoaWxlCiAgICAgICAgUmV0dXJuIGIKICAgIEVuZCBGdW5jdGlvbgogICAgU2VlIGh0dHA6Ly9zdGFja292ZXJmbG93LmNvbS9xdWVzdGlvbnMvMTUyNTUyMS9udGgtZmlib25hY2NpLW51bWJlci1pbi1zdWJsaW5lYXItdGltZS8xNTI2MDM2IzE1MjYwMzYKICAgICIiIgogICAgYSwgYiwgcCwgcSA9IDEsIDAsIDAsIDEKICAgIHdoaWxlIG4gPiAwOgogICAgICAgIGlmIG4gJSAyID09IDA6ICMgZXZlbgogICAgICAgICAgICBvbGRwID0gcAogICAgICAgICAgICBwID0gcCpwICsgcSpxCiAgICAgICAgICAgIHEgPSAyKm9sZHAqcSArIHEqcQogICAgICAgICAgICBuIC8vPSAyCiAgICAgICAgZWxzZToKICAgICAgICAgICAgb2xkYSA9IGEKICAgICAgICAgICAgYSA9IGIqcSArIGEqcSArIGEqcAogICAgICAgICAgICBiID0gYipwICsgb2xkYSpxCiAgICAgICAgICAgIG4gLT0gMQogICAgcmV0dXJuIGIKICAgIApwcmludCgqW3NpY3BmaWIoaSkgZm9yIGkgaW4gcmFuZ2UoMTApXSk=