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

def product(a, b):
    smaller = a if a < b else b
    larger = b if a < b else a
    def helper(smaller, larger): # sum up `larger` in `smaller` times
        if smaller == 0: # 0 x larger = 0
            return 0
        if smaller == 1: # 1 x larger = larger
            return larger
        s = smaller >> 1
        half = helper(s, larger)
        if smaller & 1:
            return half + half + larger
        else:
            return half + half
    return helper(smaller, larger)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

def product(a, b):
    smaller = a if a < b else b
    larger = b if a < b else a
    memo = [-1] * (smaller + 1)
    def helper(smaller, larger, memo):
        if smaller == 0:
            return 0
        if smaller == 1:
            return larger
        if memo[smaller] != -1:
            return memo[smaller]
        s = smaller >> 1
        half = helper(s, larger, memo)
        ret = 0
        if smaller & 1:
            ret = half + half + larger
        else:
            ret = half + half
        memo[smaller] = ret
        return ret
    return helper(smaller, larger, memo)