fastest fibonacci precise calculation (to millionth) including negative

fibonacci.py

def fib(n):
    if n == 0: return 0
    if n == 1: return 1
    if n >=2 and n % 2 == 0:
        k = int(n / 2)
        fbk = fib(k)
        return (2 * fib(k - 1) + fbk) * fbk
    if n >= 2:
        k = int((n + 1) / 2)
        fbk1 = fib(k - 1)
        fbk2 = fib(k)
        return fbk2 * fbk2 + fbk1 * fbk1
    else:
        x = 0; y = -1
        for i in range(-n-1):
            f = x + y
            x = y; y = f
        return f if n % 2 == 0 else -f