[具有32/16位除法的处理器上的64/32位除法

Question

My processor，一个没有FPU和整数数学运算的小型16位微控制器，只有16/16除法和32/16除法，它们都需要18个周期。目前，我正在使用非常慢的软件例程（〜7,500个周期）来执行64/32除法。有什么方法可以使用这些除法引擎来计算64/32除法吗？类似于我已经在使用16x16乘法器和加法器来计算32x32乘法的方式类似？我正在使用C，但是可以使用任何一般性的解释来说明如何实现...我希望目标是<200个周期（如果可能的话）。

Answer 1

请参见“ Hacker's Delight”，多字划分（第140-145页）。

基本概念（回溯至Knuth）是以65536为基数来考虑您的问题。然后您有一个4位数乘2位数除法的问题，以2/1位数除法为基元。

C代码在这里：https://github.com/hcs0/Hackers-Delight/blob/master/divmnu.c.txt

Answer 2

我的Knuth（计算机编程的艺术）副本正在工作，所以直到星期一我才能检查它，但这将是我的第一份资料。它有一个完整的算术部分。

---

编辑：您关于“ 16/16除法和32/16除法都需要18个周期的信息”。 -dsPIC在汇编中具有条件减法运算。考虑将其用作您的计算原语。

还请注意，如果X = XH * 2 ³² + XL和D = DH * 2 ¹⁶ + DL，那么如果您正在寻找

（（Q，R）= X / D，其中X = Q * D + R

其中，Q = QH * 2 ¹⁶ + QL，R = RH * 2 ¹⁶ + RL，则

XH * 2 ³² + XL = DH * QH * 2 ³² +（DL * QH + DH * QL）* 2 ¹⁶ +（DL * QL）+ RH * 2 ¹⁶ + RL

[这建议（通过查看高32位的术语）建议使用以下过程，类似于长除法：

1. [（QH，R0）= XH /（DH + 1）-> XH = QH *（DH + 1）+ R0 [32/16除数]
2. R1 = X-（QH * 2 ¹⁶）* D [需要16 * 32乘法，左移16并减去64位]
3. 计算R1'= R1-D * 2 ¹⁶
4. 当R1'> = 0时，将QH向上调1，设置R1 = R1'，然后转到步骤3
5. （（QL，R2）=（R1 >> 16）/（DH + 1）-> R1 = QL *（DH + 1）+ R2 [32/16除数]
6. [R3 = R1-（QL * D）[需要16 * 32乘法和48位减]]
7. 计算R3'= R3-D
8. 当R3'> = 0时，将QL向上调1，设置R3 = R3'，然后转到步骤7

您的32位商是对（QH，QL），而32位余数是R3。

（（假设商不大于32位，您需要提前知道，并且可以方便地提前进行检查。）

Answer 3

起点将是：D. Knuth，计算机编程艺术，第2卷，第4.3.1节，算法D

但是我想您可能需要优化算法。

Answer 4

您可能想看Booth's Algorithm（http://www.scribd.com/doc/3132888/Booths-Algorithm-Multiplication-Division）。

您想要的部分大约位于页面的1/2位置。

自从我的VLSI课程以来，我还没有看过这个，但是，这可能是您最好的选择，如果可能的话，您可能希望在组装时进行此操作，并尽可能地对其进行优化（如果您经常调用它）。

基本上涉及移位，加法或减法。