c++ - 大整数除法 - Knuth 算法 D

Question

我必须使用 Knuth 的算法 D(编程艺术第 2 卷)使用大整数除法将任何数字(无论大小)除以另一个数字，例如 74839234 by 72548 。

我做了两个数组来表示这些数字

n[] = {7,4,8,3,9,2,3,4}
d[] = {7,2,5,4,8}

我正在尝试获得这样的输出:

q[] = {1,0,3,1}
r[] = {4,2,2,4,6}

我真的不知道从哪里开始。任何帮助或指导将不胜感激!

Answer 1

在 D1 你有 d=1，所以设置

n[]={0,7,4,8,3,9,2,3,4}

n = 5，m = 3。

另外，在步骤D4中有一个形式错误:(第二行)应该是...

减去 q(hat) 次 (v1, v2, ..., vn)b TIMES b ** (m - j)。

这里，**表示“的力量”(Fortran风格，便于书写)。当然，这里b = 10，所以

times b ** (m - j) 将减数左移到适当的减法位置。