数学研发网设为首页收藏本站
切换到窄版

 找回密码
 欢迎注册
数学研发论坛»论坛 › 【算法研发】 › 算法交流 › B计划之长加法最佳算法讨论
123456下一页
返回列表 发新帖
楼主: 无心人

[讨论] B计划之长加法最佳算法讨论

[复制链接]
liangbch
发表于 2008-4-16 15:22:46 | 显示全部楼层
回29楼，当然！
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

无心人
 楼主| 发表于 2008-4-16 15:30:59 | 显示全部楼层
那，怎么说呢 我觉得为了一点速度的提高 有点不值吧
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

无心人
 楼主| 发表于 2008-4-16 15:31:56 | 显示全部楼层
而且，2^32也可以一次加2^30个整数而不溢出啊
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

无心人
 楼主| 发表于 2008-4-16 15:35:51 | 显示全部楼层
另外 有一个操作2^30基是无法高效的 就是x=x+1操作
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

liangbch
发表于 2008-4-16 16:35:14 | 显示全部楼层
为了阅读方便，现将23楼附件中的2进制 大数加法的代码给出。 #define PARAM_SIZE 16 #define PARAM_SRC2 12 #define PARAM_SRC1 8 #define PARAM_DST 4 //1. 普通的加法，不使用循环展开
  1. _declspec(naked)
  2. DWORD binAdd_ALU(DWORD *dst,
  3. const DWORD *src1,
  4. const DWORD *src2,
  5. int size)
  6. {
  7. _asm
  8. {
  9. push edi
  10. push esi
  12. mov edi,[esp+8+PARAM_DST]
  13. mov esi,[esp+8+PARAM_SRC1]
  14. mov edx,[esp+8+PARAM_SRC2]
  15. mov ecx,[esp+8+PARAM_SIZE]
  17. or ecx,ecx
  18. jz thisExit
  20. loop00:
  21. mov eax,[esi]
  22. adc eax,[edx]
  23. mov [edi],eax
  25. lea esi,[esi+4]
  26. lea edx,[edx+4]
  27. lea edi,[edi+4]
  28. dec ecx
  29. jnz loop00
  31. thisExit:
  32. mov eax,0
  33. adc eax,0
  34. pop esi
  35. pop edi
  36. ret
  37. }
  38. }
复制代码
//使用4路循环展开的MMX版本 // 循环主题采用yaos的代码，(有bug,己经fix),liangbch加上了收尾部分和变量初始化部分 // 使用4路循环展开
  1. _declspec(naked)
  2. DWORD binAdd_Yaos_MMX_4way_unroll(DWORD *dst,
  3. const DWORD *src1,
  4. const DWORD *src2,
  5. int size)
  6. {
  7. #define STACK_FRAME 12
  8. _asm
  9. {
  10. push esi
  11. push edi
  12. push ebx
  14. mov ebx,dword ptr [esp+4+STACK_FRAME] //dst
  15. mov esi,dword ptr [esp+8+STACK_FRAME] //src1
  16. mov edi,dword ptr [esp+12+STACK_FRAME] //src2
  17. mov ecx,dword ptr [esp+16+STACK_FRAME] //size
  19. pxor mm0,mm0
  20. mov eax,ecx
  21. shr ecx,2
  22. and eax,3
  23. jz a10
  25. loop0:
  26. movd mm1, [esi]
  27. movd mm2, [edi]
  28. paddq mm0, mm1
  29. paddq mm0, mm2
  30. movd [ebx], mm0
  31. psrlq mm0, 32
  33. lea esi,[esi+4]
  34. lea edi,[edi+4]
  35. lea ebx,[ebx+4]
  36. dec eax
  37. jnz loop0
  38. a10:
  39. or ecx,ecx
  40. jz thisExit
  41. loop1:
  42. movd mm1, [esi]
  43. movd mm2, [edi]
  44. paddq mm1, mm2
  46. movd mm3, [esi+4]
  47. movd mm4, [edi+4]
  48. paddq mm3, mm4
  50. movd mm5, [esi+8]
  51. movd mm6, [edi+8]
  52. paddq mm5, mm6
  54. movd mm7, [esi+12]
  55. movd mm2, [edi+12]
  56. paddq mm7, mm2
  57. paddq mm0, mm1
  58. movd [ebx], mm0
  59. psrlq mm0, 32
  60. paddq mm0, mm3
  61. movd [ebx+4], mm0
  62. psrlq mm0, 32
  63. paddq mm0, mm5
  64. movd [ebx+8], mm0
  65. psrlq mm0, 32
  66. paddq mm0, mm7
  67. movd [ebx+12], mm0
  68. psrlq mm0, 32
  70. add esi, 16
  71. add edi, 16
  72. add ebx, 16
  73. sub ecx,1
  74. jne loop1
  76. thisExit:
  78. pop ebx
  79. pop edi
  80. pop esi
  82. movd eax,mm0
  83. emms
  84. ret
  85. }
  86. }
