Thoughts on a better solution for primitive multiply

#1

Hi there, I wrote a faster implementation of bitwise primitive multiply.

def multiply(x,y):
	def add(x,y):
		cum = x ^ y
		carry = (x & y) << 1

		while carry:
			cum, carry = cum ^ carry, (cum & carry) << 1

		return cum
	leftovers = 0
	while y:
		if y & 1:
			leftovers = add(leftovers,x)
  		x <<= 1
		y >>= 1

	return leftovers

Any thoughts on my version vs the one in the book? i think the complexity for my add operation is smaller than O(n) but I’m not exactly sure how to quantify/ analyse it, appreciate if someone can help :smiley:

0 Likes
#2

Hi @xuan-hh,

Great, really appreciate for your idea here, and I think the worst case time complexity is still not changed here but I guess is that average or best case time complexities might improve.

Follow is my take on your solution:

def multiply(x, y):
    def add(a, b):
        while b:
            carry = a & b
            a, b = a ^ b, carry << 1
        return a
    running_sum = 0
    while x: # Examines each bit of x.
        if x & 1:
            running_sum = add(running_sum , y)
            x, y = x >> 1, y << 1
    return running_sum

Please keep up this good work, and really appreciate for your input!

0 Likes
#3

Hi, thanks for the reply. Your solution is definitely cleaner than mine, thanks for the suggestions/ comments!

0 Likes