【非典】32 bits BIN2BCD "二百五”算法 (164 bytes 341 周期)

2万 · 2011-10-8 15:13

估计早忘了。

1万 · 2011-10-8 19:02

花了2个多小时，将邓苗老师的 250算法吃透~~~

邓苗老师的 250算法真是天才之作，构思如此巧妙，如同上帝鬼斧神工之作，俺第一次看到，看的很累，但看完后，感觉思路一下子开扩许多，心旷神怡，又上了一台阶~~~

谢谢邓苗老师~~~

1万 · 2011-10-9 08:18

花了2个多小时，将邓苗老师的 250算法吃透~~~

邓苗老师的 250算法真是天才之作，构思如此巧妙，如同上帝鬼斧神工之作，俺第一次看到，看的很累，但看完后，感觉思路一下子开扩许多，心旷神怡，又上了一台阶~~~

谢 ...
Cortex-M0 发表于 2011-10-8 19:02

测试一下,看看结果是否正确

1万 · 2011-10-9 08:54

俺测试过，算法巧妙，结果完全正确~~~ :victory:

1万 · 2011-10-9 09:07

俺测试过，算法巧妙，结果完全正确~~~ :victory:
Cortex-M0 发表于 2011-10-9 08:54

我用顶楼的程序枚举输入测试,大批的结果错误

1万 · 2011-10-9 11:29

LZ
你的程序不知道测试过没有啊,结果错的,再快也没有用啊
输入1234567890结果正确
输入250结果错误,后面输入结果大排的错误
ayb_ice 发表于 2011-10-8 13:20

无论输入任何数，邓喵老师的程序运行结果都正确~~~

何以大排错误之说？

无图无真相，墙裂要求上片片~~~

只看该作者 · 2011-10-9 12:35

本帖最后由 DownCloud 于 2011-10-10 18:46 编辑

2字节数B15,B14..B0=(B15B14..B8)*256+(B9B8..B0)
除以250就可以较快速的通过移位算出来，此方法可以推广到除以一个靠近256，512，1024。。。等常数的算法
;下面给一个自己写的特殊算式
;计算的范围为：1×1×1/1000~9999×127×51/1000
;入口：（R45 R1 R2）出口：R67
;--------------------------------------------------------------------------
;黄，20110120
;    优化，20110126
;T=175..211(3 Loops)
;方法：2字节数B15,B14..B0=(B15B14..B10)*2^10+(B9B8..B0)=(B15B14..B10)*1024+(B9B8..B0)
;=(B15B14..B10)*1000+(B15B14..B10)*24+(B9B8..B0)
;除以1000后＝(B15B14..B10)+((B15B14..B10)*24+(B9B8..B0))/1000=(B15B14..B10)
;--------------------------------------------------------------------------
Huan1:    Acall  R45Div1KC0    ;R3:=R45 Div 1000, R45:=R45 Mod 1000
         Mov B,R1          ;R45:=R45*R1
         Mul AB
         Xch A,R5
         Mov B,R1
         Mul AB
         Xch A,R5
         Add A,B
         Mov R4,A
         Mov A,R3          ;R67:=R3*R1*R2
         Mov B,R1
         Mul AB
         Mov R3,B
         Mov B,R2
         Mul AB
         Mov R6,B
         Mov R7,A
         Mov A,R3
         Mov B,R2
         Mul AB
         Add A,R6
         Mov R6,A
         Acall  R45Div1K
         Mov A,R3          ;R67:+R3*R2
         Mov B,R2
         Mul AB
         Add A,R7
         Mov R7,A
         Mov A,B
         Addc A,R6
         Mov R6,A
         Mov A,R5          ;R45:+R45*R2
         Mov B,R2
         Mul AB
         Mov R5,A
         Mov A,R4
         Mov R4,B
         Mov B,R2
         Mul AB
         Add A,R4
         Mov R4,A
         Clr A
         Addc A,B
         Mov C,Acc.0       ;Highest Byte can only be 1 or 0, in C
         ACall  R45Div1K
         Mov A,R3          ;R67:+R3
         Add A,R7
         Mov R7,A
         Clr A
         Addc A,R6
         Mov R6,A

                              ;R45=(b15...b9)*500+(b15...b9)*12+(b8...b0)
         Mov A,#12       ;.R45:=R45+12
         Add A,R5
         Clr A
         Addc A,R4
         Rrc A             ;get (b15...b9)
         Jz    NoInc          ;(b15...b9) of R45 >0 then .R45>=512 then R45>=500
         Inc R7             ;R45>=500 then Inc R67
         Cjne R7,#0,NoInc
         Inc R6
