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

Question

霍尼韦尔DPS8计算机（和其他计算机）有一条“除分数”指令：

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

据我所知，这是整数除法，小数点在左边。

  .qqqqq / .ddddd

（我确实在白天将整数数学进行了前移，但我对这些技术的记忆在时间的迷雾中消失了。）

要在DPS8仿真器中实现此指令，我相信我需要从创建两个70位数字开始：71位分红减去符号位，36位除数减去符号位并向左移动35位，以便小数点对齐。

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

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

我是在正确的轨道上，还是解决方案更加细微差别化（从这里起，纠正迹象和检测错误就被省略了；这些阶段都有很好的记录。实际的划分才是问题所在）。任何指向这种硬件仿真的C实现的指针都会特别有用。

Answer 1

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

假设您有一个32位变量，您想要一个8位小数部分。然后，有一个介于0和16777215之间的整数部分，以及一个介于0和255之间的小数部分。0xiiiiiiff（其中i是整数部分，f是小数部分）。

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

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

quotient_fp = (dividend_ip << 8) / divisor_ip

到目前为止，一切顺利。

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

如果我们只是将除数上移8，那么我们会遇到一个问题：（divident\u ip

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

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

...这就。。。（股息\u ip

现在，让我们把分数部分数学放入图片中...

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

我们的商精度将与Distribution\u精度相同，即8位。

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

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

（（（股息\u ip

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

好的，但是因为你只提供小数部分，而整数部分总是零，所以你应该能够直接抛出整数部分。这使得它......（（（dividend_ip

...现在让我们改用64位整数，我们可以在商中获得32位精度...（dividend_fp

... 有些编译器支持int128\u t（它可以在某些GCC平台上启用），因此您可以使用该类型，以便轻松获得128位。我还没有试过，但我之前在网上看到过一些信息；搜索int128\u t，您可能会发现如何进行。

如果让int128\t工作，则可以使被除数为128位，除数为64位，商为64位。。。商\u fp=（（股息\u fp

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

一直以来，我遇到了一个非常聪明的ARM-in-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是余数（余数，模结果）

上述例程包含无符号除法的基本知识。

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