fib4.py

#!/usr/bin/python3
import sys
from dataclasses import dataclass
from multiprocessing.pool import ThreadPool as Pool

def add(x):
    return x[0] + x[1]

def mul(x):
    return x[0] * x[1]

pool = Pool(8)

@dataclass
class M2:
    m00: object
    m01: object
    m10: object
    m11: object

    def __mul__(l, r):
        even_products = pool.imap(mul, (
            (l.m00, r.m00),
            (l.m00, r.m01),
            (l.m10, r.m00),
            (l.m10, r.m01)))
        odd_products = pool.imap(mul, (
            (l.m01, r.m10),
            (l.m01, r.m11),
            (l.m11, r.m10),
            (l.m11, r.m11)))

        return M2(*pool.map(add, zip(even_products, odd_products)))

    def __pow__(self, exp):
        return fast_power(self, exp, self.mul_idn)

M2.mul_idn = M2(1, 0, 0, 1)

try:
    import gmpy2
except:
    M2z = None
    M2_default = M2
else:
    class M2z(M2):
        pass
    M2z.mul_idn = M2z(gmpy2.mpz(1), gmpy2.mpz(0), gmpy2.mpz(0), gmpy2.mpz(1))
    M2_default = M2z

def fast_power(base, exp, mul_idn):
    result = mul_idn
    for i in range(exp.bit_length()):
        print(end=f"{i}/{exp.bit_length()}\r", file=sys.stderr)
        sys.stderr.flush()
        if exp & (1<<i):
            result *= base
        base *= base
    print(end=" " * len(f"{i}/{exp.bit_length()}") + "\r", file=sys.stderr)
    sys.stderr.flush()
    return result

def fib(n, mat=M2):
    zero = mat.mul_idn.m01
    one = mat.mul_idn.m00
    return(mat(zero,one,one,one) ** (n-1)).m11

if __name__ == '__main__':

    def conv_bit_length(n):
        return n.bit_length()
    def conv_dec_length(n):
        return len(str(n))

    import argparse
    parser = argparse.ArgumentParser(description='Calculate fibonacci numbers')
    parser.add_argument('integers', metavar='N', type=int, nargs='+',
        help='Values for which to calculate fib(N)')
    parser.add_argument('--dec', dest='converter', action='store_const',
        const=str, default=str,
        help='Print the number in base-10')
    parser.add_argument('--bit-length', dest='converter', action='store_const',
        const=conv_bit_length,
        help='Print the bit length of the number, instead of the number')
    parser.add_argument('--dec-length', dest='converter', action='store_const',
        const=conv_dec_length,
        help='Print the bit length of the number, instead of the number')
    parser.add_argument('--bin', dest='converter', action='store_const',
        const=bin,
        help='Print the number in base-2')
    parser.add_argument('--hex', dest='converter', action='store_const',
        const=hex,
        help='Print the number in base-16')
    parser.add_argument('--oct', dest='converter', action='store_const',
        const=oct,
        help='Print the number in base-8')
    parser.add_argument('--long', dest='mat', action='store_const',
        const=M2, default=M2_default,
        help='Calculate using built-in long integers')
    if M2z is not None:
        parser.add_argument('--mpz', dest='mat', action='store_const',
            const=M2z, default=M2_default,
            help='Calculate using mpz long integers via gmpy2')

    args = parser.parse_args()

    for n in args.integers:
        print(f'{n}: {args.converter(fib(n, args.mat))}')