A+B Problem的新解法

$\mathbf{Extremely\ Fast\ Calculation\ of\ Sum}$ $\mathrm{cyq32ent}$

A+B Problem被称作世界上最难的算法问题。无论如何对其进行优化，复杂度从未低于 $\mathcal O(1)$。本文介绍了一种在 $\mathcal O(-\log n\log \log n)$ 时间内求 $a+b$ 的算法。其中，$n$ 为 $\max\{a,b\}$。

引理 1 (完全平方公式) 对于任意整数 $a,b$，有 $(a+b)^2=a^2+b^2+2ab$

证明 读者自证不难。

这启示我们将较大数的和和较小数的和建立联系。

不妨令 $\lceil\log a\rceil=\lceil\log b\rceil$，不相等的情况下可以加前导 $0$ 补足。

定理 1(快速加算法) 对引理1进行变形，得到 $a+b=\sqrt{a^2+b^2+2 a b}$

我们令 $m=\lceil\log n\rceil$；我们知道，通过$\rm{FFT}$ 求解 $ab$ 的值的时间复杂度为 $\mathcal O(m \log m)$；所以在使用二分时，来计算 $\sqrt{a^2+b^2+2 a b}$ 的时间复杂度为 $\mathcal O(m \log^2m)$。用 $T(m)$ 表示该算法的复杂度，由于计算 $a^2+b^2+2ab$ 需要两次加法运算，则有 $T(m)=\mathcal O(m \log^2m)+2T(2m)$

对上式变形，可得 $2T(2m)=T(m)-\mathcal O(m \log^2m)$

即 $T(m)=\frac{T(\frac{m}{2})-\mathcal O(\frac{m}{2} \log^2m)}{2}$

故

由 $m$ 的定义，我们得出该算法的复杂度为 $\mathcal O(-\log n\log \log n)$。

本算法可以用于任何整数之间的加法。

目前普遍使用的加法运算复杂度为 $\mathcal O(\log n)$，在一定范围内为 $\mathcal O(1)$。本算法的时间复杂度小于 $0$，这意味着应用本算法的程序可以在负数时间内计算出两数相加的值。特别的，我们可以在一些较为复杂的算法中应用它；如时间复杂度原本为 $\mathcal O(n 2^n)$ 的旅行商问题，可以应用此算法，优化为 $\mathcal O(-2^n n\log n\log\log n)$。

值得注意的是，在如下的死循环中使用本算法有一定风险，因为这会使得程序执行时间为 $-\infin$，从而导致不可预料的结果。

while(1)c=Add(a,b);

一种可行的替代方案为：

while(1){
  i++;
  for(j=0;j<pow(2,i);j++)
    c=Add(a,b);
}

（注：上述代码中 i、j、a、b、c 为高精度整数类）

这样，该程序的时间复杂度为 $\mathcal O(-\log n\log \log n)\sum_{i=0}^{\infin}2^i$。我们知道，

故上述程序的时间复杂度为 $O(\log n\log \log n)$。

快速加算法是一种时间复杂度超越常规的计算加法的方式。由于运行该算法的应用程序会在得知两数的值之前计算出两数之和，该算法得以拥有广泛的应用前景。