我在哪里可以找到软繁殖和分算法?
-
24-09-2019 - |
题
我工作的一个微控制器,而不硬件倍增和分裂。我需要煮了软件的算法对这些基本操作,这是一个很好的平衡紧凑的大规模和提高效率。我的C编译器港口将使用这些算法,不是C开发自己。
我谷歌-fu是迄今为止转动起来大多噪音关于这一主题。
任何人都可以点我的东西情报?我可以使用的增加/子和移指示。查表基础的算法可能还会为我工作,但我有点担心把这么多的成编译器的后端...嗯,可以这么说。
解决方案
这里有一个简单乘法运算法:
开始低位的乘数。
如果位乘数是1中,增加被乘数
转移被乘数由1
移动到下一位乘数和回到第2步。
而这里的分算法:
如果除数大于股息、停止。
同时,除登记小于股息登记册,移离开。
移除数登记权利通过1.
减除数的注册股息的注册和改变位于1的结果登记处位,相当于总数的变化做到的数登记册。
开始在第1步数登记在原来的状态。
当然,你需要放在一个检查分0,但它应的工作。
这些算法,当然,仅仅是为整数。
其他提示
我最喜欢的事情是这样的参考,可以在书的形式:
http://www.hackersdelight.org/
此外,你不能去错TAOCP:的http:// www-cs-faculty.stanford.edu/~uno/taocp.html
下面是一个分裂的算法:的http:// WWW。 prasannatech.net/2009/01/division-without-division-operator_24.html
我认为我们在谈论整数?
如果没有硬件支持,你必须实现自己除以零异常。
(我没有多少运气很快找到乘算法,但我会继续寻找,如果别人没有找到一个)。
事实证明,我仍然有长的乘法和除法长一些旧68000汇编代码。 68000代码非常干净和简单,所以应该很容易转化为你的芯片。
在68000有乘法和除法指令IIRC - 我认为这些被写入作为一个学习锻炼
决定只把代码在这里。添加的评论,并且在这个过程中,固定的问题。
;
; 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
顺便说一句 - 我也没搞清楚,是否有必要在开始时一切积极转换。如果你是细心与移位操作,这可能是可以避免的开销。
要乘,加部分积从被乘数移位到累加器当且仅当在乘法器对应的位被设置。移位被乘数和乘数在循环的结束,检测乘数1,以查看是否此外应该这样做。
Microchip的PICmicro 16Fxxx系列芯片不具有乘法或除法指令。 也许有些乘法软软除法例程它可以移植到你的MCU。
还检查了 “牛顿法” 为除法一>。 我认为方法使我见过的任何除法算法的最小的可执行文件的大小,虽然解释使得它听起来复杂得多它确实是。 我听到一些早期Cray超级使用牛顿法用于除法。