Teaching Kids Programming – Multipy Two Integers Without Multiplication, Division and Bit Shifting

Teaching Kids Programming: Videos on Data Structures and Algorithms

Multiply Two Numbers without usig any Multiply, Divide, and Bit Shifting Operators.

1
2

def mul(a, b):
  return a * b

def mul(a, b):
  return a * b

Algorithm to Multiply Two Integers without Multiply, Divide and Bit Shifting

Given a and b two non-negative integers, we can add number b a times or add number a b times. If any (or both) the numbers are negative, we can always turn the signs so that we can focus on dealing with the multiplication of two non-negative numbers.

If a is smaller than b, for example, 3*5, we prefer 5+5+5 instead of 3+3+3+3+3, because the former involves less addition operations. We can implement this in pure recursion:

1
2
3
4
5
6
7
8
9
10
11
12

def mul(a, b):
  if a == 0 or b == 0:
    return 0
  if a < 0 and b < 0:
    return mul(-a, -b)
  if a < 0:
    return mul(-a, b)
  if b < 0:
    return mul(a, -b)
  if a > 0:
    return mul(b, a)
  return mul(a - 1, b) + b

def mul(a, b):
  if a == 0 or b == 0:
    return 0
  if a < 0 and b < 0:
    return mul(-a, -b)
  if a < 0:
    return mul(-a, b)
  if b < 0:
    return mul(a, -b)
  if a > 0:
    return mul(b, a)
  return mul(a - 1, b) + b

That is: . We can implement this using Iterative Approach e.g. while loop:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

def mul(a, b):
  if a == 0 or b == 0:
    return 0
  if a < 0 and b < 0:
    return mul(-a, -b)
  if a < 0:
    return mul(-a, b)
  if b < 0:
    return mul(a, -b)
  if a > 0:
    return mul(b, a)
  ans = 0
  while a > 0:
    ans += b
    a -= 1
  return ans

def mul(a, b):
  if a == 0 or b == 0:
    return 0
  if a < 0 and b < 0:
    return mul(-a, -b)
  if a < 0:
    return mul(-a, b)
  if b < 0:
    return mul(a, -b)
  if a > 0:
    return mul(b, a)
  ans = 0
  while a > 0:
    ans += b
    a -= 1
  return ans

The time complexity is O(Min(|a|, |b|)). If we can use the division or bit shifting, when a is even, a*b can be reduced to (a/2)*(b*2), so we can further reduce the number of additions to O(logN)) where N is Min(|a|, |b|).

–EOF (The Ultimate Computing & Technology Blog) —