分治法的思路一般的算法教科书上都有，大数相乘也经常用来作为练习分治思想的很好的例子。

具体如下：

image

虽然上面的原理是对应2进制的，但是对于10进制也同样可行。

745F289E368648A38856C963432419F4

用C#实现，尽可能的利用C#的特性。本例中，只要拆分的数字小于9位数，就可以直接相乘计算，保证不会溢出。

在编程中，还需要用的加法和减法，也要通过字符串模拟实现。

最终的乘法运算，依赖递归思想得以实现。

本文的代码还有一些可以优化的地方，比如对于不使用字符串而是全部使用数组，可能会更快点。

代码如下：


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
namespace  bigIntMultiply
{
     class  Program
     {
         static  void  Main( string [] args)
         {
            string  a =  "99999999999999" ;
            string  b =  "123456789001234567890" ;
             Stopwatch sw =  new  Stopwatch();
             sw.Start();
             string  s = Multiply(b, b);
             sw.Stop();
             Console.WriteLine(s);
             Console.WriteLine(sw.Elapsed);
         }
         //字符串模拟乘法操作
         static  string  Multiply( string  x,  string  y)
         {
             //deep++;// Console.WriteLine("-" + deep + "-");
             string  negative =  "" ;
             if  ((x.StartsWith( "-" ) && y.StartsWith( "-" )) || (!x.StartsWith( "-" ) && !y.StartsWith( "-" )))
             {
                 x = x.TrimStart( '-' ); y = y.TrimStart( '-' );
                 negative =  "" ;
             }
             else  if  ((x.StartsWith( "-" ) && !y.StartsWith( "-" )) || (!x.StartsWith( "-" ) && y.StartsWith( "-" )))
             {
                 x = x.TrimStart( '-' ); y = y.TrimStart( '-' );
                 negative =  "-" ;
             }
             //如果长度都小于9，直接相乘，返回就行了。
             if  (x.Length <= 9 && y.Length <= 9)
             {
                 long  tmp = ( long .Parse(x) *  long .Parse(y));
                 if  (tmp == 0)
                     return  tmp.ToString();
                 return  negative + ( long .Parse(x) *  long .Parse(y)).ToString();
             }
             //公式里的abcd
             string  a, b, c, d;
             if  (x.Length <= 9)
             {
                 a =  "0" ; b = x;
             }
             else
             {
                 if  (x.Length % 2 != 0)
                     x =  "0"  + x;
                 a = x.Substring(0, x.Length / 2);
                 b = x.Substring(x.Length / 2);
             }
             if  (y.Length <= 9)
             {
                 c =  "0" ;
                 d = y;
             }
             else
             {
                 if  (y.Length % 2 != 0)
                     y =  "0"  + y;
                 c = y.Substring(0, y.Length / 2);
                 d = y.Substring(y.Length / 2);
             }
             int  n = x.Length >= y.Length ? x.Length : y.Length;
             string  t1, t2, t3;
             //递归调用，根据公式计算出值。
             string  ac = Multiply(a, c);
             string  bd = Multiply(b, d);
             t1 = Multiply(Subtract(a, b), Subtract(d, c));
             t2 = Add(Add(t1, ac), bd);
             t3 = Add(Add(Power10(ac, n), Power10(t2, n / 2)), bd).TrimStart( '0' );
             if  (t3 ==  "" )  return  "0" ;
             return  negative + t3;
         }
         //字符串模拟加法操作
         static  string  Add( string  x,  string  y)
         {
             if  (x.StartsWith( "-" ) && !y.StartsWith( "-" ))
             {
                 return  Subtract(y, x.TrimStart( '-' ));
             }
             else  if  (!x.StartsWith( "-" ) && y.StartsWith( "-" ))
             {
                 return  Subtract(x, y.TrimStart( '-' ));
             }
             else  if  (x.StartsWith( "-" ) && y.StartsWith( "-" ))
             {
                 return  "-"  + Add(x.TrimStart( '-' ), y.TrimStart( '-' ));
             }
             if  (x.Length > y.Length)
             {
                 y = y.PadLeft(x.Length,  '0' );
             }
             else
             {
                 x = x.PadLeft(y.Length,  '0' );
             }
             int [] sum =  new  int [x.Length + 1];
             for  ( int  i = x.Length - 1; i >= 0; i--)
             {
                 int  tmpsum =  int .Parse(x[i].ToString()) +  int .Parse(y[i].ToString()) + sum[i + 1];
                 if  (tmpsum >= 10)
                 {
                     sum[i + 1] = tmpsum - 10;
                     sum[i] = 1; //表示进位
                 }
                 else
                 {
                     sum[i + 1] = tmpsum;
                 }
             }
             string  returnvalue =  string .Concat(sum);
             if  (sum[0] == 1)
             {
                 return  returnvalue;
             }
             else
             {
                 return  returnvalue.Remove(0, 1);
             }
         }
         //字符串模拟减法操作
         static  string  Subtract( string  x,  string  y)
         {
             //if (x.StartsWith("-") && !y.StartsWith("-"))
             //{
             //    return "-" + Add(x.TrimStart('-'), y);
             //}
             //if (y.StartsWith("-"))
             //{
             //    return Add(x, y.TrimStart('-'));
             //}
             //x是正数，y也是正数
             int  flag = checkBigger(x, y);
             if  (flag == 0)
             {
                 return  "0" ;
             }
             else  if  (flag == -1)
             {
                 string  tmp = y;
                 y = x;
                 x = tmp;
             }
             //保证了x>=y
             y = y.PadLeft(x.Length,  '0' ); //y补0与x对齐
             int [] difference =  new  int [x.Length];
             for  ( int  i = x.Length - 1; i >= 0; i--)
             {
                 int  tmpdifference;
                 tmpdifference =  int .Parse(x[i].ToString()) -  int .Parse(y[i].ToString()) + difference[i];
                 if  (tmpdifference < 0)
                 {
                     tmpdifference += 10;
                     difference[i - 1] = -1; //表示借位
                 }
                 difference[i] = tmpdifference;
             }
             StringBuilder returnvalue =  new  StringBuilder( string .Concat(difference).TrimStart( '0' ));
             {
                 if  (returnvalue.ToString() ==  "" )
                 {
                     return  "0" ;
                 }
             }
             if  (flag == -1)
             {
                 returnvalue = returnvalue.Insert(0,  "-" );
             }
             return  returnvalue.ToString();
         }
         //比较大小
         static  int  checkBigger( string  x,  string  y)
         {
             if  (x.Length > y.Length)
             {
                 return  1;
             }
             else  if  (x.Length < y.Length)
             {
                 return  -1;
             }
             else
             {
                 for  ( int  i = 0; i < x.Length; i++)
                 {
                     if  ( int .Parse(x[i].ToString()) >  int .Parse(y[i].ToString()))
                     {
                         return  1;
                     }
                     else  if  ( int .Parse(x[i].ToString()) <  int .Parse(y[i].ToString()))
                     {
                         return  -1;
                     }
                     continue ;
                 }
                 return  0;
             }
         }
         //模拟移位
         static  string  Power10( string  num,  int  n)
         {
             return  num.PadRight(num.Length + n,  '0' );
         }
                                      
     }
}


测试了一下1234567890.........1234567890(260个1234567890，2600位)的平方，得出的结果如下：163627903.png


可以从https://defuse.ca/big-number-calculator.htm得到验证。