#!/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=