二进制32位整数快速平方根

gxqcn

今天运行了 liangbch 的测试程序， 发现我的程序经无心人汇编后速度反而下降了。 另讲个自己测试的笑话： 因为这几天有点忙，就将自己的代码简单测试了下， 由于原本是没加 __fastcall 限定的， 所以就单独写段代码测试（循环次数与其它的一样）。 但每次测试我的代码都只要“0 s”，所以感觉快得不可思议！ 现在才明白了，被编译器优化掉了，实际上根本就没去循环调用！ 不过若是写成函数指针形式，编译器就不会去过度优化了。

liangbch

贴上一份测试结果： CPU: AMD Sempron 2500+, 1.75MH, MMX,3DNow,SSE L1 Data :64K，L1 Code:64K L2 cache:256K RAM: 1248MB, 说明： 1. 参考函数为iSqt_ref，代码见下 DWORD __fastcall iSqrt_ref(DWORD n) { DWORD r=(DWORD)(sqrt(double(n))); return r; } 2. 测试时：取3次测试的最小值 测试结果 case 1,计算0-65535的平方根 1）iSqt_FPU1_lbc 最快，其次是iSqt_FPU2_lbc， 2）liangbch的两个C版本也排到了第3和第5. 这两个c版本和被开方数的bit数有关，被开方数越小，速度越快。 3）只有 iSqt_GxQ_asm 和 iSqt_16 的速度低于参考函数(iSqrt_ref), ISqrt最慢。 4）各个函数的实际速度为（按速度排序） iSqt_FPU1_lbc#: 0.00091 s iSqt_FPU2_lbc#: 0.00126 s iSqt_c1_lbc#: 0.00141 s iSqt_FPU_yaos#: 0.00182 s iSqt_c2_lbc#: 0.00184 s iSqt_FPU2_yaos#: 0.00185 s iSqt_FPU3_lbc#: 0.00192 s iSqt_gxq_c#: 0.00202 s iSqt_FPU1_yaos#: 0.00219 s Sqt_ref 0.00295 s （参考函数） iSqt_GxQ_asm#: 0.00336 s iSqt_16#: 0.00449 s 测试结果 case 2,计算0-2^28-1的平方根 1）iSqt_FPU1_lbc 最快，其次是iSqt_FPU2_lbc， 2）liangbch的两个C版本也这次排到了第8和第10. 3）iSqt_c1_lbc，iSqt_GxQ_asm 和 iSqt_16 的速度低于参考函数(iSqrt_ref), ISqrt_16依然是最慢的。 4）各个函数的实际速度为（按速度排序） iSqt_FPU1_lbc#: 3.82618 s iSqt_FPU2_lbc#: 5.32978 s iSqt_FPU_yaos#: 7.70527 s iSqt_FPU2_yaos#: 7.74564 s iSqt_FPU3_lbc#: 8.12494 s iSqt_gxq_c#: 8.43633 s iSqt_FPU1_yaos#: 9.19390 s iSqt_c2_lbc#: 11.06406 s iSqt_ref#: 12.36054 s (参考函数） iSqt_c1_lbc#: 12.53915 s iSqt_GxQ_asm#: 14.09524 s iSqt_16#: 19.85911 s

无心人

GxQ 我的优化汇编在我的机器上是比你C快的啊 只能说你的U不好 哈哈

gxqcn

我昨天试着写汇编，每个 SQRT_CORE 展开可比你的少3条指令。 等我有空时调试好了再帖上来吧。 我是个对整型算法痴迷的追求者， 大家看看纯用ALU指令可否再提速？

无心人

我也是觉得11条太多 期待你的程序 因为我还没完全看懂那个算法 所以只能照搬C逻辑 而不能重新写汇编

无心人

Core 2 XEON 1.6G 1024M n: 0-0x10000 iSqt_ref#: 0.00860 s iSqt_c1_lbc#: 0.00802 s iSqt_c2_lbc#: 0.01004 s iSqt_FPU1_lbc#: 0.00235 s iSqt_FPU2_lbc#: 0.00235 s iSqt_FPU3_lbc#: 0.00235 s iSqt_FPU_yaos#: 0.00246 s iSqt_FPU1_yaos#: 0.00248 s iSqt_FPU2_yaos#: 0.00235 s iSqt_gxq_c#: 0.00859 s iSqt_GxQ_asm#: 0.00517 s iSqt_16#: 0.01793 s n: 0-0x10000000 iSqt_ref#: 35.64516 s iSqt_c1_lbc#: 38.43555 s iSqt_c2_lbc#: 54.55676 s iSqt_FPU1_lbc#: 9.76307 s iSqt_FPU2_lbc#: 9.77639 s iSqt_FPU3_lbc#: 9.78283 s iSqt_FPU_yaos#: 10.10670 s iSqt_FPU1_yaos#: 10.29507 s iSqt_FPU2_yaos#: 9.81197 s iSqt_gxq_c#: 38.91645 s iSqt_GxQ_asm#: 21.45924 s iSqt_16#: 80.26027 s

无心人

宝宝的1，2，3都看了 1、不能说好，因为受RC控制，且这个函数将来被用在RC失控的地方就会出错 2、和我的逻辑一样，唯一不同是存在跳转，呵呵，看来宝宝的汇编功力比我的强 有时间改写下这个函数，可能会有更好的速度 3、这么利用esp不知道好不好，总觉得存在问题，怎么不增加2个处理esp的语句？

无心人

GxQ的算法如果首次循环从bsr扫描到的位置启动 是否对小数字会比较好

无心人

另外 宝宝的测试并不完善 在2^31-1以上才存在修正呢 我想测试2100000000-2200000000比较妥当

liangbch

3、这么利用esp不知道好不好，总觉得存在问题，怎么不增加2个处理esp的语句？

在单线程应该不会存在问题，在多线程的情况下我就不知道了。 如果多线程的各个栈是独立的则应该不会有问题，否则，可能会出现问题。