定点整数除法（“小数除法”）算法

Question

Honeywell DPS8 计算机（和其他计算机）具有“除小数”指令：

该指令将 71 位小数被除数（包括符号）除以 36 位小数除数（包括符号），形成 36 位小数商（包括符号）和 36 位小数余数（包括符号）。余数的 35 对应于被除数的第 70 位。除非余数为零，否则余数符号等于被除数符号。

所以，据我了解，这是整数除法，小数点位于左侧。

  .qqqqq / .ddddd

（我当时在 FORTH 中做过缩放整数数学，但我对这些技术的记忆已经消失在时间的迷雾中。）

要在 DPS8 模拟器中实现此指令，我相信我需要首先创建两个 70 位数字：71 位被除数减去其符号位，36 位除数减去其符号位并向左移动 35 位，以便小数点对齐。

我想我可以用“%”和“/”形成余数和商（在C语言中），但我不确定这些结果是否需要标准化（即移位）。

我找到了“移位和减法”算法“计算机算术” ，幻灯片 10）的示例，但我更喜欢更直接的实现。

我是否走在正确的轨道上，或者解决方案是否更加细致（修复迹象和错误检测已从此处省略；这些阶段都有详细记录。实际的划分是问题所在。）。任何指向此类硬件模拟的 C 实现的指针都会特别有帮助。

Answer 1

我没有明确的答案，但由于除法就是除法，您可能会发现查看一些基本的除法例程很有帮助。

假设您有一个 32 位变量，并且想要一个 8 位小数部分。然后，您将得到 0 到 16777215 之间的整数部分和 0 到 255 之间的小数部分。 0xiiiiiiiff （其中 i 是整数部分，f 是小数部分）。

假设您有一个 24 位被除数（分子）（例如值 3）和一个 24 位除数（分母）（例如值 13）。我们很快就会看到，3/13 大于 0 且小于 1。这意味着我们的小数部分不为零，但整数部分完全用零填充。

因此，要使用标准除法函数进行上述除法，我们只需将被除数移位 N，这样我们就可以在小数部分获得 N 位精度。

quotient_fp = (dividend_ip << 8) / divisor_ip

到目前为止，一切都很好。

但是如果我们希望除数有小数部分呢？

如果我们只是将除数上移 8，那么我们就会遇到一个问题： (dividend_ip << 8) / (divisor_ip << 8) - 因为我们显然会丢失商（结果）的小数部分。

相反，我们需要将股息向上移动与向上移动小数部分一样多的位数......

((dividend_ip << 8) << 8) / (divisor_ip << 8)

...这使得... (dividend_ip << (dividend_ precision + divisor_ precision) / (divisor_ip << divisor_ precision)

现在，让我们将小数部分数学代入图中......

(((dividend_ip << dividend_precision) | dividend_fp) << divisor_precision) / ((divisor_ip << divisor_precision) | divisor_fp)

我们的商的精度将与被除数精度相同，均为 8 位。

不幸的是，这会吃掉很多东西。

幸运的是，在您的情况下，整数部分并不重要，因此您将为小数部分提供很大的空间。让我们将精度提高到 15 位；这可以使用普通的 32 位整数进行测试......

(((dividend_ip << 15) | dividend_fp) << 15) / ((divisor_ip << 15) | divisor_fp)

我们的商现在将具有 15 位精度。

好的，但由于您只提供小数部分，而整数部分始终为零，因此您应该能够只丢弃整数部分。这使得...... (((dividend_ip << 16) |dividend_fp) << 16) / ((divisor_ip << 16) | divisor_fp) ...减少到... (dividend_fp << 16) / divisor_fp

...现在让我们使用 64 位整数，我们可以得到 32 位精度的商... (dividend_fp << 32) / divisor_fp

...一些编译器支持 int128_t （它可以在某些 GCC 平台上启用），因此您可能可以使用该类型，以便轻松获得 128 位。我没有尝试过，但我之前在网上看到过信息；搜索 int128_t，您可能会找到方法。

如果你让 int128_t 工作，你可以使被除数为 128 位，除数为 64 位，商为 64 位... quotient_fp = ((dividend_fp << 36) / divisor) >> (64 - 36) ...为了获得36位精度。请注意，由于结果位于商的前 36 位中，因此商需要下移 (64 - 36) = 28 位。您甚至可以高达 (128 - 36) = 92 位精度：(dividend_fp << 92) / 除数

现在，您可能（希望）有一个解决方案，我想建议您熟悉低级二进制除法（再次；因为您不久前已经经历过）。最好的来源似乎是硬件如何划分二进制数；例如微控制器、CPU等。汇编语言分隔符也有利于了解内部工作原理。通常，使用位移位的 32 位除法例程是非常好的源。

在这段时间里，我发现了一种非常巧妙的用 ARM 汇编语言实现 ARM 的方法。通常我不会发布参考资料或汇编语言示例，但考虑到代码非常小，我认为这样就可以了。

摘自快速高精度定点除法

r0 是分子（被除数） r2 是分母（除数）

    mov     r1,#0
    adds    r0,r0,r0
    .rept   32
    adcs    r1,r2,r1,lsl#1
    subcc   r1,r1,r2
    adcs    r0,r0,r0
    .endr

r0 是商（结果） r1 是余数（余数，模结果）

上面的例程包含无符号除法的基础知识。

我希望这些信息会有用。它可能包含错误，因为我没有测试提到的任何代码或示例。不过，我相信这并不全是错误的。;)