きったんの頭_ん中☆

#! /usr/bin/env python3
"""
Fibonacci Number
https://mind.kittttttan.info/py/fib
"""
from time import time

def fib(n):
    if n > 0:
        a, b = 1, 0
        for i in range(n-1):
            a, b = a+b, a
        return a
    return 0

# |a b|   |d e|   |ad+be bd+ce|
# |   | x |   | = |           |
# |b c|   |e f|   |bd+ce be+cf|
def mmul(a, b):
  	ad = a[0] * b[0]
  	be = a[1] * b[1]
  	bd = a[1] * b[0]
  	ce = a[2] * b[1]
  	cf = a[2] * b[2]
  	return ad + be, bd+ce, be + cf

# |1 1|^n   |fib(n+1) fib(n)  |
# |   |   = |                 |
# |1 0|     |fib(n)   fib(n-1)|
def fibm(n):
    a, b = (1,1,0), (1,1,0)
    n -= 1
    while n > 0:
        if n & 1:
            b = mmul(b,a)
        n >>= 1
        a = mmul(a, a)
    return b[1]

def main():
    n = 7777
    t0 = time()
    f1 = fib(n)
    t1 = time()
    f2 = fibm(n)
    t2 = time()
    print(f1)
    print(f2)
    print('%sms %sms' % (t1 - t0, t2 - t1))

if __name__ == "__main__":
    main()