通过平方根展开对多值函数求值

Last updated on Nov 12, 2025

在之前关于“多值函数的图像保持（Image Preservation of Multivalued Functions）”的章节中，我们看到，与其在 $k$ 次单位根上计算 $f(x)$ ，不如将 $f(x)$ 转换为一个多值函数，并在定义域 $\set{1}$ 上对其进行求值。

展开平方根

将 1 的 8 次根看作嵌套的平方根会更容易理解：

\sqrt[8]{x}=\sqrt{\sqrt{\sqrt{x}}}

现在我们展示如何计算：

\sqrt{\sqrt{\sqrt{1}}}

使用平方根展开的方法。

我们知道 $\sqrt{1}$ 的计算结果为 $\set{1,-1}$ ，因此我们将 1 的最内层平方根替换为它的求值结果：

这“消除”了一层平方根。接下来，我们计算 $\sqrt{1}$ 和 $\sqrt{-1}$ 。由于我们是在 8 次单位根上进行计算， $-1\equiv\omega^4$ ，因此 $\sqrt{-1}=\{\omega^2,-\omega^2\}$

然后，我们计算剩余的每一个平方根：

观察发现，求值树的“叶子”恰好是 $f$ 在 8 次单位根上的求值结果。

在 8 次单位根上计算 $f(x)=x^2$

平方根展开的妙处在于，对于 $x$ 的大多数幂次，平方根会像这个例子所展示的那样“尽早消失”。我们将 $x$ 替换为 $\sqrt[8]{x}$ ，但由于 $x$ 是平方，我们最终得到的是 $\sqrt[4]{x}$ 或者

\sqrt{\sqrt{x}}

下面是不断展开平方根直到获得 8 个求值结果的求值树。在最后一行，当没有平方根时，我们直接将对应的值复制下来。

现在观察一下，如果我们直接在 $f(x)=x^2$ 上对 8 次单位根 $\set{1,...,\omega^7}$ 进行求值会发生什么——结果是完全一样的。

\begin{align*} f(1)&=(1)^2&=1\\ f(-1)&=(-1)^2&=1\\ f(\omega^2)&=(\omega^2)^2&=-1\\ f(-\omega^2)&=(-\omega^2)^2&=-1\\ f(\omega)&=(\omega)^2&=\omega^2\\ f(-\omega)&=(-\omega)^2&=\omega^2\\ f(\omega^3)&=(\omega^3)^2&=-\omega^2\\ f(-\omega^3)&=(-\omega^3)^2&=-\omega^2\\ \end{align*}

在 8 次单位根上计算 $f(x)=x^4$

同样地，我们将 $x$ 替换为 $\sqrt[8]{x}$ ，这会得到 $\sqrt{x}$ 。由于我们只有一个平方根，我们将只对平方根进行一次展开，然后简单地将结果复制下来即可。

我们在前面的章节中看到，如果 $x^{k/2}$ 在 $\omega$ 的偶数次幂上求值，结果为 1，否则为 -1。这里的结果与预期完全一致。

在 8 次单位根上计算 $f(x)=ax+bx^5$

如果我们将 $x$ 替换为 $\sqrt[8]{x}$ ，我们会得到一个有些尴尬的结果：

f(x)=a\sqrt[8]{x}+bx^{5/8}

然而，如果我们先提取出 $x$ ，将 $f(x)$ 转换为 $f(x)=x(a+bx^4)$ ，那么当我们将 $x$ 替换为 $\sqrt[8]{x}$ 时，新形式就变得容易处理得多：

g(x)=\sqrt[8]{x}(a+b\sqrt{x})

第一层平方根将在第一次求值后消失，并且在求值树的大部分节点中， $(a+b\sqrt{x})$ 将变成一个常数。

下面是展开平方根的图解。在每一层，我们解开（求值）一个平方根。蓝色的平方根代表每一步被求值的部分。作为一个通用规则，如果是嵌套的平方根，请对最内层的平方根进行求值：

现在，让我们将该结果与在 8 次单位根上逐个计算 $f(x)=ax+bx^5$ 的结果进行比较：