复制代码
//使用8路循环展开的ALU版本 /* 下面的代码由原始的GMP代码转译而来,限於对GMP的理解的限制， 部分代码不得不重写，GMP源代码请参见 aors_n.asm 使用8路循环展开 */
  1. _declspec(naked)
  2. DWORD binAdd_GMP_ALU_8way_unroll(DWORD *dst,
  3. const DWORD *src1,
  4. const DWORD *src2,
  5. int size)
  6. {
  7. _asm
  8. {
  9. push edi
  10. push esi
  12. mov edi,[esp+8+PARAM_DST]
  13. mov esi,[esp+8+PARAM_SRC1]
  14. mov edx,[esp+8+PARAM_SRC2]
  15. mov ecx,[esp+8+PARAM_SIZE]
  17. mov eax,ecx
  18. shr ecx,3
  19. and eax,7
  20. jz a10
  22. push ecx
  23. mov ecx,eax
  25. loop00:
  26. mov eax,[esi]
  27. adc eax,[edx]
  28. mov [edi],eax
  30. lea esi,[esi+4]
  31. lea edx,[edx+4]
  32. lea edi,[edi+4]
  33. dec ecx
  34. jnz loop00
  35. pop ecx
  37. a10:
  38. mov eax,0
  39. adc eax,0
  40. or ecx,ecx
  41. jz thisExit
  42. ALIGN 8
  43. loop01:
  44. mov eax,[esi]
  45. adc eax,[edx]
  46. mov [edi],eax
  48. mov eax,[esi+4]
  49. adc eax,[edx+4]
  50. mov [edi+4],eax
  52. mov eax,[esi+8]
  53. adc eax,[edx+8]
  54. mov [edi+8],eax
  56. mov eax,[esi+12]
  57. adc eax,[edx+12]
  58. mov [edi+12],eax
  60. mov eax,[esi+16]
  61. adc eax,[edx+16]
  62. mov [edi+16],eax
  64. mov eax,[esi+20]
  65. adc eax,[edx+20]
  66. mov [edi+20],eax
  68. mov eax,[esi+24]
  69. adc eax,[edx+24]
  70. mov [edi+24],eax
  72. mov eax,[esi+28]
  73. adc eax,[edx+28]
  74. mov [edi+28],eax
  77. lea esi,[esi+32]
  78. lea edx,[edx+32]
  79. lea edi,[edi+32]
  81. dec ecx
  82. jnz loop01
  83. mov eax,0
  84. adc eax,0
  85. thisExit:
  86. pop esi
  87. pop edi
  88. ret
  89. }
  90. }
复制代码
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

无心人
 楼主| 发表于 2008-4-16 16:39:54 | 显示全部楼层
你还没回答我问题呢？ 2^32的MMX版本也是可以多次加不进位的 X = X+1的2^30版本如何高效？
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

