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

liangbch

回29楼，当然！

无心人

那，怎么说呢
我觉得为了一点速度的提高
有点不值吧

无心人

而且，2^32也可以一次加2^30个整数而不溢出啊

无心人

另外
有一个操作2^30基是无法高效的
就是x=x+1操作

liangbch

为了阅读方便，现将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
    
11. 
    
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]
    
16. 
    
17.         or  ecx,ecx
    
18.         jz thisExit
    
19. 
    
20. loop00:
    
21.         mov eax,[esi]
    
22.         adc eax,[edx]
    
23.         mov [edi],eax
    
24.        
    
25.         lea esi,[esi+4]
    
26.         lea edx,[edx+4]
    
27.         lea edi,[edi+4]
    
28.         dec ecx
    
29.         jnz loop00
    
30.        
    
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
    
13. 
    
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
    
18.                
    
19.                 pxor mm0,mm0
    
20.                 mov eax,ecx
    
21.                 shr ecx,2       
    
22.                 and eax,3
    
23.                 jz  a10
    
24. 
    
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
    
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
    
45.                
    
46.                 movd mm3, [esi+4]
    
47.                 movd mm4, [edi+4]
    
48.                 paddq mm3, mm4
    
49.                
    
50.                 movd mm5, [esi+8]
    
51.                 movd mm6, [edi+8]
    
52.                 paddq mm5, mm6
    
53.                
    
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
    
69.                
    
70.                 add esi, 16
    
71.                 add edi, 16
    
72.                 add ebx, 16
    
73.                 sub ecx,1
    
74.                 jne loop1
    
75. 
    
76. thisExit:
    
77.                
    
78.                 pop ebx
    
79.                 pop edi
    
80.                 pop esi
    
81.                
    
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
    
11. 
    
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]
    
16. 
    
17.         mov        eax,ecx
    
18.         shr ecx,3       
    
19.         and eax,7
    
20.         jz  a10
    
21. 
    
22.         push ecx
    
23.         mov  ecx,eax
    
24. 
    
25. loop00:
    
26.         mov eax,[esi]
    
27.         adc eax,[edx]
    
28.         mov [edi],eax
    
29.        
    
30.         lea esi,[esi+4]
    
31.         lea edx,[edx+4]
    
32.         lea edi,[edi+4]
    
33.         dec ecx
    
34.         jnz loop00
    
35.         pop ecx
    
36. 
    
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
    
47.        
    
48.         mov        eax,[esi+4]
    
49.         adc        eax,[edx+4]
    
50.         mov        [edi+4],eax
    
51.        
    
52.         mov        eax,[esi+8]
    
53.         adc        eax,[edx+8]
    
54.         mov        [edi+8],eax
    
55.        
    
56.         mov        eax,[esi+12]
    
57.         adc        eax,[edx+12]
    
58.         mov        [edi+12],eax
    
59. 
    
60.         mov        eax,[esi+16]
    
61.         adc        eax,[edx+16]
    
62.         mov        [edi+16],eax
    
63. 
    
64.         mov        eax,[esi+20]
    
65.         adc        eax,[edx+20]
    
66.         mov        [edi+20],eax
    
67. 
    
68.         mov        eax,[esi+24]
    
69.         adc        eax,[edx+24]
    
70.         mov        [edi+24],eax
    
71.        
    
72.         mov        eax,[esi+28]
    
73.         adc        eax,[edx+28]
    
74.         mov        [edi+28],eax
    
75. 
    
76.        
    
77.         lea esi,[esi+32]
    
78.         lea edx,[edx+32]
    
79.         lea edi,[edi+32]
    
80. 
    
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. }

复制代码

无心人

你还没回答我问题呢？
2^32的MMX版本也是可以多次加不进位的

X = X+1的2^30版本如何高效？

liangbch

// 接楼上,给出剩余的几个采用$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
    
14.        
    
15. 
    
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]
    
20. 
    
21.         xor        edx,edx        //clear carry
    
22.         or  ecx,ecx
    
23.         jz thisExit
    
24.        
    
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
    
38. 
    
39. thisExit:
    
40.        
    
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
    
15. 
    
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]
    
20. 
    
21.         lea eax,[esi+edx*4]
    
22.         mov [esp],eax
    
23. 
    
24.         xor ecx,ecx                //clear carry
    
25.         and edx,3
    
26.         jz  a10
    
27.        
    
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
    
43. 
    
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]
    
51.        
    
52.         add edx,ecx
    
53.         mov ecx,edx
    
54.         and edx,BASE30_MASK
    
55.         shr ecx,30
    
56.         mov [ebx],edx
    
57.        
    
58.         add eax,ecx
    
59.         mov ecx,eax
    
60.         and eax,BASE30_MASK
    
61.         shr ecx,30
    
62.         mov [ebx+4],eax
    
63. 
    
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]
    
69. 
    
70.         add edx,ecx
    
71.         mov ecx,edx
    
72.         and edx,BASE30_MASK
    
73.         shr ecx,30
    
74.         mov [ebx+8],edx
    
75.        
    
76.         add eax,ecx
    
77.         mov ecx,eax
    
78.         and eax,BASE30_MASK
    
79.         shr ecx,30
    
80.         mov [ebx+12],eax
    
81. 
    
82.         lea esi,[esi+16]
    
83.         lea edi,[edi+16]
    
84.         lea ebx,[ebx+16]
    
85. cmp00:
    
86.         cmp esi,[esp]
    
87.         jb loop01
    
88. 
    
89. thisExit:
    
