腾讯云

文章/答案/技术大牛

发布

社区首页 >问答首页 >快速傅立叶变换多项式乘法

问快速傅立叶变换多项式乘法
EN

Stack Overflow用户

提问于 2012-07-06 04:07:40

回答 1查看 1.4K关注 0票数 2

我正在使用FFT来计算某个点上的多项式，以便可以使用值表示法来表示它。(表示为与其度数相等的点数)

然而，为了将两个d次多项式相乘，我需要在2d +1点处计算这两个多项式。但是，使用FFT进行计算(乘以dth的单位根)仅计算d点处的多项式。因此，如果FFT只在d点处计算多项式，那么如何使用FFT进行多项式计算？(相对于2d + 1)

algorithm

math

computer-science

fft

回答 1

Stack Overflow用户

回答已采纳

发布于 2012-07-06 04:24:10

你可以选择计算-1的第n个根。如果您需要2d-1点(我怀疑您需要)，只需使用-1的(2d-1)-th根。实际上，您通常会使用-1的2^k次方根，其中2^k是2log2d-1的第一次幂，因为对2的幂进行快速快速傅立叶变换要容易得多。由于O的定义允许常数因子，因此复杂度仍然是O(d >= d)。

票数 4

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/11355705

复制

如何让8岁表妹快速了解傅立叶变换

其他

而他的独特是因为：他不像其他科学家那般死抓着纯数学研究，而是致力于将数学应用于实际生产。

IT阅读排行榜

2018/08/16

4810

从傅立叶级数到傅立叶变换

对象存储

卡尔曼和玻尔兹曼谁曼

2020/08/02

7070

从傅立叶级数到傅立叶变换

css

卡尔曼和玻尔兹曼谁曼

2019/11/02

6430

傅立叶变换公式解析

“傅立叶变换是信号分析的基础。看到公式的瞬间，就有想要放弃的感觉～让我们从目的出发，逐步展现它的逻辑之美”

用户7573907

2020/07/21

1.4K0

离散傅立叶变换的Python实现

python set 函数可视化数据

离散傅里叶变换（Discrete Fourier Transform，缩写为DFT），是指傅里叶变换在时域和频域上都呈现离散的形式，将时域信号的采样变换为在离散时间傅里叶变换（DTFT）频域的采样。在形式上，变换两端（时域和频域上）的序列是有限长的，而实际上这两组序列都应当被认为是离散周期信号的主值序列。即使对有限长的离散信号做DFT，也应当对其经过周期延拓成为周期信号再进行变换。在实际应用中，通常采用快速傅里叶变换来高效计算DFT。

曼亚灿

2023/07/31

1.4K0

傅立叶变换的物理意义

编程算法

傅立叶变换是数字信号处理领域一种很重要的算法。要知道傅立叶变换算法的意义，首先要了解傅立叶原理的意义。傅立叶原理表明：任何连续测量的时序或信号，都可以表示为不同频率的正弦波信号的无限叠加。而根据该原理创立的傅立叶变换算法利用直接测量到的原始信号，以累加方式来计算该信号中不同正弦波信号的频率、振幅和相位。

全栈程序员站长

2022/07/15

6290

离散傅立叶变换及相关解析

node.js

“前一篇文章我们讲解了傅立叶变换的理论公式，而实际工程应用中采集到的信号都是离散的数据，采用的是离散傅立叶变换。让我们继续解析一下其推导过程及相关概念”

用户7573907

2020/07/21

2.6K0

MATLAB实现图像的傅立叶变换

matlab 图像处理

傅里叶变换是线性系统分析的一个有力工具，它能够定量地分析诸如数字化系统、采样点、电子放大器、卷积滤波器、噪音和显示点等的作用。通过实验培养这项技能，将有助于解决大多数图像处理问题。对任何想在工作中有效应用数字图像处理技术的人来说，把时间用在学习和掌握博里叶变换上是很有必要的。

timerring

2023/03/04

1.2K0

全面解析傅立叶变换（非常详细）

全栈程序员站长

2022/11/01

6K0

从傅立叶变换到Gabor滤波器

编程算法

作者：夏　敏编辑：李文臣 PART 01 gabor介绍 gabor特征首先我们介绍下Gabor 特征，它是一种可以用来描述图像纹理信息的特征，Gabor 滤波器的频率和方向与人类的视觉系统类似，特别适合于纹理表示与判别。它主要依靠 Gabor 核在频率域上对信号进行加窗，从而能描述信号的局部频率信息。而Gabor 核靠傅里叶变换，我们才能将信号转换到频率域，才能让Gabor核在频率域去加窗。而在原本的空间域中，一个 Gabor 核实际上就是一个高斯核与正弦波调制的结果，可以看做是高斯核应用在了正弦

机器学习算法工程师

2018/03/06

2.2K0

神经网络与傅立叶变换有关系吗？

神经网络深度学习卷积神经网络编程算法

机器学习和深度学习中的模型都是遵循数学函数的方式创建的。从数据分析到预测建模，一般情况下都会有数学原理的支撑，比如：欧几里得距离用于检测聚类中的聚类。

deephub

2022/06/04

7450

神经网络与傅立叶变换有何关系？

神经网络深度学习卷积神经网络函数数学

算法进阶

2023/08/28

3580

LOJ #108. 多项式乘法

其他

