大整数乘法和Strassen矩阵乘法
本节中，研究两个不同寻常的算法，它们用于解决两个数的乘法和两个方阵的乘法。两个算法都以增加少量加法运算为代价，减少乘法运算的执行总次数 。为了达到这个目的，两者都使用了分治思想。
大整数乘法
当代的密码技术，需要对超过100位的十进制整数进行乘法运算。因为这样的整数过于长，现代计算机的一个“字”是装不下的，所以我们需要对它们作特别的处理。这就是研究高效的大整数乘法运算的现实需求。
经典的笔算算法对两个n位整数相乘，第一个数中的n个素质分别要被第二个数中的n个数字相乘，这样就一共要做n^2次位乘。现在我们用分治法设计一个乘法次数少于n^2的算法.
为了展示该算法的基本思想，我们研究一个两位整数相乘的案例，比如说，23和14.这两个数字可以这样表示：
23 = 2·10^1 + 3·10^0
14 = 1·10^1 + 4^10^0
现在把它们相乘：
23 = (2·10^1 + 3·10^0) * (1·10^1 + 4·10^0)
= (2 * 1)10^2 + (3 * 1 + 2 * 4)10^1 + (3 * 4)10^0
方程产生出一个正确的结果322，和笔算算法一样，使用了四次位乘。
但是2*1和3*4无论如何都需要计算，我们可以利用它们的积，只做一次乘法计算出中间项的结果，来减少位乘的次数。
3 * 1 + 2 * 4 = (2+3) * (1+4) - (2 * 1) - (3 * 4)
总结一个规律，对于任何两位数a=a1a0和b=b1b0，它们的积c可以用这个公式来计算：
c = a * b = c2 * 10^2 + c1 * 10^1 + c0
其中，
c2 = a1 * b1
c0 = a0 * b0
c1 = (a1+b1) * (a0+b0) - (c2+c0)，即a数字和b数字和的积减去c2与c0的和。
现在我们应用这个窍门计算两个n位整数a和b的积，其中n是一个正的偶数。我们从中间把两个数字一分为二，毕竟，要利用分治技术。把a的前半部分记住a1, a的后半部分记住a0；对于b，则分别记住b1和b0.
在这种记法中，a＝a1a0意味着a=a1*10^(n/2) + a0, b = b1b0意味着b=b1*10^(n/2) + b0.所以利用与计算两位数相同的方法，我们有：
c = a * b = (a1 * 10^(n/2) + a0) * (b1 * 10^(n/2) + b0)
= (a1 * b1)10^n + (a1 * b0 + a0 * b1)10^(n/2) + (a0 * b0)
= c2 * 10^n + c1 * 10^(n/2) + c0
其中，
c2 = a1*b1是它们前半部分的积c0 = a0*b0,是它们后半部分的积，
c1 = (a1+a0)*(b1+b0)-(c2+c1)是a两部分和与b两部分和的积减去c2与c0的和。
因此，如果n是2的乘方，我们就得到了一个计算两个n位数积的递归算法。在这种完美的形式下，当n变成1时，递归就停止了。
该算法会做多少次位乘呢？
因为n位数的乘法需要对n/2位数做三次乘法运算，乘法次数M(n)的递推式将会是：
当n>1时，M(n) = 3M(n/2), M(1)=1
当b＝2^k时，我们用反向替换法对它求解：
M(2^k) = 3M(2^k-1) = 3[3M(2^(k-2))] = 3^2M(2^(k-2))
= …=3^iM(2^(k-i)=…=3^kM(2^(k-k))=3^k
因为k＝log2 n,
M(n) = 3^(log2 n) = n^(log2 3) ≈ n^1.585
(最后一步，利用了对数的一个特性：a^logb c = c^logb a
对于不是很大的整数，该算法的运行时间很可能比经典算法长。报告说，实验显示，大于600位的整数开始，分治算法的性能超越了笔算算法的性能。如果我们使用类似Java，C++和Smalltalk这样的面向对象的语言，会发现这些语言专门为处理大整数提供了一些类。
Strassen矩阵乘法
分治方法可以减少两个数乘法中的位乘次数，它在矩阵乘法中发挥的同样作用。V.Strassen在1969年发表了一个算法，该算法的成功依赖于这个实现：计算两个2阶方阵A和B的积C只需要进行7次乘法运算，而不是曼丽算法所需要的8次(n^3=2^3).为了做到这一点，我们使用了下面的公式。
其中，
因此，对两个2阶方阵相乘时，Strassen算法执行了7次乘法和18次加减法，而蛮力算法需要执行8次乘法和4次加减法。该算法的重要性体现在当矩阵的阶趋于无穷大时，该算法所表现出来的卓越的渐进效率。
假设n是2的乘方，A和B是两个n阶方阵（如果n不是2的乘方，矩阵可以用全0的行或列来填充）。我们把A，B和C分别划分为4个n/2阶的子矩阵：
我们像对待数字一样对待这些子矩阵，求得正确的积。例如，把数字替换成相应的子矩阵的话，C00用M2+M4-M5+M7来计算，其中M1，M4，M5和M7是由Strassen方程定义的。如果递归调用相同的方法来计算7个n/2阶矩阵的乘积，我们就得到了矩阵乘法的Strassen算法。
评估一下该算法的渐进效率。如果M(n)是Strassen算法在计算两个n阶方阵时执行的乘法次数，我们对它有下面的递推关系式：
当n > 1时，M(n) = 7M(n/2), M(1) = 1
因为n=2^k,
因为k＝log2 n，
它比蛮力算法需要的n^3次乘法运算要来得小。
因为减少了的乘法运算次数是以额外的加法运算为代价的，我们必须检查一下Strassen算法执行的加法次数A(n).对两个n>1阶矩阵相乘时，该算法要对n/2阶的矩阵作7次乘法和18次加法；当n＝1时，因为两个数字直接相乘，所以没有执行加法运算，从这一事实我们得出了下列递推关系式：
根据主定理，A(n)∈Θ(n^(log2 7)).换句话说，加法的增长次数和乘法的增长次数是相同的。所以Strassen算法属于集合Θ(n^(log2 7)),这个效率类型要比蛮力法的Θ(n^3)要来得好。
目前为止，这类算法中最快的是Coopersmith和Winograd发明的，它的时间效率达到了O(n^2.376).指数值的减小以算法越来越复杂为代价的。而且乘法常量的值很大，使它们没有实用的价值。然而从学术的观点看，我们得到的最优效率和理论上的最优效率之间还有鸿沟，但它们越来越接近。矩阵乘法在理论上的效率下界n^2次乘法。另一方面，矩阵乘法同其他一些重要问题在算法上是等价的，比如解线性方程组问题。