移位相减除法升级思路验证
汇编吧
全部回复
仅看楼主
level 1
F_U_C_K_S_HIT 楼主
移位相减是解决CPU内部除法器不支持除法位数的好方法,我在网上搜索了许多资料,发现全部的移位相减除法都是以1为步进不断移动被除数来和除数相比较,能减则减,随后商加一。
我写过这样的算法,但是发现速度太慢了,所以需要找的合适的方法加速。
就比如说这个,一般的移位相减除法是一次只试出一位商,多少位商是多少次。而现在许多CPU虽然有除法器不支持你的数据长度,但好歹有呀,不用除法指令集加速实在太浪费了!
这是我遇到的实际问题:为了解决浮点数的除法运算问题,核心是编写53位除53位并得到包括小数的53位结果的除法。不幸的是,我的Cortex-M3平台只有32位除法器及其指令集UDIV/SDIV,是达不到要求的。所以我打算用移位相减算法实现这个53位除法,并且用除法指令进行试商,一次试出9位商。但是这个算法我也不好保证一定对,这是粗略的理论推导和个别的随机样例看起来没问题。
输入: 除数 [R3,R2],其中除数的第52位一定为1,位宽总是53位;
被除数 [R1,R0],其中被除数的第52位一定为1,位宽总是53位;
结果 [R1,R0],1位整数和54位小数。
算法如下:
2018年12月26日 13点12分 1
level 1
F_U_C_K_S_HIT 楼主
这是一般移位相减,相互印证:
2018年12月26日 13点12分 2
level 1
F_U_C_K_S_HIT 楼主
核心思路就是通过适当截尾使得53位数据能被32位除法器处理,而又不影响一定位数的结果。
我是先将被除数左移11位使得最高位63位是1,然后左移除数2位,这样被除数与除数相差9位,直接除会得到9-10位结果,随后把商乘以除数后与被除数相减,完成一次试商。随后每一次都把被除数左移9位然后得到商在相减,重复多次。
这里我把被除数和除数的低32位丢弃,然后直接用32位除法指令运算,理论上应该和直接除结果一样。
2018年12月26日 13点12分 3
level 3
厉害
2018年12月30日 02点12分 4
1