14

我正在开发一个没有硬件乘法和除法的微控制器。我需要为这些基本操作编写软件算法,这些算法在紧凑的尺寸和效率之间取得了很好的平衡。我的 C 编译器移植将使用这些算法,而不是 C 开发人员自己。

到目前为止,我的 google-fu 主要是在这个话题上出现噪音。

任何人都可以指出我的信息吗?我可以使用 add/sub 和 shift 指令。基于表查找的算法也可能对我有用,但我有点担心在编译器的后端塞进这么多……嗯,可以这么说。

4

7 回答 7

6

这是一个简单的乘法算法:

  1. 从最右边的乘数开始。

  2. 如果乘数中的位为 1,则添加被乘数

  3. 将被乘数移动 1

  4. 移动到乘法器中的下一位并返回步骤 2。

这是一个除法算法:

  1. 如果除数大于被除数,则停止。

  2. 当除数寄存器小于除数寄存器时,左移。

  3. 将除数寄存器右移 1。

  4. 从被除数寄存器中减去除数寄存器,并将结果寄存器中与除数寄存器的移位总数相对应的位更改为 1。

  5. 以原始状态的除数寄存器从第 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 回答
1

一种简单且性能相当好的整数乘法算法是俄罗斯农民乘法

对于有理数,您可以尝试使用二进制引号表示法,除法比平时更容易。

于 2010-03-05T22:36:28.200 回答
0

要进行乘法运算,如果乘法器中的相应位已设置,则将移位被乘数的部分乘积加到累加器中。在循环结束时移动被乘数和乘数,测试乘数和 1 以查看是否应该进行加法。

于 2010-03-05T22:39:47.660 回答
0

Microchip PICmicro 16Fxxx 系列芯片没有乘法或除法指令。也许它的一些软乘法和软除法例程可以移植到您的 MCU。

PIC单片机基本数学乘法方法

PIC单片机基本数学除法方法

另请查看除法的“牛顿法”。我认为该方法给出了我见过的任何除法算法中最小的可执行大小,尽管解释使它听起来比实际更复杂。我听说一些早期的 Cray 超级计算机使用牛顿的除法方法。

于 2010-06-01T00:53:19.463 回答