10
votes
Show how to do FFT by hand
Define the polynomials, where deg(A) = q and deg(B) = p. The deg(C) = q + p.
In this case,...
- 101
3
votes
Expected Behavior of FFT
In polar coordinates, $(0,x) = (0,y)$ for any $x$ and $y$, so there's no issue. You've simply used a representation that has multiple representations of the complex number $0 + 0i$.
Going beyond your ...
- 12.1k
3
votes
Accepted
Expected Behavior of FFT
Zero-padding is used to compute longer FFT, in your case the signal is padded to be power of 2. In fact, there is no need to do so, there are FFT available using different lengths (also prime ones).
...
- 9,495
3
votes
Accepted
Calculating force between n points placed on the x-axis
Suppose that the charges are $q_1,\ldots,q_n$. You need to calculate, for all $i$,
$$
F_i = q_i \sum_{j>i} \frac{q_j}{(i-j)^2} - q_i \sum_{j<i} \frac{q_j}{(i-j)^2}.
$$
In matrix form, we get
$$
\...
- 278k
3
votes
Complexity of polynomial interpolation
Fast polynomial interpolation and Fast polynomial evaluation are algorithms that seem to be discovered back in 1973. They allow to interpolate/evaluate polynomial at N arbitrary points as far as field ...
- 1,988
2
votes
Distribution of random Fourier coefficients
Each Fourier coefficient on its own is the average of $2^n$ independent uniformly random $\pm1$ variables. Its distribution is roughly normal with mean $0$ and variance $2^{-n}$.
- 278k
2
votes
Accepted
What's the connection between the two "Fast Walsh Transform"?
Suppose that $A$ and $B$ are vectors of length $n$, where $n$ is a power of 2. We index $A$ and $B$ using binary vectors of length $\log_2 n$, and define their convolution $C$ as
$$
C_i = \sum_{j \...
- 278k
2
votes
Explaining why FFT is faster than DFT for the general public?
What does a Fourier transformation do? It takes a sequence of values, like the sound volume recorded on a CD with 44,100 values per second, and transforms it into frequencies. That is very useful for ...
- 31.5k
1
vote
2D fourier transform
It has same meaning as the 1d Fourier transform: the magnitude and phase of waves that, when superimposed, reconstruct your original signal. In one dimension,
the signal is (usually) a function of ...
- 173
1
vote
How does each element in the output array of a DFT correspond to a specific frequency?
Let us denote the input signal by $x(0),\ldots,x(n-1)$ and the output signal by $y(0),\ldots,y(n-1)$. Your program is using the following formula:
$$
y(k) = \sum_{t=0}^{n-1} e^{-2\pi i tk/n} x(t).
$$
...
- 278k
1
vote
Check for common element in two arrays using FFT
This one is a bit esoteric, but:
$$
\prod_{1\leq i,j \leq n} (x_i-y_j)
$$
Could be decomposed to (as noted by @NotDijkstra)
$$
\prod_{i=1}^{n} p(x_i)
$$
where
$$
p (x) = \prod_{j=1}^{n} (x - y_j)
$$
...
- 243
1
vote
Difference between the Magnitude and the Phase Spectrum of the Fourier Transform?
Fourier Transform changes basis from time (spatial data) to frequency. To encode frequency we need amplitude (magnitude) to know how strong is signal at given frequency and phase to know when sine ...
- 9,495
1
vote
What are 'Butterfly Combinations' and why are they called this way?
So, a summary of the Wikipedia page on Butterfly Diagrams:
In Computing Science, a Butterfly is the portion of a computation that combines the results of (two) smaller computations into the larger ...
- 123
1
vote
What is the significance of the imaginary parts in the output of an Inverse Fourier Transform? Can I avoid them?
The Fourier Transform is the change of basis, the discrete signal from image, which is finite, gets transformed into sines. The transformation itself is prone to rounding, because in frequency domain ...
- 9,495
1
vote
How is this definition of the quantum Fourier transform to be understood?
The index $\mathbf{k}$ goes over all vectors in $\{0,1\}^n$ (which can be identified with $\mathbb{Z}_2^n$). The index $\mathbf{x}$ also has the same range, and $\mathbf{k} \cdot \mathbf{x} = \sum_{i=...
- 278k
1
vote
Explaining why FFT is faster than DFT for the general public?
Here is an attempt.
The Fourier transform decomposes a signal into superimposed sine waves of various frequencies (this can be demonstrated visually).
It turns out that we can find out the strength of ...
- 278k
Only top scored, non community-wiki answers of a minimum length are eligible