具有 32/16 位除法的处理器上的 64/32 位除法 [英] 64/32-bit division on a processor with 32/16-bit division

问题描述

我的处理器，一个没有 FPU 的小型 16 位微控制器整数数学只有 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.)

推荐答案

参见Hacker's Delight"，多词划分(第 140-145 页).

See "Hacker's Delight", multiword division (pages 140-145).

基本概念(回到 Knuth)是用 base-65536 术语来考虑您的问题.然后你有一个 4 位数乘 2 位数的除法问题，以 2/1 位数除法作为原始.

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.

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

这篇关于具有 32/16 位除法的处理器上的 64/32 位除法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！