两个n位数字的递归除法算法

Question

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

\n\n

请给出该递归除法算法的理论论证。

\n\n

提前致谢。

\n\n

function divide(x, y) \n   if x = 0: \n      return (q, r) = (0, 0) \n   (q, r) = divide(floor(x/2), y) \n   q = 2q, r = 2r \n   if x is odd: \n      r = r + 1 \n   if r \xe2\x89\xa5 y: \n      r = r \xe2\x88\x92 y, q = q + 1\n   return (q, r)\n

\n

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执行乘以 2 时更大。