liangbch
发表于 2008-4-16 16:43:45 | 显示全部楼层
// 接楼上,给出剩余的几个采用$2^30$进制的大数加法的函数 //基为2^30的版本，不采用循环展开
  1. _declspec(naked)
  2. DWORD binAdd_base30_ALU(DWORD *dst,
  3. const DWORD *src1,
  4. const DWORD *src2,
  5. int size)
  6. {
  7. #undef BASE30_MASK
  8. #define BASE30_MASK 0x3fffffff
  9. _asm
  10. {
  11. push edi
  12. push esi
  13. push ebx
  16. mov ebx,[esp+12+PARAM_DST]
  17. mov esi,[esp+12+PARAM_SRC1]
  18. mov edi,[esp+12+PARAM_SRC2]
  19. mov ecx,[esp+12+PARAM_SIZE]
  21. xor edx,edx //clear carry
  22. or ecx,ecx
  23. jz thisExit
  25. loop00:
  26. mov eax,[esi]
  27. add eax,[edi]
  28. add eax,edx
  29. mov edx,eax
  30. and eax,BASE30_MASK
  31. shr edx,30
  32. mov [ebx],eax
  33. lea esi,[esi+4]
  34. lea edi,[edi+4]
  35. lea ebx,[ebx+4]
  36. dec ecx
  37. jnz loop00
  39. thisExit:
  41. pop ebx
  42. pop esi
  43. pop edi
  44. mov eax,0
  45. adc eax,0
  46. ret
  47. }
  48. }
复制代码
//基为2^30的版本，采用4路循环展开
  1. _declspec(naked)
  2. DWORD binAdd_base30_ALU_4way_unroll(DWORD *dst,
  3. const DWORD *src1,
  4. const DWORD *src2,
  5. int size)
  6. {
  7. #undef BASE30_MASK
  8. #define BASE30_MASK 0x3fffffff
  9. _asm
  10. {
  11. push edi
  12. push esi
  13. push ebx
  14. sub esp,4
  16. mov ebx,[esp+16+PARAM_DST]
  17. mov esi,[esp+16+PARAM_SRC1]
  18. mov edi,[esp+16+PARAM_SRC2]
  19. mov edx,[esp+16+PARAM_SIZE]
  21. lea eax,[esi+edx*4]
  22. mov [esp],eax
  24. xor ecx,ecx //clear carry
  25. and edx,3
  26. jz a10
  28. loop00:
  29. mov eax,[esi]
  30. add eax,[edi]
  31. add eax,ecx
  32. mov ecx,eax
  33. and eax,BASE30_MASK
  34. shr ecx,30
  35. mov [ebx],eax
  36. lea esi,[esi+4]
  37. lea edi,[edi+4]
  38. lea ebx,[ebx+4]
  39. dec edx
  40. jnz loop00
  41. a10:
  42. jmp cmp00
  44. ALIGN 8
  45. loop01:
  46. //calc [ebx] and [ebx+4]
  47. mov edx,[esi]
  48. mov eax,[esi+4]
  49. add edx,[edi]
  50. add eax,[edi+4]
  52. add edx,ecx
  53. mov ecx,edx
  54. and edx,BASE30_MASK
  55. shr ecx,30
  56. mov [ebx],edx
  58. add eax,ecx
  59. mov ecx,eax
  60. and eax,BASE30_MASK
  61. shr ecx,30
  62. mov [ebx+4],eax
  64. //calc [ebx+8] and [ebx+12]
  65. mov edx,[esi+8]
  66. mov eax,[esi+12]
  67. add edx,[edi+8]
  68. add eax,[edi+12]
  70. add edx,ecx
  71. mov ecx,edx
  72. and edx,BASE30_MASK
  73. shr ecx,30
  74. mov [ebx+8],edx
  76. add eax,ecx
  77. mov ecx,eax
  78. and eax,BASE30_MASK
  79. shr ecx,30
  80. mov [ebx+12],eax
  82. lea esi,[esi+16]
  83. lea edi,[edi+16]
  84. lea ebx,[ebx+16]
  85. cmp00:
  86. cmp esi,[esp]
  87. jb loop01
  89. thisExit:
  90. add esp,4
  92. pop ebx
  93. pop esi
  94. pop edi
  95. mov eax,0
  96. adc eax,0
  97. ret
  98. }
  99. }