NoInc:    Ret

;--------------------------------------------------------------------------
;R3:=R45 Div 1000, R45:=R45 Mod 1000
;=(B15B14..B10)*1000+(B15B14..B10)*24+(B9B8..B0)
;R45/1000=(B15B14..B10)+((B15B14..B10)*24+(B9B8..B0))/1000
;--------------------------------------------------------------------------
R45Div1KC0: Clr C             ;R3:=B15B14..B10 of R45
R45Div1K: Mov A,R4
         Rrc A
         Clr C
         Rrc A
         Mov R3,A
         Mov B,#(1024-1000) ;R45:=R45(B9B8..B0)+R3:*(1024-1000)
         Mul AB
         Add A,R5
         Mov R5,A
         Mov A,R4
         Anl A,#00000011B
         Addc A,B
R45Div1KLp: Mov R4,A
         Cjne A,#4,$+3    ;If B15B14..B10 of R45>0 then R45>1000
         Jc    R45Div1KQ
         Inc R3          ;R3:+1, R45:-1000
         Xch A,R5          ;C=0, For MaxR3(3F)*24+MaxR45(3FF)=9E7<10000H
         Subb A,#Low(1000)
         Xch A,R5
         Subb A,#High(1000)
         Sjmp R45Div1KLp    ;Tested Max 3 Loops, 20110126, at 4412*86*51
R45Div1KQ:  Ret

1万 · 2011-10-9 13:15

LS写的不错哈~~~

顶~~~~

1万 · 2011-10-9 14:06

有图有真相,错误的结果源代码全部复制LZ的顶楼代码,只是将测试输入改成250,后面还有大批的错误结果

1万 · 2011-10-9 14:22

直接上KEIL测试项目程序

1万 · 2011-10-9 15:14

恭喜ayb_ice，贺喜ayb_ice ~~~

邓喵老师思路非常严密，程序中难得有bug，结果偶然一次小小的笔误给ayb_ice逮着了~~~ :lol

ayb_ice只要将程序中的一个子程序，略为改动一下，修正bug,  即OK了~~~

SUB_R4_GE250:
   XCH A, R4
   ADD A, #6
   JC $+4
   SJMP  $+5
   INC R4
   SJMP  $+4
   ADD A, #250
   XCH A, R4
   RET

1万 · 2011-10-9 15:22

邓喵老师的“二百五”算法，是俺有生以来见过的最具有神奇特色的算法之一。

1万 · 2011-10-9 16:08

恭喜ayb_ice，贺喜ayb_ice ~~~

邓喵老师思路非常严密，程序中难得有bug，结果偶然一次小小的笔误给ayb_ice逮着了~~~ :lol

ayb_ice只要将程序中的一个子程序，略为改动一下，修正bug, 即OK了~~~

SUB_R4_GE250:
...
Cortex-M0 发表于 2011-10-9 15:14

我就是用最简单的枚举方法测试
我略微修改了一下程序,交换了一下寄存器的值,使与C参数传递兼容,然后在C里调用转换程序,自动检验测试结果,结果很快就杯具了,在250时出错,后面大批的结果出错,我怕自己修改错误,没有发C测试程序,为了找错误,直接用原始汇编程序测试结果一样出错,只能这样了
先别说修好了BUG
等我再测试一下再说

1万 · 2011-10-9 16:34

这回应该正确了,
32位枚举太费时间了,间隔1000完整测试了,没有问题

只看该作者 · 2011-10-9 16:48

LS写的不错哈~~~

顶~~~~
Cortex-M0 发表于 2011-10-9 13:15

通用性不好，只是创新一下帮他人完成项目里需要的一个算法（只比他原来程序快几到二十几周期，但精度完全保留了），所以数字都有些奇怪。
现在老师要求写浮点库，浮点数的数据格式还是他自己独创的，郁闷啊，纯汇编又没得参考，都不想写啊（这样学习其他的还来不及就死在研究汇编上了）。（但愿老师没上这个网啊）

