2. 变换的概念¶

2.1. 变换的概念：整数乘法¶

乘两个大数比把它们加起来困难得多。回想一下你在学校学过的做大数加法和大数乘法的算法。两个 \(n\) 位数相加是简单地从右到左扫过两个数，总共 \(O(n)\) 的工作。但直接乘两个 \(n\) 位数的代价是 \(O(n^2)\)，因为你本质上需要把一个数的每一位与另一个数的每一位相乘。

回想一下对数的一个性质： \(\log nm = \log n + \log m\)。因此，如果取对数和反对数都很廉价，那么我们就可以取两个操作数的对数、相加、再取和的反对数，从而把乘法归结为加法。

在正常情况下，取对数和反对数是昂贵的，所以这种归结通常不会被认为是可行的。然而，这种归结正是计算尺的基础。计算尺用对数刻度来度量两个数的长度，实际上自动完成了向对数的转换。然后把这两个长度相加，再在另一个对数刻度上读出和的反对数。通常被认为昂贵的那部分（取对数和反对数）其实很廉价，因为它是计算尺的物理组成部分。于是，整个乘法过程可以通过归结为加法定成廉价操作。在电子计算器问世之前的年代，科学家和工程师经常用计算尺进行这类基本计算。

这个快速的乘法过程是使用变换来加速问题求解的一个例子。我们通过将输入值取它们的自然对数，然后在变换后的值上执行了一个廉价的操作（加法），然后通过反向变换（使用反对数）来得到对原始问题的真实答案。