我正在开发一个没有硬件乘法和除法的微控制器。我需要为这些基本操作编写软件算法，这些算法在紧凑的尺寸和效率之间取得了很好的平衡。我的 C 编译器移植将使用这些算法，而不是 C 开发人员自己。
到目前为止，我的 google-fu 主要是在这个话题上出现噪音。
任何人都可以指出我的信息吗？我可以使用 add/sub 和 shift 指令。基于表查找的算法也可能对我有用，但我有点担心在编译器的后端塞进这么多……嗯，可以这么说。
问问题
2690 次
7 回答
6
这是一个简单的乘法算法：
从最右边的乘数开始。
如果乘数中的位为 1，则添加被乘数
将被乘数移动 1
移动到乘法器中的下一位并返回步骤 2。
这是一个除法算法：
如果除数大于被除数，则停止。
当除数寄存器小于除数寄存器时，左移。
将除数寄存器右移 1。
从被除数寄存器中减去除数寄存器，并将结果寄存器中与除数寄存器的移位总数相对应的位更改为 1。
以原始状态的除数寄存器从第 1 步开始。
当然，您需要检查除以 0，但它应该可以工作。
当然，这些算法仅适用于整数。
于 2010-03-05T22:37:31.207 回答
2
我最喜欢的此类参考资料，以书本形式提供：
http://www.hackersdelight.org/
TAoCP 也不会出错：http ://www-cs-faculty.stanford.edu/~uno/taocp.html
于 2010-03-05T22:51:35.023 回答
1
It turns out that I still have some old 68000 assembler code for long multiplication and long division. 68000 code is pretty clean and simple, so should be easy to translate for your chip.
The 68000 had multiply and divide instructions IIRC - I think these were written as a learning exercise.
Decided to just put the code here. Added comments and, in the process, fixed a problem.
;
; Purpose : division of longword by longword to give longword
; : all values signed.
; Requires : d0.L == Value to divide
; : d1.L == Value to divide by
; Changes : d0.L == Remainder
; : d2.L == Result
; : corrupts d1, d3, d4
;
section text
ldiv: move #0,d3 ; Convert d0 -ve to +ve - d3 records original sign
tst.l d0
bpl.s lib5a
neg.l d0
not d3
lib5a: tst.l d1 ; Convert d1 -ve to +ve - d3 records result sign
bpl.s lib5b
neg.l d1
not d3
lib5b: tst.l d1 ; Detect division by zero (not really handled well)
bne.s lib3a
rts
lib3a: moveq.l #0,d2 ; Init working result d2
moveq.l #1,d4 ; Init d4
lib3b: cmp.l d0,d1 ; while d0 < d1 {
bhi.s lib3c
asl.l #1,d1 ; double d1 and d4
asl.l #1,d4
bra.s lib3b ; }
lib3c: asr.l #1,d1 ; halve d1 and d4
asr.l #1,d4
bcs.s lib3d ; stop when d4 reaches zero
cmp.l d0,d1 ; do subtraction if appropriate
bhi.s lib3c
or.l d4,d2 ; update result
sub.l d1,d0
bne.s lib3c
lib3d: ; fix the result and remainder signs
; and.l #$7fffffff,d2 ; don't know why this is here
tst d3
beq.s lib3e
neg.l d2
neg.l d0
lib3e: rts
;
; Purpose : Multiply long by long to give long
; Requires : D0.L == Input 1
; : D1.L == Input 2
; Changes : D2.L == Result
; : D3.L is corrupted
;
lmul: move #0,d3 ; d0 -ve to +ve, original sign in d3
tst.l d0
bpl.s lib4c
neg.l d0
not d3
lib4c: tst.l d1 ; d1 -ve to +ve, result sign in d3
bpl.s lib4d
neg.l d1
not d3
lib4d: moveq.l #0,d2 ; init d2 as working result
lib4a: asr.l #1,d0 ; shift d0 right
bcs.s lib4b ; if a bit fell off, update result
asl.l #1,d1 ; either way, shift left d1
tst.l d0
bne.s lib4a ; if d0 non-zero, continue
tst.l d3 ; basically done - apply sign?
beq.s lib4e ; was broken! now fixed
neg.l d2
lib4e: rts
lib4b: add.l d1,d2 ; main loop body - update result
asl.l #1,d1
bra.s lib4a
By the way - I never did figure out whether it was necessary to convert everything to positive at the start. If you're careful with the shift operations, that may be avoidable overhead.
于 2010-03-05T22:58:43.627 回答
1
这是一个除法算法： http: //www.prasannatech.net/2009/01/division-without-division-operator_24.html
我假设我们在谈论整数？
如果没有硬件支持，您将不得不实现自己的除零异常。
（我没有太多运气很快找到乘法算法，但如果其他人找不到，我会继续寻找）。
于 2010-03-05T22:33:16.940 回答
0
要进行乘法运算，如果乘法器中的相应位已设置，则将移位被乘数的部分乘积加到累加器中。在循环结束时移动被乘数和乘数，测试乘数和 1 以查看是否应该进行加法。
于 2010-03-05T22:39:47.660 回答
0
Microchip PICmicro 16Fxxx 系列芯片没有乘法或除法指令。也许它的一些软乘法和软除法例程可以移植到您的 MCU。
另请查看除法的“牛顿法”。我认为该方法给出了我见过的任何除法算法中最小的可执行大小，尽管解释使它听起来比实际更复杂。我听说一些早期的 Cray 超级计算机使用牛顿的除法方法。
于 2010-06-01T00:53:19.463 回答