复制代码
//基为2^30的版本，采用8路循环展开
  1. _declspec(naked)
  2. DWORD binAdd_base30_ALU_8way_unroll(DWORD *dst,
  3. const DWORD *src1,
  4. const DWORD *src2,
  5. int size)
  6. {
  7. #undef BASE30_MASK
  8. #define BASE30_MASK 0x3fffffff
  9. _asm
  10. {
  11. push edi
  12. push esi
  13. push ebx
  14. sub esp,4
  16. mov ebx,[esp+16+PARAM_DST]
  17. mov esi,[esp+16+PARAM_SRC1]
  18. mov edi,[esp+16+PARAM_SRC2]
  19. mov edx,[esp+16+PARAM_SIZE]
  21. lea eax,[esi+edx*4]
  22. mov [esp],eax
  24. xor ecx,ecx
  25. and edx,7
  26. jz a10
  28. loop00:
  29. mov eax,[esi]
  30. add eax,[edi]
  31. add eax,ecx
  32. mov ecx,eax
  33. and eax,BASE30_MASK
  34. shr ecx,30
  35. mov [ebx],eax
  36. lea esi,[esi+4]
  37. lea edi,[edi+4]
  38. lea ebx,[ebx+4]
  39. dec edx
  40. jnz loop00
  41. a10:
  42. jmp cmp00
  44. ALIGN 8
  45. loop01:
  46. //calc [ebx] and [ebx+4]
  47. mov edx,[esi]
  48. mov eax,[esi+4]
  49. add edx,[edi]
  50. add eax,[edi+4]
  52. add edx,ecx
  53. mov ecx,edx
  54. and edx,BASE30_MASK
  55. shr ecx,30
  56. mov [ebx],edx
  58. add eax,ecx
  59. mov ecx,eax
  60. and eax,BASE30_MASK
  61. shr ecx,30
  62. mov [ebx+4],eax
  64. //calc [ebx+8] and [ebx+12]
  65. mov edx,[esi+8]
  66. mov eax,[esi+12]
  67. add edx,[edi+8]
  68. add eax,[edi+12]
  70. add edx,ecx
  71. mov ecx,edx
  72. and edx,BASE30_MASK
  73. shr ecx,30
  74. mov [ebx+8],edx
  76. add eax,ecx
  77. mov ecx,eax
  78. and eax,BASE30_MASK
  79. shr ecx,30
  80. mov [ebx+12],eax
  82. //calc [ebx+16] and [ebx+20]
  83. mov edx,[esi+16]
  84. mov eax,[esi+20]
  85. add edx,[edi+16]
  86. add eax,[edi+20]
  88. add edx,ecx
  89. mov ecx,edx
  90. and edx,BASE30_MASK
  91. shr ecx,30
  92. mov [ebx+16],edx
  94. add eax,ecx
  95. mov ecx,eax
  96. and eax,BASE30_MASK
  97. shr ecx,30
  98. mov [ebx+20],eax
  100. //calc [ebx+24] and [ebx+28]
  101. mov edx,[esi+24]
  102. mov eax,[esi+28]
  103. add edx,[edi+24]
  104. add eax,[edi+28]
  106. add edx,ecx
  107. mov ecx,edx
  108. and edx,BASE30_MASK
  109. shr ecx,30
  110. mov [ebx+24],edx
  112. add eax,ecx
  113. mov ecx,eax
  114. and eax,BASE30_MASK
  115. shr ecx,30
  116. mov [ebx+28],eax
  118. lea esi,[esi+32]
  119. lea edi,[edi+32]
  120. lea ebx,[ebx+32]
  121. cmp00:
  122. cmp esi,[esp]
  123. jb loop01
  125. thisExit:
  126. add esp,4
  127. pop ebx
  128. pop esi
  129. pop edi
  130. mov eax,0
  131. adc eax,0
  132. ret
  133. }
  134. }