\begin{array}{rcll} f(1) &=& a(1) + b(1)^5 &= a + b\\[4pt] f(-1\equiv\omega^4) &=& a\omega^4 + b\omega^{20} = a(-1) + b(-1) &= -a - b\\[4pt] f(\omega^2) &=& a\omega^2 + b\omega^{10} = a\omega^2 + b\omega^2 &= (a + b)\omega^2\\[4pt] f(-\omega^{2}\equiv\omega^6) &=& a\omega^6 + b\omega^{30} = a(-\omega^2) + b(-\omega^2) &= -(a + b)\omega^2\\[4pt] f(\omega) &=& a\omega + b\omega^5 &= a\omega - b\omega \\[4pt] f(-\omega\equiv\omega^5) &=& a\omega^5 + b\omega^{25} = a(-\omega) + b\omega &= -a\omega + b\omega = (b - a)\omega\\[4pt] f(\omega^3) &=& a\omega^3 + b\omega^{15} = a\omega^3 + b\omega^7 &= a\omega^3 - b\omega^3 = (a - b)\omega^3\\[4pt] f(-\omega^3\equiv\omega^7) &=& a\omega^7 + b\omega^{35} = a(-\omega^3) + b(-\omega^3) &= -(a + b)\omega^3 \end{array}

使用上述方法计算各项需要进行 8 次加法和 16 次乘法。

但是，使用平方根展开，我们只需要 2 次加法和 10 次乘法。每当一个平方根被展开为它的两个解时，我们就将它与相邻的项相乘。因此，每当解开“最终”的平方根时，就会产生两次乘法。这些在下图中用红色高亮显示。加法用蓝色高亮显示。

请注意，“计算平方根”是完全确定性的。我们知道它总是遵循 $\set{1}$ 、2 次单位根、4 次单位根、8 次单位根等等这样的规律。因此，不需要显式地计算平方根。

简单项与困难项

我们可以看到， $x^{k/2}$ 项最容易计算，因为它们只需要进行 1 次求值，剩余部分只需沿求值树向下复制对应的值即可。

另一方面，没有幂次（也就是 1 次方）的 $x$ 是“最困难”计算的，因为在沿求值树向下的每一步中，我们都需要进行平方根展开。

函数 $f(x)=a+bx^{k/2}$ 的美妙之处在于，当它在 $k$ 次单位根上变为多值函数 $g(x)=(a+b\sqrt{x})$ 时，我们在求值树的第二层就完全计算出了平方根，在剩余的计算过程中，只需将 $a+b$ 的和复制下来即可。

实际上，任何多项式都可以被改写为“最大化” $a+bx^{k/2}$ 项的数量并“最小化” $x$ 项的数量。

假设我们有一个 7 次多项式，想要在 8 次单位根上进行求值。

f(x)= a_0 + a_1x + a_2x^2 + a_3x^3 + a_4x^4 + a_5x^5 + a_6x^6 + a_7x^7

为了使 $x^4$ 项的数量最大化且只保留一个 $x$ 项，我们将其因式分解如下：

f(x)= a_0 + a_2x^2 + a_4x^4 + a_6x^6 + a_1x + a_5x^5 + a_3x^3+ a_7x^7

f(x)= a_0 + a_4x^4 + (a_2x^2 + a_6x^6) + (a_1x + a_5x^5) + (a_3x^3+ a_7x^7)

f(x)= a_0 + a_4x^4 + x^2(a_2 + a_6x^4) + x(a_1 + a_5x^4) + x^3(a_3x+ a_7x^4)

f(x)= a_0 + a_4x^4 + x^2(a_2 + a_6x^4) + x((a_1 + a_5x^4) + x^2(a_3x+ a_7x^4))

练习： 在 4 次单位根上计算多项式 $f(x)=a_0+a_1x+a_2x^2+a_3x^3$ 时，应当如何对其进行因式分解，才能使其只有一个 $x$ 项并包含尽可能多的 $x^2$ 项？请记住，在这种情况下 $x^{k/2}$ 就是 $x^2$ 。

在下一章中，我们将展示如何使用平方根展开计算一般的 4 次和 8 次多项式，这也恰好就是 NTT 算法。