具有 32/16 位除法的处理器上的 64/32 位除法
我的处理器，一个小型 16 位微控制器，没有 FPU 和整数数学只有16/16除法和32/16除法，两者都需要18个周期。目前我正在使用非常慢的软件例程（约 7,500 个周期）来执行 64/32 除法。有什么方法可以使用这些除法引擎来计算 64/32 除法吗？类似于我已经使用 16x16 乘法器和加法器来计算 32x32 乘法吗？我正在使用 C，但可以使用任何关于如何完成它的一般解释...我希望目标是 <200 个周期（如果可能的话）。
My processor, a small 16-bit microcontroller with no FPU and integer math only has 16/16 division and 32/16 division which both take 18 cycles. At the moment I'm using a very slow software routine (~7,500 cycles) to do 64/32 division. Is there any way to use these division engines to calculate a 64/32 division? Similar to how I'm already using the 16x16 multiplier and adder to calculate 32x32 multiplies? I'm using C but can work with any general explanation on how it can be done... I'm hoping to target <200 cycles (if it's at all possible.)
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
请参阅“黑客的乐趣”，多词除法（第 140-145 页）。
基本概念（回到 Knuth）是用 base-65536 术语来思考你的问题。然后你有一个 4 位乘 2 位除法问题，以 2/1 位除法作为原语。
C代码在这里： https://github.com/ hcs0/Hackers-Delight/blob/master/divmnu.c.txt
See "Hacker's Delight", multiword division (pages 140-145).
The basic concept (going back to Knuth) is to think of your problem in base-65536 terms. Then you have a 4 digit by 2 digit division problem, with 2/1 digit division as a primitive.
The C code is here: https://github.com/hcs0/Hackers-Delight/blob/master/divmnu.c.txt
我的《高德纳 (Knuth)》（《计算机编程的艺术》）正在使用，所以我要到周一才能查看它，但这将是我的第一个来源。它有一整个部分是关于算术的。
编辑：您关于“16/16 划分和 32/16 划分都需要 18 个周期”的帖子。 -- dsPIC 在汇编中具有条件减法运算。考虑使用它作为您的计算原语。
另请注意，如果 X = XH * 232 + XL 且 D = DH * 216 + DL，那么如果您正在寻找
(Q,R) = X/ D 其中 X = Q * D + R
其中 Q = QH * 216 + QL，R = RH * 216 + RL，则
XH * 232 + XL = DH * QH * 232 + (DL * QH + DH * QL) * 216 + (DL * QL) + RH * 2 16 + RL
这建议（通过查看高 32 位的项）使用以下过程，类似于长除法：
您的 32 位商是对 (QH,QL)，32 位余数是 R3。
（这里假设商不大于32位，你需要提前知道，并且可以轻松提前检查。）
My copy of Knuth (The Art of Computer Programming) is at work, so I can't check it until Monday, but that would be my first source. It has a whole section on arithmetic.
edit: your post about "16/16 division and 32/16 division which both take 18 cycles." -- dsPICs have a conditional subtract operation in assembly. Consider using this as your computational primitive.
Also note that if X = XH * 232 + XL and D = DH * 216 + DL, then if you are looking for
(Q,R) = X/D where X = Q * D + R
where Q = QH * 216 + QL, R = RH * 216 + RL, then
XH * 232 + XL = DH * QH * 232 + (DL * QH + DH * QL) * 216 + (DL * QL) + RH * 216 + RL
This suggests (by looking at terms that are the high 32 bits) to use the following procedure, akin to long division:
Your 32-bit quotient is the pair (QH,QL), and 32-bit remainder is R3.
(This assumes that the quotient is not larger than 32-bit, which you need to know ahead of time, and can easily check ahead of time.)
起点是：
D. Knuth，《计算机编程艺术》第 2 卷，第 4.3.1 节，算法 D
但我想您可能需要优化算法。
Starting point would be:
D. Knuth, The Art of Computer Programming Vol.2, Section 4.3.1, Algorithm D
But I suppose you may need to optimize the algorithm.
您可能需要查看
Booth 算法(http ://www.scribd.com/doc/3132888/Booths-Algorithm-Multiplication-Division）。您想要的部分大约位于页面下方的 1/2 处。
自从我的 VLSI 课程以来，我还没有看过这个，但是，这可能是你最好的选择，如果可能的话，你可能想在汇编中执行此操作，以尽可能优化它，如果你会经常调用它。
基本上涉及移位和加减。
You may want to look at
Booth's Algorithm(http://www.scribd.com/doc/3132888/Booths-Algorithm-Multiplication-Division).The part you want is about 1/2 way down the page.
I haven't looked at this since my VLSI class, but, this may be your best bet, if possible you may want to do this in assembly, to optimize it as much as possible, if you will be calling this often.
Basically involves shifting and adding or subtracting.