复制代码
// 使用4路循环展开
  1. _declspec(naked)
  2. DWORD binAdd_Base30_MMX_4way_unroll(DWORD *dst,
  3. const DWORD *src1,
  4. const DWORD *src2,
  5. int size)
  6. {
  7. #define STACK_FRAME 12
  8. #undef BASE30_MASK
  9. #define BASE30_MASK 0x3fffffff
  10. _asm
  11. {
  12. push esi
  13. push edi
  14. push ebx
  16. mov ebx,dword ptr [esp+4+STACK_FRAME] //dst
  17. mov esi,dword ptr [esp+8+STACK_FRAME] //src1
  18. mov edi,dword ptr [esp+12+STACK_FRAME] //src2
  19. mov ecx,dword ptr [esp+16+STACK_FRAME] //size
  21. pxor mm0,mm0
  22. mov eax,BASE30_MASK
  23. movd mm7,eax
  25. mov eax,ecx
  26. shr ecx,2
  27. and eax,3
  28. jz a10
  30. loop0:
  31. movd mm1, [esi]
  32. movd mm2, [edi]
  33. paddq mm0, mm1
  34. paddq mm0, mm2
  36. movq mm1, mm0
  37. psrlq mm0, 30
  38. pand mm1, mm7
  39. movd [ebx],mm1
  41. lea esi,[esi+4]
  42. lea edi,[edi+4]
  43. lea ebx,[ebx+4]
  44. dec eax
  45. jnz loop0
  46. a10:
  47. or ecx,ecx
  48. jz thisExit
  49. loop1:
  50. //calc [ebx] and [ebx+4]
  51. movd mm1,[esi]
  52. movd mm3,[edi]
  53. movd mm2,[esi+4]
  54. movd mm4,[edi+4]
  55. paddq mm1,mm3
  56. paddq mm2,mm4
  58. paddq mm0,mm1
  59. movq mm3,mm0
  60. psrlq mm0,30
  61. pand mm3,mm7
  62. movd [ebx],mm3
  64. paddq mm0,mm2
  65. movq mm4,mm0
  66. psrlq mm0,30
  67. pand mm4,mm7
  68. movd [ebx+4],mm4
  70. //calc [ebx+8] and [ebx+12]
  72. movd mm1,[esi+8]
  73. movd mm3,[edi+8]
  74. movd mm2,[esi+12]
  75. movd mm4,[edi+12]
  76. paddq mm1,mm3
  77. paddq mm2,mm4
  79. paddq mm0,mm1
  80. movq mm3,mm0
  81. psrlq mm0,30
  82. pand mm3,mm7
  83. movd [ebx+8],mm3
  85. paddq mm0,mm2
  86. movq mm4,mm0
  87. psrlq mm0,30
  88. pand mm4,mm7
  89. movd [ebx+12],mm4
  91. add esi, 16
  92. add edi, 16
  93. add ebx, 16
  94. sub ecx,1
  95. jne loop1
  97. thisExit:
  99. pop ebx
  100. pop edi
  101. pop esi
  103. movd eax,mm0
  104. emms
  105. ret
  106. }
  107. }
复制代码
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

liangbch
发表于 2008-4-16 17:01:23 | 显示全部楼层
1.
2^32的MMX版本也是可以多次加不进位的
我不带明白你指的是什么，是大数乘法还是大数加法。 如果是大数加法，使用ALU指令必然会进位。 我们不但要考虑MMX指令，更多的情况下，我们需要考虑ALU指令，我们不能假定我的程序总是运行在支持SSE2指令的计算机。我的程序应该自动侦测CPU，在任何386以上的CPU上运行。 2.对于大数x，计算x=x+1,并不是一个常用的操作，一般情况下，其复杂度为常数，不值得考虑。
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

无心人
 楼主| 发表于 2008-4-16 17:04:17 | 显示全部楼层
哈 当然是加法了 就你说的 A+B+C+D 。。。。。。。。。。。。。。。。。。。。。。。。 2.对于大数x，计算x=x+1,并不是一个常用的操作，一般情况下，其复杂度为常数，不值得考虑。这个不是吧，在不等长的加法里是常见的操作啊
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

liangbch
发表于 2008-4-16 17:07:01 | 显示全部楼层
在99.99999999...%的情况下，x=x+1，不会连续进位，所以我说是一个常数时间。
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

123456下一页
返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2024-11-15 10:16 , Processed in 0.026309 second(s), 15 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

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