How multiplication works

multiply.py

#!/usr/bin/python
# -*- coding: utf-8 -*-

""" How multiplication works """

def simple(a, b):
	""" Multiplication you've learned at school """
	additions = 0
	multiplications = 0
	product = 0
	for power1, digit1 in enumerate(str(b)[::-1]):
		for power2, digit2 in enumerate(str(a)[::-1]):
			power = 10**(power1+power2)
			tmp = int(digit1)*int(digit2)*power
			product += tmp
			additions += 1
			multiplications += 1
	return product, additions, multiplications

def karatsuba(x, y, additions=0, multiplications=0):
	""" kratsuba multiplication that works recursively """
	if len(str(x)) == 1:
		return x*y, additions, multiplications+1
	if len(str(x)) != len(str(y)):
		print "\tnot the same length!"
		return x*y, additions, multiplications+1

	n = len(str(x))
	a = int(str(x)[0:(n/2)])
	b = int(str(x)[(n/2):])
	c = int(str(y)[0:(n/2)])
	d = int(str(y)[(n/2):])
	ac, additions, multiplications = karatsuba(a, c, additions, multiplications)
	bd, additions, multiplications = karatsuba(b, d, additions, multiplications)
	# (a+b)(c+d) = ac + bd + ad + bc - we already got ac and bd
	# mid = a*d + b*c
	apb = a + b
	cpd = c + d
	additions += 2
	mid, additions, multiplications = karatsuba(apb, cpd, additions, multiplications)
	mid -= ac
	mid -= bd
	#print a, b, c, d
	#print "%i = %i*%i + %i*%i = %i * %i - %i - %i" % (mid, a, d, b, c, apb, cpd, ac, bd)
	additions += 2

	additions += 2
	return 10**n * ac + 10**(n/2)*(a*d + b*c) + bd, additions, multiplications

if __name__ == "__main__":
	x = 1234
	y = 5678

	print("%i · %i = %i" % (x, y, x*y))
	print("Simple\t\t\t: %i (%i additions, \t%i multiplications)" % simple(x, y))
	print("Decomposition\t: %i (%i additions, \t%i multiplications)" % karatsuba(x, y))