内存限制：256 MiB时间限制：1000 ms标准输入输出题目类型：传统评测方式：文本比较上传者：匿名提交提交记录统计讨论测试数据题目描述这是一道模板题。输入两个多项式，输出这两个多项式的乘积。输入格式第一行两个整数 n nn 和 m mm，分别表示两个多项式的次数。第二行 n+1 n + 1n+1 个整数，分别表示第一个多项式的 0 00 到 n nn 次项前的系数。第三行 m+1 m + 1m+1 个整数，分别表示第二个多项式的 0 00 到 m mm 次项前的系数。输出格式

attack

2018/04/11

7200

R语言蒙特卡洛计算和快速傅立叶变换计算矩生成函数

function

特征函数能够唯一确定随机变量的概率分布，如果随机变量的概率密度函数f(x)存在，特征函数相当于 f(x)的傅里叶变换。

拓端

2020/09/28

1.2K0

在图像的傅里叶变换中,什么是基本图像_傅立叶变换

图像处理

大家好，又见面了，我是你们的朋友全栈君。从现代数学的眼光来看，傅里叶变换是一种特殊的积分变换。它能将满足一定条件的某个函数表示成正弦基函数的线性组合或者积分。在不同的研究领域，傅里叶变换具有多种不同的变体形式，如连续傅里叶变换和离散傅里叶变换。傅立叶变换属于调和分析的内容。”分析”二字，可以解释为深入的研究。从字面上来看，”分析”二字，实际就是”条分缕析”而已。它通过对函数的”条分缕析”来达到对复杂函数的深入理解和研究。从哲学上看，”分析主义”和”还原主义”，就是要通过对事物内部适当的分析达到增进对其本质理解的目的。比如近代原子论试图把世界上所有物质的本源分析为原子，而原子不过数百种而已，相对物质世界的无限丰富，这种分析和分类无疑为认识事物的各种性质提供了很好的手段。在数学领域，也是这样，尽管最初傅立叶分析是作为热过程的解析分析的工具，但是其思想方法仍然具有典型的还原论和分析主义的特征。”任意”的函数通过一定的分解，都能够表示为正弦函数的线性组合的形式，而正弦函数在物理上是被充分研究而相对简单的函数类，这一想法跟化学上的原子论想法何其相似！奇妙的是,现代数学发现傅立叶变换具有非常好的性质,使得它如此的好用和有用,让人不得不感叹造物的神奇: 1. 傅立叶变换是线性算子,若赋予适当的范数,它还是酉算子; 2. 傅立叶变换的逆变换容易求出,而且形式与正变换非常类似; 3. 正弦基函数是微分运算的本征函数,从而使得线性微分方程的求解可以转化为常系数的代数方程的求解.在线性时不变的物理系统内,频率是个不变的性质,从而系统对于复杂激励的响应可以通过组合其对不同频率正弦信号的响应来获取; 4. 著名的卷积定理指出:傅立叶变换可以化复杂的卷积运算为简单的乘积运算,从而提供了计算卷积的一种简单手段; 5. 离散形式的傅立叶变换可以利用数字计算机快速的算出(其算法称为快速傅立叶变换算法(FFT)). 正是由于上述的良好性质,傅里叶变换在物理学、数论、组合数学、信号处理、概率、统计、密码学、声学、光学等领域都有着广泛的应用。傅立叶变换在图像处理中有非常非常的作用

全栈程序员站长

2022/09/27

1.4K0

使用傅立叶变换清理时间序列数据噪声

python https 网络安全

傅立叶变换是一种从完全不同的角度查看数据的强大方法：从时域到频域。但是这个强大的运算用它的数学方程看起来很可怕。

deephub

2021/10/20

4.2K0

UOJ#34. 多项式乘法(NTT)

nat

这是一道模板题。给你两个多项式，请输出乘起来后的多项式。输入格式第一行两个整数 nn 和 mm，分别表示两个多项式的次数。第二行 n+1n+1 个整数，表示第一个多项式的 00 到 nn 次项系数。第三行 m+1m+1 个整数，表示第二个多项式的 00 到 mm 次项系数。输出格式一行 n+m+1n+m+1 个整数，表示乘起来后的多项式的 00 到 n+mn+m 次项系数。样例一 input 1 2 1 2 1 2 1 output 1 4 5 2 explanation (1+2x)⋅(1

attack

2018/05/30

8990

R语言蒙特卡洛计算和快速傅立叶变换计算矩生成函数

编程算法

如果要导出给定分布的矩，则一些矩生成函数很有趣。另一个有趣的特征是，在某些情况下，此矩生成函数（在某些条件下）完全表征了随机变量的分布。

拓端

2020/08/06

9410

一文读懂傅立叶变换处理图像的原理

图像处理

图 (a): (从左到右) (1) 原始图片 (2) 使用高斯低通滤波器 (3) 使用高斯高通滤波器. 本文中的原始图像来自OpenCV Github示例。

小白学视觉

2020/07/01

4.4K0

点击加载更多

相似问题

快速傅立叶变换-乘法多项式？

快速傅立叶变换快速傅立叶变换

OpenMP快速傅立叶变换乘法加速

用快速傅立叶变换库C++计算快速傅立叶变换和快速傅立叶变换

Python NumPy -快速傅立叶变换和逆快速傅立叶变换？

添加站长进交流群

领取专属 10元无门槛券

AI混元助手 在线答疑

关注 腾讯云开发者公众号

洞察 腾讯核心技术

剖析业界实践案例

问快速傅立叶变换多项式乘法
EN