# Questions tagged [fast-fourier-transform]

Fast Fourier transformation computes discrete Fourier transformation efficiently. It is used in many areas including fast polynomial multiplication, signal processing and computing sequence convolutions efficiently.

36 questions
Filter by
Sorted by
Tagged with
22 views

### How can I reduce the complexity of an inverse DFT where I have a uniform frequency series being evaluated at non-uniform target points?

I have implemented an N-dimensional Non-Uniform Discrete Fourier Transform (in this case it's specifically an inverse NUDFT) using PyTorch. My goal with this implementation is to have a function which ...
• 101
79 views

### Implementation of the divide-and-conquer principle for a specific summation formula

I have found two formulas in the work on pages 5 and 6, of which I am trying to develop a recursive implementation. The similarity to the DFT or FFT might be useful here. I divide this question into ...
2k views

### Is there a faster algorithm than FFT if interested only on the maximum amplitude frequency?

Given an $n$ input array, is there an algorithm that is faster than Fast Fourier Transform if we are only interested in obtaining the maximum amplitude frequency? Looking at the Cooley–Tukey algorithm ...
• 254
1 vote
59 views

Consider normalized DFT (discrete Fourier transform) — a transform with input $x = (x_0,\dots,x_{n-1})$ and output $y=(y_0,\dots,y_{n-1})$ s.t. $$y_j = \frac1{\sqrt{n}} \sum_{l=0}^{n-1} x_l \omega^{jl}... • 111 1 vote 1 answer 60 views ### product of every difference Given a sorted array where every element is distinct, we need to evaluate product of every difference, modulo  10^9 + 7$$ \prod_{i < j} (arr[j] - arr[i]) \% (10^9 + 7) $$Best approach I can ... • 333 1 vote 4 answers 178 views ### XOR pair frequency queries We are given an array of length N and Q queries (offline) where each query is a value K, for each query we need to count number of pairs in array with XOR K. If N and Q can both be upto ... • 333 0 votes 0 answers 36 views ### Matrix Multiplication with a matrix consisting of a single shifted row I have the following question (prefacing this with the fact that this is a question from an exam, I am currently studying but am stumped so reaching out for help). The answer to the following ... • 13 0 votes 0 answers 47 views ### How to calculate FFT([a1, a2, . . . , an]) in time O(n), when you know FFT([a0, a1, . . . , an−1])? I came across this problem while studying the FFT, but I have no idea how to solve it. Can anyone help? 2 votes 0 answers 55 views ### Algorithm to compute sum of quotient polynomials Let f(X) be a polynomial in \mathbb{F}_p[X] for some prime p (of size 256 bits) that is not necessarily FFT-friendly. Let a_1,\cdots,a_n, b_1,\cdots, b_n be \mathbb{F}_p elements. What is ... • 193 1 vote 0 answers 47 views ### What algorithms apart from FFT get a computational boost by leveraging complex numbers? If we think of the algorithmic problem of doing a convolution of two arrays, it turns out that converting them to the frequency domain first and then doing an element-wise product is equivalent. And ... • 377 5 votes 3 answers 887 views ### Multiplying 2 positive integers using FFT and convolutions I was trying to figure out how I can perform multiplication of 2 big integers using FFT and convolutions, I ran into the following article: http://numbers.computation.free.fr/Constants/Algorithms/fft.... • 275 1 vote 1 answer 76 views ### FFT of logarithmic input data Is there a reasonably accurate method of computing an FFT of logarithmically-represented input data (with a sign bit, that is ±2^{\text{double-precision value}})? The naive method (convert to linear ... • 1,414 0 votes 1 answer 167 views ### Why does merge sort work for any n, but the basic FFT algorithm only for powers of 2? Merge sort and FFT are both divide and conquer algorithms that split the input in two repeatedly. While merge sort can be applied to any n, the FFT algorithm given in CLRS (section 30.2, third ... • 377 2 votes 3 answers 258 views ### FFT algorithm for arbitrary n In section 30.2 of CLRS (third edition), they given an algorithm for computing the fast Fourier transform of a vector represented as an n dimensional array when n is a power of 2. They say that ... • 377 2 votes 0 answers 79 views ### Fastest algorithm for polynomial multiplication in 256-bit finite fields I am looking for the fastest algorithm (in practice) to multiply two polynomials f(X)\cdot h(X) in \mathbb{F}_p[X]. The prime p is roughly 256 bits but the integer p-1 might not have any ... • 193 4 votes 0 answers 59 views ### Polynomial multiplication in finite field without smooth-order roots of unity I am working in a finite prime field \mathbb{F}_p that does not have primitive n-th roots of unity for any large smooth integer n, which makes FFTs a bit difficult. If I need to compute a ... • 193 1 vote 1 answer 91 views ### Product of sparse polynomials with FFT I need to compute the product of two polynomials f(X) and g(X) over a finite field. The degrees of these polynomials are n^2 for some integer n. However, we also know that the polynomials are ... • 193 3 votes 1 answer 483 views ### How do I take the average of multiple Fast Fourier Transforms? How do I take the average of multiple fast Fourier transforms (ffts)? I have multiple audios that I want to take the fft of and then average these results to smooth out the random noise that appears ... 2 votes 0 answers 32 views ### Fast calculations using fast-Fourier convolution Consider an array X with shape H \times W. Let Y be the other array of the same shape and Z is an array of shape h \times w. We want to construct an array R of shape (H-h + 1, W-w+ 1) by ... • 151 0 votes 0 answers 237 views ### Recursive-FFT Algorithm in CLRS In this FFT algorithm (as per CLRS), in line number 4, shouldn't the angle be -2\pi i/n and not +2\pi i/n? The same algorithm is used in cp-algorithms as well, but in python, ... 0 votes 1 answer 131 views ### Finding Aeven(x) and Aodd(x) for a Fast Fourier Transform (FFT) problem? In this article about FFT the author used FFT on this polynomial. A(x) = 3+2x+3x^2+4x^3 Using  A(x)= Aeven(x^2) + xAodd(x^2) the author determined the following for Aeven(x) and Aodd(x)  ... 2 votes 1 answer 750 views ### Using FFT as a black box to solve subset sum. How is this done? Given a set of numbers, S, and a target value T Given a set of numbers, S {s1, s2, ... sn} and a value T, I am looking to determine if any three elements in the set add up to value T. It is valid to have repeats like 2+2+2 would be fine for ... • 21 3 votes 1 answer 195 views ### Computing coefficients of p(x)^n in time O(n \log n) For homework I've to give an algorithm that computes the coefficients of the polynomial p(x)^n in time O(n\log n), where p(x) is a polynomial of degree 7. As an hint I'm told to consider first ... • 217 0 votes 1 answer 83 views ### Multiplying two bivariate polynomials using FFT Consider two bivariate polynomials of degree at most n − 1 in each variable:$$ F(x,y) = \sum_{i,j=0}^{n-1} f_{i,j} x^iy^j \quad\text{and}\quad G(x,y) = \sum_{i,j=0}^{n-1} g_{i,j} x^iy^j $$Show how ... 0 votes 1 answer 278 views ### Multiplication of polynomials in value representation as done for Fast Fourier Transform I am trying to understand the discrete Fast Fourier Transform. I get the idea of switching between coefficient and value representations to and then back but I am stuck in figuring out how the ... 1 vote 1 answer 83 views ### How polynomial interpolation of polynomial multiplication algorithm works? I'm trying to apply the following algorithm from DPV's textbook to an example to see how it works. First, the algorithm is as following: Algorithm [DPV, p. 60] Input: Coefficients of two polynomials. ... • 729 1 vote 0 answers 113 views ### Efficient Fast Fourier Transform to calculate the expected value Suppose two people A and B draw a list of cards with difference scores n = {0, 1, 2, ..., n - 1}. Let i \inn such that i \in [0, n - 1]. Let a_i be the probability that the person A draws a card ... 3 votes 0 answers 84 views ### Multipoint evaluation of a given polynomial You are given a polynomial of degree n. We have to find the value of the polynomial at n different points in O(n(log(n))^2). The answer should be modulo 998244353. I have read various blogs on it and ... 1 vote 1 answer 194 views ### Given an array a, we have to find product of a_{j}-a_{i} modulo 998244353 over all i and j given j>i Given an array a, we have to find product of a_{j}-a_{i} modulo 998244353 over all i and j given j>i. For eg. Let the array be 1,2,3 then my answer will be calculated as- (2-1).(... 1 vote 0 answers 115 views ### Butterfly diagram from Cooley-Tukey algorithm I am trying to understand the logic of this algorithm so I can implement my own but I am not understanding this diagram I see appearing many times in a fair few articles on the topic. I am teaching ... • 147 1 vote 0 answers 64 views ### How to compute the first n coefficients using number theoretic transform (NTT)? I need to find the first n coefficients of$$\prod_{i = 1}^{i = q}(1 + x^{a_i})^{b_i}$$modulo a NTT favourable prime. Can someone suggest an algorithm with worst-case complexity O(n\log n) or O(... • 11 1 vote 0 answers 302 views ### Understanding the recursive fast Fourier Transform Algorithm from CLRS Consider the following recursive fast Fourier transform algorithm from CLRS: I believe that I understand this algorithm correctly: you split the input coefficients into the odd and even terms, ... 1 vote 0 answers 54 views ### Optimization of modular exponentiation using fft [duplicate] My math/cs professor said it is trivial to optimize a modular exponentiation (a^b \bmod c) problem using fft, yet I am not able to understand how to do this. I found 3 papers on this ([1], [2], ... • 29 1 vote 0 answers 261 views ### Optimization of modular exponentiation using fft My math prof said it is trivial to optimize a modular exponentiation (a^b mod c) problem for large values using fft, but I can't figure out how to do this. I looked it up and found a few papers on it (... • 29 0 votes 0 answers 287 views ### Multiplying bivariate polynomials using FFT Consider two bivariate polynomials of degree at most n-1 in each variable:$$ F(x,y) = \sum_{i,j=0}^{n-1} f_{i,j} x^i y^j \quad \text{and} \quad G(x,y) = \sum_{i,j=0}^{n-1} g_{i,j} x^i y^j.  ...
• 1
I came across the following problem. Given a set of $n$ positive integers $A$ and an integer $k$. Let $S$ be the set of integers that are the sum of $k$ distinct integers in $A$. Mathematically ...