快速加算法

· · 休闲·娱乐

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

摘要

本文介绍了一种在 \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 m)。用 T(m) 表示该算法的复杂度，由于计算 a^2+b^2+2ab 需要两次加法运算，则有

T(m)=\mathcal O(m \log m)+2T(2m)

对上式变形，可得

2T(2m)=T(m)-\mathcal O(m \log m)

即

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

故

T(m)=-m\log m\sum_{i=1}^{\infin}\frac{1}{4^i}=\mathcal O(-m\log m)

由 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。我们知道，

\sum_{i=0}^{\infin}2^i=(1111\cdots 1)_2=-1

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

总结

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

参考文献

快速加算法