90.         add esp,4
    
91.        
    
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
    
15. 
    
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]
    
20. 
    
21.         lea eax,[esi+edx*4]
    
22.         mov [esp],eax
    
23. 
    
24.         xor ecx,ecx
    
25.         and edx,7
    
26.         jz  a10
    
27.        
    
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
    
43. 
    
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]
    
51.        
    
52.         add edx,ecx
    
53.         mov ecx,edx
    
54.         and edx,BASE30_MASK
    
55.         shr ecx,30
    
56.         mov [ebx],edx
    
57.        
    
58.         add eax,ecx
    
59.         mov ecx,eax
    
60.         and eax,BASE30_MASK
    
61.         shr ecx,30
    
62.         mov [ebx+4],eax
    
63.        
    
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]
    
69.        
    
70.         add edx,ecx
    
71.         mov ecx,edx
    
72.         and edx,BASE30_MASK
    
73.         shr ecx,30
    
74.         mov [ebx+8],edx
    
75.        
    
76.         add eax,ecx
    
77.         mov ecx,eax
    
78.         and eax,BASE30_MASK
    
79.         shr ecx,30
    
80.         mov [ebx+12],eax
    
81. 
    
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]
    
87.        
    
88.         add edx,ecx
    
89.         mov ecx,edx
    
90.         and edx,BASE30_MASK
    
91.         shr ecx,30
    
92.         mov [ebx+16],edx
    
93.        
    
94.         add eax,ecx
    
95.         mov ecx,eax
    
96.         and eax,BASE30_MASK
    
97.         shr ecx,30
    
98.         mov [ebx+20],eax
    
99. 
    
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]
     
105.        
     
106.         add edx,ecx
     
107.         mov ecx,edx
     
108.         and edx,BASE30_MASK
     
109.         shr ecx,30
     
110.         mov [ebx+24],edx
     
111.        
     
112.         add eax,ecx
     
113.         mov ecx,eax
     
114.         and eax,BASE30_MASK
     
115.         shr ecx,30
     
116.         mov [ebx+28],eax
     
117. 
     
118.         lea esi,[esi+32]
     
119.         lea edi,[edi+32]
     
120.         lea ebx,[ebx+32]
     
121. cmp00:
     
122.         cmp esi,[esp]
     
123.         jb loop01
     
124. 
     
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
    
15. 
    
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
    
20.                
    
21.                 pxor mm0,mm0
    
22.                 mov  eax,BASE30_MASK
    
23.                 movd mm7,eax
    
24. 
    
25.                 mov eax,ecx
    
26.                 shr ecx,2       
    
27.                 and eax,3
    
28.                 jz  a10
    
29. 
    
30. loop0:
    
31.                 movd mm1, [esi]
    
32.                 movd mm2, [edi]
    
33.                 paddq mm0,  mm1
    
34.                 paddq mm0,  mm2
    
35.                
    
36.                 movq mm1, mm0
    
37.                 psrlq mm0, 30
    
38.                 pand mm1, mm7
    
39.                 movd [ebx],mm1
    
40.                
    
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
    
57.        
    
58.                 paddq        mm0,mm1
    
59.                 movq        mm3,mm0
    
60.                 psrlq        mm0,30
    
61.                 pand        mm3,mm7
    
62.                 movd        [ebx],mm3
    
63.        
    
64.                 paddq        mm0,mm2
    
65.                 movq        mm4,mm0
    
66.                 psrlq        mm0,30
    
67.                 pand        mm4,mm7
    
68.                 movd        [ebx+4],mm4
    
69. 
    
70.                 //calc [ebx+8] and [ebx+12]
    
71.                
    
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
    
78.                
    
79.                 paddq        mm0,mm1
    
80.                 movq        mm3,mm0
    
81.                 psrlq        mm0,30
    
82.                 pand        mm3,mm7
    
83.                 movd        [ebx+8],mm3
    
84.        
    
85.                 paddq        mm0,mm2
    
86.                 movq        mm4,mm0
    
87.                 psrlq        mm0,30
    
88.                 pand        mm4,mm7
    
89.                 movd        [ebx+12],mm4
    
90.                
    
91.                 add esi, 16
    
92.                 add edi, 16
    
93.                 add ebx, 16
    
94.                 sub ecx,1
    
95.                 jne loop1
    
96. 
    
97. thisExit:
    
98.                
    
99.                 pop ebx
    
100.                 pop edi
     
101.                 pop esi
     
102.                
     
103.                 movd eax,mm0
     
104.                 emms
     
105.                 ret
     
106.         }
     
107. }

复制代码

liangbch

1.

2^32的MMX版本也是可以多次加不进位的

我不带明白你指的是什么，是大数乘法还是大数加法。
如果是大数加法，使用ALU指令必然会进位。

我们不但要考虑MMX指令，更多的情况下，我们需要考虑ALU指令，我们不能假定我的程序总是运行在支持SSE2指令的计算机。我的程序应该自动侦测CPU，在任何386以上的CPU上运行。

2.对于大数x，计算x=x+1,并不是一个常用的操作，一般情况下，其复杂度为常数，不值得考虑。

无心人

哈
当然是加法了
就你说的 A+B+C+D
。。。。。。。。。。。。。。。。。。。。。。。。
2.对于大数x，计算x=x+1,并不是一个常用的操作，一般情况下，其复杂度为常数，不值得考虑。这个不是吧，在不等长的加法里是常见的操作啊

liangbch

在99.99999999...%的情况下，x=x+1，不会连续进位，所以我说是一个常数时间。