问题及解答

我们以十位数乘以十位数为例. 这里 $ab$ 是十位数, 即 $10a+b$, $a,b\in\{0,1,2,\ldots,9\}$.

\[
ab\times cd=(10a+b)(10c+d)=100ac+10(ad+bc)+bd.
\]

这是通常的算法, 需要 4 次乘法.

注意到

\[
(a+b)(c+d)=(ac+bd)+(ad+bc),
\]

因此,

\[
ad+bc=(a+b)(c+d)-(ac+bd)
\]

于是

\[
ab\times cd=100ac+10(ad+bc)+bd=100ac+10[(a+b)(c+d)-(ac+bd)]+bd.
\]

这里, 我们只需 $ac$, $bd$, $(a+b)(c+d)$ 三次乘法.

对于大的整数, 采用分治策略, 归结为小整数的乘法和加法运算.