乘除法的递归运算
2014-05-24
乘法公式
算法：
function multiply(x, y)
Input: Two n-bit integers x and y, where y >= 0
Output: Their product
if y = 0: return 0
z = multiply(x, math.floor(y / 2))
if y is even:
return z
else:
return x + 2z
除法
一个整数x除以另一个整数y(y!=0)，意味需要找到一个商数q和一个余数r，使得 x = yq + r，同时r < y。
function divide(x, y)
Input: Two n-bit integers x and y, where y >= 1
Output: The quotient and remainder of x divided by y
if x = 0: return (q, r) = (0, 0)
(q, r) = divide(math.floor(x / 2), y)
q = 2 * q r = 2 * r
if x is odd: r = r + 1
if x >= y: r = r -y, q = q + 1
return (q, r)