algorithm - 两个n位数的递归除法算法

Question

在下面的除法算法中，我无法理解为什么将 q 和 r 乘以 2 有效，以及为什么如果 x 为奇数则 r 递增。

请给出这种递归除法算法的理论依据。

提前致谢。

function divide(x, y) 
   if x = 0: 
      return (q, r) = (0, 0) 
   (q, r) = divide(floor(x/2), y) 
   q = 2q, r = 2r 
   if x is odd: 
      r = r + 1 
   if r ≥ y: 
      r = r − y, q = q + 1
   return (q, r)

Answer 1

假设您要划分 x通过 y ，即代表x = Q * y + R

让我们假设 x甚至。你递归地划分 x / 2通过 y并为较小的案例获得所需的表示形式:x / 2 = q * y + r .

将它乘以二，你会得到:x = 2q * y + 2r .查看您想为 x 获得的表示首先，你看到你找到了!让Q = 2q和 R = 2r你找到了想要的 Q和 R .

如果x很奇怪，您再次首先获得较小情况的所需表示:(x - 1) / 2 = q * y + r , 乘以二:x - 1 = 2q * y + 2r , 并发送 1右边:x = 2q * y + 2r + 1 .同样，您找到了 Q和 R你想要:Q = 2q , R = 2r + 1 .

算法的最后一部分只是归一化，因此 r < y . r可以变得大于y当您执行乘以二时。