首页 > 其他 > 详细

O(nlog^2/loglogn)的cdq FFT

时间:2020-03-04 12:31:20      阅读:73      评论:0      收藏:0      [点我收藏+]

论文鸽在群里说了一下这个东西,我也实现了一下,发现效果还不错。

由于这个 exp 的 \(O(n\log n)\) 算法非常的慢,所以我们一般采用 \(O(n\log^2 n)\) 的分治 FFT 来求解。

普通的分治 FFT 已经可以与论文鸽的 exp 五五开了,但是有没有更快的方法呢?

注意,这个优化只能在 cdq FFT 的时候采用,也就是说不能优化 n 个一次多项式的卷积之类的问题。

\(O(n\log^2n)\)

我们先来回忆一下普通的分治 FFT 是如何做的。

我们假设 \(F(x) = e^{G(X)}\),这里我们知道 \(G(x)\),我们要求解 \(F(x)\)

两侧求导,得 \(F^{'}(x) = e^{G(X)} \times G^{'}(X) = F(X) \times G^{'}(X)\)

也就是说我们是对这个式子进行求解:\(F^{'}(x) = F(X) \times G^{'}(X)\)

我们采用 \(solve(l, r)\) 表示求解 \(F(X)\) 的第 \(l\) 项到第 \(r\) 项。

取区间中点 \(mid\)

先调用 \(solve(l, mid)\) 来求解出前半部分。

再计算左侧对右侧的贡献。

再调用 \(solve(mid + 1, r)\) 来求解出后半部分。

这就是普通的分治 FFT。

\(O(\frac{n\log^2n}{\log \log n})\)

首先分治 FFT 是一个树状结构,我们往往可以尝试增加一层往下的分支数来优化深度。

我们设分支数为 \(B\)

如果直接分治 FFT,那么需要计算每个儿子对后面儿子的贡献,每次计算需要一个长度为 \(O(n / B)\) 的卷积(\(n\)为目前分治区间长度)。

也就是说时间复杂度 \(T(n) = B \times T(\frac{n}{B}) + B \times n \times \log {\frac{n}{b}}\),大力求解得 \(B=2\) 时最优。

我是不是在玩你。

好的我们继续。

我们真的是每一对儿子都要用一次卷积来计算贡献吗?

我们可以先求出这个儿子的点值,考虑它对后面儿子的贡献,这个儿子的点值就不用重复计算了。

存储前面儿子对它的贡献的时候,你也可以直接存储点值,最后一次 FFT 转换即可,也不用多次计算了。

而卷上的是 \(G^{'}(x)\) 的一个区间,这个区间的点值也可以提前计算。

也就是说我们只需要 \(O(B)\) 次长度为 \(O(n / B)\) 的 FFT 了!

因此计算贡献的部分复杂度变为了 \(O(B^2 \times \frac{n}{B} + B \times \frac{n}{b} \times \log {\frac{n}{b}})\)

\(O(Bn + n \times \log {\frac{n}{b}})\)

时间复杂度 \(T(n) = B \times T(\frac{n}{B}) + Bn + n \times \log {\frac{n}{b}}\)。不错,求解一下。

发现 \(B = O(\log n)\) 的时候最优秀,时间复杂度为\(O(\frac{n\log^2n}{\log \log n})\)

事实上由于计算贡献的时候非常的****,可以使用 avx2 进行优化,亲测一定的常数优化之后进行 \(4 \times 10^6\) 的 exp 只需要 1.5s。

当然其他类似的 cdq FFT 也可以这样进行优化,祝大家早日吊打 \(O(n\log n)\)

O(nlog^2/loglogn)的cdq FFT

原文:https://www.cnblogs.com/skip1978/p/12408384.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!