# 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.

10 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
46 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 ...
45 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 \in$n such that $i \in [0, n - 1].$ Let $a_i$ be the probability that the person A draws a card ...
37 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 ...
53 views

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(... 0answers 123 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, ... 0answers 103 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 (... 0answers 48 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, ... 1answer 38 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) ...
I have a linear equation $Cx=b$ where $C$ is $n \times n$ circulant matrix. By applying circular convolution process, vector $x$ can be solved using Fast Fourier Transform (FFT) to transform the ...
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.$$ ...