This kata is a continuation of [Part 1](http://www.codewars.com/kata/the-fibfusc-function-part-1). The `fibfusc` function is defined recursively as follows:

    fibfusc(0) = (1, 0)
    fibfusc(1) = (0, 1)
    fibfusc(2n) = ((x + y)(x - y), y(2x + 3y)), where (x, y) = fibfusc(n)
    fibfusc(2n + 1) = (-y(2x + 3y), (x + 2y)(x + 4y)), where (x, y) = fibfusc(n)

Your job is to produce the code for the `fibfusc` function. In this kata, your function will be tested with large values of n (up to 2000 bits), so you should be concerned about stack overflow and timeouts. Moreover, since the `fibfusc` function grows exponentially, your function should take an extra argument `num_digits` with a default value of `None`. When not `None`, `num_digits` takes a positive `int` value and the returned values shall be truncated to the last `num_digits` digits. 

For example, let `n = 101`. With `num_digits` not set or set to `None`, `fibfusc` should return: 
`(-280571172992510140037611932413038677189525L, 734544867157818093234908902110449296423351L)`. If `num_digits = 12`, the function should return `(-38677189525L, 449296423351L)`. Notice in particular, that for any value of `n` greater than 1, `x` is negative, and the truncated value of `x` should also be negative.

Hint 1: Use modulo `10 ** num_digits` arithmetic to keep all intermediary results small.

Hint 2: Consider using an iterative ["number climber"](http://www.codewars.com/kata/number-climber) to avoid stack overflows.

Difficulty: interview

Starter code:

def fibfusc(n, num_digits=None):
	

Solutions:
def fibfusc(n, num_digits=None):
    if n < 2: return (1 - n, n)
    b = bin(n)[2:]
    
    x, y = fibfusc(int(b[0]))
    for bit in b[1:]:
        if bit == "1":
            x, y = (-y*(2*x + 3*y), (x + 2*y)*(x + 4*y))
        else:
            x, y = ((x + y) * (x - y), y * (2*x + 3*y))
        if num_digits:
            x, y = x % 10 ** num_digits - 10**num_digits, y % 10 ** num_digits
    return x, y


def fibfusc(n, num_digits=None):
    if num_digits: mod = pow(10, num_digits)
    x, y = 1, 0
    for c in bin(n)[2:]:
        if c == '0':
            x, y = (x + y) * (x - y), y * ( 2 * x + 3 * y)
        else:
            x, y = -y * (2 * x + 3 * y), (x + 2 * y) * (x + 4 * y)
        if num_digits:
            x, y = x % -mod, y % mod
    return x, y


def fibfusc(n, num_digits=None):
    f0 = lambda x, y: ((x + y) * (x - y), y * (2 * x + 3 * y))
    f1 = lambda x, y: (-y * (2 * x + 3 * y), (x + 2 * y)*(x + 4 * y))
    
    x, y = 1, 0
    if num_digits: m = 10 ** num_digits
    for digit in bin(n)[2:]:
        if digit == '0':
            x, y = f0(x, y)
        else:
            x, y = f1(x, y)
        if num_digits:
            x, y = x%m - m, y%m
      
    return (x, y)


def climb(n):
    r=[n]
    while(n>1):
        if n%2==0:
            n//=2
        else:
            n=(n-1)//2
        r.append(n)
    return r[::-1]

def fibfusc(n, num_digits=None):
    if n==0: return (1,0)
    r=climb(n)
    x,y=0,1
    for i in r[1:]:
        if i%2==0:
            if num_digits:
                x,y=((x+y)%(10**num_digits))*(x-y), y*((2*x+3*y)%(10**num_digits))
            else:
                x,y=(x+y)*(x-y), y*(2*x+3*y)
        else:
            if num_digits:
                x,y=-y*((2*x+3*y)%(10**num_digits)), (x+2*y)*(x+4*y)
            else:
                x,y=-y*(2*x+3*y), (x+2*y)*(x+4*y)
        if num_digits:
            x=x%(10**num_digits) if x>=0 else -(abs(x)%(10**num_digits))
            y=y%(10**num_digits)
    return (x,y)

def fibfusc(n, num_digits=None):
    if num_digits: num_digits = 10 ** num_digits
    x, y = 1, 0
    for c in bin(n)[2:]:
        if c == '1': x, y = -y * (2*x + 3*y), (x + 2*y) * (x + 4*y)
        else: x, y = (x + y) * (x - y), y * (2*x + 3*y)
        if num_digits: x, y = x % -num_digits, y % num_digits
    return x, y

def fibfusc(n, num_digits=None):
    if n==0: return (1,0)
    x,y=0,1
    trunc=1 if num_digits==None else 10**(num_digits)
    nbin=bin(n)[3:]
    for i in nbin:
        x,y=((x+y)*(x-y),y*(2*x+3*y)) if i=='0' else (-y*(2*x + 3*y),(x + 2*y)*(x + 4*y))
        if trunc > 1 : x,y=(-(-x % trunc),y % trunc)   
    
    return x,y

def fibfusc(n, num_digits=None):
    x, y = 1, 0
    for k in range(len(bin(n)) - 3, - 1, -1):
        m = n >> k
        if m & 1:
            x, y = -y * (2 * x + 3 * y), (x + 2 * y) * (x + 4 * y)
        else:
            x, y = (x + y) * (x - y), y * (2 * x + 3 * y)
        if num_digits:
            x, y = x % 10 ** num_digits, y % 10 ** num_digits
    if num_digits and n > 1:
        x -= 10 ** num_digits
    return x, y

def fibfusc(n, num_digits=None):
    m = 10 ** num_digits if num_digits is not None else None
    x, y = 1, 0
    for i in reversed(range(n.bit_length())):
        if n & 1 << i == 0:
            x, y = ((x + y) * (x - y), y * (2*x + 3*y))
        else:
            x, y = (-y * (2*x + 3*y), (x + 2*y) * (x + 4*y))
        if m is not None:
            x %= m
            y %= m
    if m is not None and n >= 2:
        x -= m
    return x, y

def fibfusc(n, num_digits=None):
    arr=[]
    (x,y)=(0,1)
    
    if num_digits: MOD=10**num_digits  
    if n==0: return (1,0)
    
    while n>1:
        arr.append(n)
        n//=2
    arr=list(reversed(arr))
    
    for i in arr:
        if i%2==0: (x,y)=(((x+y)*(x-y),y*(2*x+3*y)))
        else: (x,y)=((-y*(2*x+3*y),(x+2*y)*(x+4*y)))
        if num_digits: (x,y)=(x%MOD,y%MOD)
        
    if arr and num_digits: x = -MOD+(x%MOD)
    return (x,y)