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

9 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
45 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 ...
35 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 118 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 99 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 (... 1answer 22 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.$$ ...