Recursive Multiply

Write a recursive function to multiply two positive integers without using the * operator. You can use addition, subtraction, and bit shifting, but you should minimize the number of those operations

Naive solution

The "naive" approach to this problem, is quite simple:

def rec_mult(a,b):
  if b == 0:
    return 0
  if b == 1:
    return a
  return a + rec_mult(a, b-1)

The time complexity of this would be O(b) - not great.

Bit manipulation, anyone?

The question mentioned bit manipulation, so I thought that would be a good place to start.

After some research and experimentation, I discovered you can effectively multiply a number by a power of two by shifting left by whatever the power of two is. For example, 3 << 4 is the same as 3 * 2^4.

This is a significantly more efficient way to do it. Instead of only reducing b by 1 on each recursion, we reduce b by its most significant bit!

Solution

def rec_mult(a,b):
	# Base cases for recursion
	if b == 0:
		return 0
	if b == 1:
		return a

	# Get the most significant bit and the power of two it represents
	msb = 1
	pwr_of_2 = 0
	while True:
		next_msb = msb << 1
		if next_msb > b:
			break
		pwr_of_2 += 1
		msb = next_msb
		if msb == b:
			break

	# To understand the return value, remember:
	# 1: Left shifting by the power of two is the same as multiplying by the number itself (ie x*16=x<<4)
	# 2: Once we've done that, we still need to multiply by the remainder, hence b - msb
	return (a << pwr_of_2) + rec_mult(a, b - msb)

Big O Analysis

Time Complexity: O(number of significant bits in b ^ 2)

Space Complexity: O(number of significant bits in b)

Explanation: We make recursive calls equal to number of significant bits in b (so the call stack takes that much space). For each of those calls, we have to find the next most significant bit.