我正在研究一种没有硬件乘法和除法的微控制器。 我需要为这些基本操作制作软件算法,这是紧凑尺寸和效率的良好平衡。 我的C编译器端口将使用这些算法,而不是C开发人员自己。
我的google-fu到目前为止主要是关于这个主题的噪音。
谁能指点我的信息? 我可以使用add / sub和shift指令。 基于表查找的算法也可能对我有用,但我有点担心编译器的后端这么多……嗯,可以这么说。
这是一个简单的乘法算法:
这是一个除法算法:
当然你需要把支票除以0,但它应该有效。
当然,这些算法仅适用于整数。
这是我最喜欢的参考资料,有书本forms:
你也不会错过TAoCP: http ://www-cs-faculty.stanford.edu/~uno/taocp.html
这是一个除法算法: http : //www.prasannatech.net/2009/01/division-without-division-operator_24.html
我假设我们正在谈论整数?
如果没有硬件支持,则必须实现自己的除零exception。
(我很快就找到了一个乘法算法,但我会一直在寻找其他人找不到的算法)。
一个简单且相当高效的整数乘法算法是俄罗斯农民增殖 。
对于有理数,您可以尝试使用二进制引号表示法 ,因为它比平常更容易划分。
事实certificate,我仍然有一些旧的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上。
PIC单片机基本数学乘法方法
PIC单片机基本数学分区方法
还可以查看“Newton’s method”进行划分 。 我认为该方法给出了我见过的任何除法算法的最小可执行大小,尽管这种解释使它听起来比实际上更复杂。 我听说一些早期的Cray超级计算机使用了牛顿的分割方法。
需要了解更多c/c++开发分享我在哪里可以找到软乘法和除法算法?,也可以关注C/ C++技术分享栏目---计算机技术网(www.ctvol.com)!
以上就是c/c++开发分享我在哪里可以找到软乘法和除法算法?相关内容,想了解更多C/C++开发(异常处理)及C/C++游戏开发关注计算机技术网(www.ctvol.com)!)。
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/979006.html