karatsuba using fast exponentiation i.e. Factors number in powers of 2 using its binary form that sum up to it

karatsuba_fast_exponentiation.py

import operator

def karatsuba(x,y):
  '''Function to multiply 2 numbers.
  
  
  More efficient manner than the 
  grade school algorithm.
  '''
  stack = []
  while 1:
      n = max(len(str(x)),len(str(y)))
      nby2 = n / 2
      a = x / 10**(nby2)
      b = x % 10**(nby2)
      c = y / 10**(nby2)
      d = y % 10**(nby2)
      stack.append([a+b, c+d])
      x, y = a, c
      if len(str(x)) == 1 or len(str(y)) == 1:
          stack.append(x*y)

  if len(str(x)) == 1 or len(str(y)) == 1:
    return x*y
  else:
    n = max(len(str(x)),len(str(y)))
    nby2 = n / 2
    a = x / 10**(nby2)
    b = x % 10**(nby2)
    c = y / 10**(nby2)
    d = y % 10**(nby2)
    ac = karatsuba(a,c)
    bd = karatsuba(b,d)
    ad_plus_bc = karatsuba(a+b,c+d) - ac - bd

  # this little trick, writing n as 2*nby2 takes care of both even and odd n
  prod = ac * exp(10, (2*nby2)) + (ad_plus_bc * exp(10, nby2)) + bd
  return prod

def exp(base, exponent):
  '''Binary exponents using 2^k-ary method.

  Fast exponentiation using divide and conquer method that breaks the 
  exponent into its decimal addends that sum up to it using
  binary factorization.


  params:
    base: int, a number.
    exponent: int, the power for the base.
  
  returns:
    int, a number.
  '''
  exponent_arr = binary_2_dec_factors(exponent)
  return reduce(operator.mul, [pow(base, num) for num in exponent_arr])


def binary_2_dec_factors(number):
	'''Factors number in powers of 2 using its binary form that sum up to it.
		
		params:
			number: int.
		returns:
			list, an array of factors.
	'''
	
	dec_factors = []
	binary_str = bin(number).lstrip('0b')
	ln = len(binary_str)
	for idx in xrange(ln, 0, -1):
		dec_place = idx - 1
		digit = int(binary_str[ln-dec_place-1])
		if digit:
			pow2 = (2*digit)**dec_place
			# print('pow2 %d, dec place %d, digit %d' %(pow2, dec_place,digit))
			dec_factors.append(pow2)
	return dec_factors