Computing `limit` digits of the nth Fibonacci number in log(n)

fib.py

#!/usr/bin/env python3

import sys


limit = 6
mod = 10 ** limit


def mat_mul(m1, m2):
    n1 = (m1[0][0] * m2[0][0]) % mod + (m1[0][1] * m2[1][0]) % mod
    n2 = (m1[0][0] * m2[0][1]) % mod + (m1[0][1] * m2[1][1]) % mod
    n3 = (m1[1][0] * m2[0][0]) % mod + (m1[1][1] * m2[1][0]) % mod
    n4 = (m1[1][0] * m2[0][1]) % mod + (m1[1][1] * m2[1][1]) % mod

    m1[0][0] = n1
    m1[0][1] = n2
    m1[1][0] = n3
    m1[1][1] = n4

    return m1


def mat_exp(m, n):
    acc = [[1, 0], [0, 1]]

    while n != 0:
        if n % 2 != 0:
            acc = mat_mul(acc, m)

        n /= 2
        m = mat_mul(m, m)

    return acc


def fib(n):
    mat = [[1, 1], [1, 0]]

    return 0 if n == 0 else mat_exp(mat, n - 1)[0][0]


print(fib(int(sys.argv[1])))