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.

Source: codewars | Difficulty: MEDIUM_HARD
Tags: Mathematics

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))
		elif 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 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)