1万 · 2011-10-9 18:04

本帖最后由 dengm 于 2011-10-9 18:28 编辑

RE: 50楼 Cortex-M0  大于等于250 这样改才是最好!!! 对不起, 因为该代码没有用于项目, 所以没有测试.
36楼才是最终代码!!

SUB_R4_GE250:
   XCH A, R4
   ADD A, #6
   ADD A, #250
   CPL C
   XCH A, R4
   RET

1万 · 2011-10-10 05:40

谢谢邓喵老师指点。

SUB_R4_GE250 子程序俺理解为判(R4值+6)是否有进位，即您说的是否大于等于250，如成立，返回（ACC值+1, R4值+6), 否则，原样返回，（ACC值, R4值）不变。

您 55楼的程序并不能保证上述功能，返回值，（ACC值, R4值）始终不变。

1万 · 2011-10-10 06:15

另：

最近在玩中颖的51,  由于中颖自带 16/8位除法，俺用中颖的除法指令做 BIN ---> BCD 转换，经测试，32位 BIN ---> BCD 转换，用时约 500个时钟周期，俺用您 36楼的“二百五”算法最终代码，用时约636个时钟周期，中颖是1T单片机，1个时钟周期为工作频率的倒数，对比之下，中颖用 16/8位除法做 BIN ---> BCD 转换，速度略为比“二百五”算法高一些。

俺用中颖的除法指令做 BIN ---> BCD 转换，经测试，16位 BIN ---> BCD 转换，用时约 130个时钟周期，俺用您另一个贴子的 16位 BIN ---> BCD 转换“非典”算法最终代码，用时约 121个时钟周期，还是您的“非典”算法厉害，快了近 10个时钟周期。

您的 16位 BIN ---> BCD 转换“非典”算法最终代码，在贴子：
https://bbs.21ic.com/viewthread.p ... ghlight=&page=2
21楼，您用标准51测试时，
;16 bits bin2bcd  52 周期
;32 bits bin2bcd  185 周期(算法暂时不公开)

俺斗胆问您讨个32位的 BIN ---> BCD 转换“非典”算法最终代码，程序和算法不公开没关系，您可以以库形式提供，谢谢。
邓喵老师的 32位的 BIN ---> BCD 转换“非典”算法程序建库要求：
1.  输入 32位BIN :    R4:R5:R6:R7 (高在先，以便和C51命名匹配，可直接赋值调用)
2.  输出 BCD码：（R3）:R4:R5:R6:R7 (高在先，以便和C51命名匹配，可直接使用返回值)
                        注：返回值中，最高位 R3可丢弃，因为C51 长整数变量只有 32位，用不上。
3.  程序名前请加下划线“_”,  以便 Keil C51能可靠传递参数，且注明公用函数调用性质。

谢谢邓喵老师~~~

1万 · 2011-10-10 08:48

将中颖自带 16/8位除法指令做的 32位 BIN ---> BCD 转换程序进行了优化处理，先除100, 余数再除10 (主要是中颖16/8位除法指令执行时间较长，要20个时钟周期，而中颖 8/8位除法指令只要 11个时钟周期), 以加快除法速度，结果并不是很理想，仅减少了 20几个时钟周期，再去掉原程序的限位（即不做32位BIN全范围转换，仅做最大8位BCD码范围之内的转换），经测试，32位 BIN ---> BCD 转换，用时约 400个时钟周期，无法再降低了~~~

期盼邓喵老师的 32 bits bin2bcd 185 周期 “非典”程序~~~

1万 · 2011-10-31 18:40

本帖最后由 dengm 于 2011-11-3 16:22 编辑

32 bits bin2bcd 最快可达 171周期 (不包括 CALL 及 RET)
给你提示: 131072 = 131 * 1000 + 72
131*128 = 16*1000 + 300H

【非典】32 bits BIN2BCD "二百五”算法 (164 bytes 341 周期)

技术奇才奖章

核心会员奖章

伴坛终老

湍急之河流

坚毅之洋流

七世轮回

技术高手奖章

社区建设奖章

以坛为家

欢快之小溪

荣誉元老奖章

十世金身

技术领袖奖章