10.5. 变换的概念¶
10.5.1. 变换的概念：整数乘法¶
乘两个大数比把它们加起来困难得多。回想一下你在学校学过的做大数加法和大数乘法的算法。两个 \(n\) 位数相加是简单地从右到左扫过两个数，总共 \(O(n)\) 的工作。但直接乘两个 \(n\) 位数的成本是 \(O(n^2)\)，因为你本质上需要把一个数的每一位与另一个数的每一位相乘。
回想一下对数的一个性质： \(\log nm = \log n + \log m\)。因此，如果取对数和反对数都很廉价，那么我们就可以取两个操作数的对数、相加、再取和的反对数，从而把乘法归结为加法。
在正常情况下，取对数和反对数是昂贵的，所以这种归结通常不会被认为是可行的。然而，这种归结正是计算尺的基础。计算尺用对数刻度来度量两个数的长度，实际上自动完成了向对数的转换。然后把这两个长度相加，再在另一个对数刻度上读出和的反对数。通常被认为昂贵的那部分（取对数和反对数）其实很廉价，因为它是计算尺的物理组成部分。于是，整个乘法过程都可以通过归约为加法而廉价地完成。在电子计算器问世之前的年代，科学家和工程师经常用计算尺进行这类基本计算。
这个快速的乘法过程是使用 变换 来加速问题求解的一个例子。我们通过对输入值取对数完成了变换，然后在变换后的值上执行了一个廉价的操作（加法），再通过反向变换（使用反对数）得到原始问题的真实答案。
10.5.2. 多项式乘法¶
现在考虑大规模多项式相乘的问题。一个包含 \(n\) 个值的向量 \(\mathbf a\) 可以唯一表示一个 \(n-1\) 次多项式，表示为
或者，一个 \(n-1\) 次多项式可以用它在 \(n\) 个不同点的值列表唯一表示。求多项式在给定点的值被称为 求值 过程。给定在 \(n\) 个点的值求多项式的系数被称为 插值 过程。
有许多有用的工程问题涉及两个大规模多项式相乘。这可以用一个变换来完成，它涉及求值（通常很贵）、插值（通常很贵）和向量乘法（很便宜），其概念与计算尺如何用变换高效地乘大数类似。加速这一过程的秘诀在于仔细选择求值和插值的正确值。
现在，让我们开始思考加速的方法。
