找回密码
 欢迎注册
查看: 13498|回复: 11

[擂台] 整数开根号果真慢过浮点?

[复制链接]
发表于 2014-7-1 07:18:27 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有账号?欢迎注册

×
  1. org 100h
  2. mov esi,0xfffffff
  3. ee:
  4. lea eax,[esi+$80000000]
  5. cvtsi2sd xmm0,eax
  6. addsd xmm0,[yy]
  7. sqrtsd xmm1,xmm0
  8. cvttsd2si eax,xmm1
  9. dec esi
  10. jnz ee
  11. ret
  12. db $1e8-$ dup 0
  13. yy:
  14. dq 2147483648.0
复制代码

时间2.6s

http://bbs.emath.ac.cn/thread-1207-2-1.html好像都更慢,有更快的吗
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2014-7-1 07:24:29 | 显示全部楼层
至1fffffff是4.84
至fffffffff是37.08
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2014-7-1 07:30:36 | 显示全部楼层
空转2^32 = 3.83
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2014-7-1 08:15:44 | 显示全部楼层
更严重的是

  1. //这个程序计算从1到0xFFFFFFFF的所有数的平方根,并全部打印
  2. #include <stdio.h>
  3. #include <stdlib.h>

  4. int main(int argc, char** argv)
  5. {
  6.     register unsigned int num = 1;
  7.     register unsigned int root = 1;
  8.     register unsigned int square = 0;


  9.     for( ; ; root++)
  10.     {
  11.         square += root << 1;
  12.         square--;

  13.         for( ; ; )
  14.         {
  15.             if(num == square)
  16.             {
  17. #ifdef __DEBUG__
  18.                 printf("square root of %d is %d\n", num, root);
  19. #endif
  20.                 num++;
  21.                 break;
  22.             }

  23. #ifdef __DEBUG__                        
  24.             printf("square root of %d is %d\n", num, root-1);
  25. #endif                        
  26.             num++;

  27.             if(num == 0xFFFFFFFF)
  28.             {
  29.                 return 0;
  30.             }
  31.         }
  32.     }

  33.     return 0;
  34. }
复制代码


  1. org 100h
  2. xor eax,eax
  3. xor ecx,ecx
  4. xor edx,edx
  5. s1:
  6. lea edx,[eax+eax+1]
  7. s2:
  8. ;do
  9. inc eax
  10. dec edx
  11. jnz s2
  12. inc cx
  13. jnz s1
  14. ret            
复制代码

跑了一分多钟(接近2)没结果
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2014-7-1 08:18:21 | 显示全部楼层
  1. org 100h
  2. xor eax,eax
  3. xor ecx,ecx
  4. xor edx,edx
  5. s1:
  6. lea edx,[ecx*2+1]
  7. s2:
  8. ;do
  9. inc eax
  10. dec edx
  11. jnz s2
  12. inc cx
  13. jnz s1
  14. ret            
复制代码
是3.78,上一层楼的不对
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2014-7-2 07:56:28 | 显示全部楼层
平方根算法主要有牛顿迭代法、二分查找法,对于整型来说,还有一种“移位相减”的硬件算法。

对于计算机来说,要看运行的平台,比如 CPU 支持哪些指令集,以及相关指令的时钟数;
还要看需求,比如说,是否短时间内反复调用?cache 是否对其有影响?
另外,对于某些特殊范围的入参,还可以有更快的版本,比如说,对于 \(\text{4 ~ 15}\) 内的 \(n\),用 \((n+15)\gg3\) 即可快速获取其平方根。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2014-7-3 11:06:09 | 显示全部楼层
1楼的程序核心部分使用了SSE2指令SQRTSD,这条指令属于浮点指令,和普通的浮点指令比,SSE2指令的操作数在MMX或者XMM中,而普通浮点指令的操作数在浮点数栈中进行。

下面列出这段代码中使用的几条SSE2指令。

cvtsi2sd:
   Convert Dword Integer to Scalar Double-Precision FP Value
ADDSD:
    Add Scalar Double-Precision Floating-Point Values
CVTTSD2SI:
   Convert with Truncation Scalar Double-Precision FP Value to Signed Integer
SQRTSD:
   Compute Square Root of Scalar Double-Precision Floating-Point Value
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2014-7-3 11:22:47 | 显示全部楼层
liangbch 发表于 2014-7-3 11:06
1楼的程序核心部分使用了SSE2指令SQRTSD,这条指令属于浮点指令,和普通的浮点指令比,SSE2指令的操作数在M ...

程序是我写的,这个我懂(当然作为补充也无妨)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2014-7-3 11:24:55 | 显示全部楼层
liangbch 发表于 2014-7-3 11:06
1楼的程序核心部分使用了SSE2指令SQRTSD,这条指令属于浮点指令,和普通的浮点指令比,SSE2指令的操作数在M ...

不过你如果能分析lea和add的妙处那最好
  1. lea eax,[esi+$80000000]
  2. cvtsi2sd xmm0,eax
  3. addsd xmm0,[yy];2147483648.0
复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2014-7-3 13:21:06 | 显示全部楼层
l4m2 发表于 2014-7-3 11:24
不过你如果能分析lea和add的妙处那最好

这又什么难以理解的?
  cvtsi2sd 要求源操作数是带符号数,故当操作数>=$2^31$, cvtsi2sd不能按预期的方式工作。代码“lea eax,[esi+80000000]”将被开方数减去$2^31$,转化为浮点数后,使用代码“addsd xmm0,[yy]" 又加上$2^31$来恢复到原始值。这样,当被开方数大于$2^31$时,也能工作了。

点评

我看上一个没人这么做,都用判断负,+2^32  发表于 2014-7-3 19:10
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-3-29 00:21 , Processed in 0.045948 second(s), 17 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表