首页 > 其他 > 详细

Bluestein's Algorithm

时间:2020-05-29 21:32:01      阅读:50      评论:0      收藏:0      [点我收藏+]

用下降幂搞搞事情

\[ \frac{m(m-1) + k(k+1) -(m-k)(m-k-1)}{2} \ =\frac{m^2 - m + k^2 + k - m^2 - k^2 + 2mk - k + m}{2} \ = mk \ y_{m} = \sum_{k=0}^n A_{k}\omega^{mk}\\=\omega^{\frac{m(m-1)}{2}}\sum_{k=0}^n A_k\omega^{\frac{k(k+1)}{2}}\omega^{\frac{-(m-k)(m-k-1)}{2}} \]

后面是一个卷积形式,可以快速实现求 \(f(x),f(x^1), f(x^2) .. f(x^n)\) 以及循环卷积意义下的多项式快速幂

Bluestein's Algorithm

原文:https://www.cnblogs.com/mangoyang/p/12989428.html

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