def mul(n,m): # compute n*m; n and m are nonnegative integers, with n < 2^32
k = 32
# new variables:
# d = b/2^(32-k), so b = d*2^(32-k)
# e = c*2^k + a
#a = n
#b = m
#c = 0
d = m # because d = b/2^(32-k) = m/2^(32-32) = m
e = n # because e = c*2^k + a = 0*2^32 + n = n
# invariant ab+c = nm and a < 2^k
while k != 0:
if e&1 == 1:
# no need to do a = a - 1, because of later a=a>>1
# c = c + b
# e' = c'*2^k + a
# = (c+b)*2^k + a
# = c*2^k + b*2^k + a
# = (c*2^k + a) + b*2^k
# = e + b*2^k
# = e + (d*2^(32-k))*2^k
# = e + d*2^32
e = e + (d<<32)
# (a-1)b + (c+b) = ab -b + c + b = ab+c = nm
#a = a>>1
#b = b<<1
# d doesn't need updating, because b doubled and k decreases by 1
e = e>>1
# (a/2)2b+c = ab+c = nm
k = k - 1
# since the previous a was < the previous 2^k,
# a/2 < 2^(k-1)
# (a-1)/2 < 2^(k-1)
# we know a < 2^0, so a=0, just like before
return e