固定点整数除法（“分数除法”）算法

Question

霍尼韦尔DPS8计算机（以及其他计算机）具有/曾经具有“分数除法”指令：

“此指令通过将包括符号在内的71位小数被除数（dividend）除以包括符号在内的36位小数除数（divisor），形成一个包括符号在内的36位小数商（quotient）和一个包括符号在内的36位小数余数（remainder）。余数的第35位对应于被除数的第70位。余数的符号等于除数的符号，除非余数为零。”

因此，据我所知，这是整数除法，小数点远在左侧。

  .qqqqq / .ddddd

（在以前的FORTH中，我曾经进行过整数缩放运算，但我对这些技术的记忆已经逐渐模糊。）

要在DPS8仿真器中实现此指令，我认为需要创建两个70位数字：71位被除数减去其符号位，和36位除数减去其符号位并向左移动35位，以使小数点对齐。

然后使用“％”和“/”（在C语言中）形成余数和商，但我不确定这些结果是否需要归一化（即移位）。

我在"计算机算术"第10页找到了一个“移位和减法”的算法示例，但我更喜欢更直接的实现方式。

我走在正确的道路上吗？还是解决方案更加微妙（修正符号和检测错误的阶段已被省略；这些阶段文档已经很好了。实际除法是问题所在。）任何指向此类硬件仿真的C实现的指针都将特别有帮助。

- user1538392

Answer 1

我没有确切的答案，但是因为除法就是除法，你可能会发现查看一些基本的除法例程很有帮助。

假设你有一个32位变量，并且你想要一个8位小数部分。 那么你的整数部分在0到16777215之间，而小数部分在0到255之间。 0xiiiiiiff（其中i是整数部分，f是小数部分）。

假设你有一个24位被除数（分子），比如值为3，和一个24位除数（分母），比如值为13。 正如我们很快将看到的那样，3/13大于零且小于一。这意味着我们的小数部分非零，但是我们的整数部分完全填满了零。

所以，为了使用标准的除法函数进行上述除法，我们只需将被除数向左移动N位，这样我们的小数部分就可以得到N位精度。

quotient_fp = (dividend_ip << 8) / divisor_ip

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

但如果我们想要除数有小数部分呢？

如果我们只是将除数向上移8位，那么就会有一个问题：(被除数_ip << 8) / (除数_ip << 8)——因为我们显然会失去商（结果）的小数部分。

相反，我们需要将被除数向上移动尽可能多的位数，以便与我们移动的小数部分相匹配...

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

...这使得它...

(被除数IP <<（被除数精度+除数精度）/（除数IP <<除数精度）

现在，让我们把我们的小数部分数学运算带入计算...

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

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

不幸的是，这需要大量的位数。

幸运的是，在您的情况下，整数部分并不重要，因此小数部分有很多空间。让我们把精度增加到15位；可以使用普通的32位整数进行测试...

(((被除数ip << 15) | 被除数fp) << 15) / ((除数ip << 15) | 除数fp)

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

好的，但由于您仅提供小数部分，而整数部分始终为零，因此您应该能够丢弃整数部分。这样就变成了....

(((被除数ip << 16) | 被除数fp) << 16) / 除数fp ... 简化为 ...

(被除数fp << 16) / 除数fp ... 现在让我们使用64位整数，我们可以得到32位商数精度...

(被除数fp << 32) / 除数fp ... 一些编译器支持int128_t（在某些平台上可以启用GCC），因此您可能可以使用该类型，以轻松获得128位。我没有尝试过，但我早些时候在网上看到过相关信息。搜索int128_t，您可能会发现如何操作。

如果您使int128_t工作，您可以使被除数为128位，除数为64位，商数为64位...

商数fp = ((被除数fp << 36) / 除数) >> (64 - 36)

... 以获得36位精度。请注意，由于结果在商的前36位中，因此需要将商向下移位（64-36）= 28位。您甚至可以提高到（128-36）= 92位精度：

(被除数fp << 92) / 除数

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

随着时间的推移，我发现了一种ARM的非常聪明的实现方法，用ARM汇编语言编写。通常情况下，我不会发布参考或汇编语言示例，但考虑到代码非常小，我认为这应该没问题。

摘自A Fast Hi Precision Fixed Point Divide

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 是余数（剩余量，模结果）

上述程序包含了无符号除法的基础。

我希望这些信息对您有所帮助。由于我没有测试任何提到的代码或示例，它可能会包含错误。但我相信，它并非完全错误。;)

- user1985657