GitXplorerGitXplorer
C

algorithms

public
2 stars
0 forks
0 issues

Commits

List of commits on branch master.
Unverified
d01f6198b4018ebc0fffd77dd7641b8df63a9b1f

add reference & fix typo

CCzxck001 committed 6 years ago
Unverified
93e7288da4fd6d98f06083753a3fa76967ee4e07

Render the equations in README.md

CCzxck001 committed 6 years ago
Unverified
3c642cd9a5eb700b105d4ba464b029ab288efb8b

add Torvalds' good taste code about traverse linked list

CCzxck001 committed 7 years ago
Unverified
ffb76cc61f1a72c30436a2496c60dadc6fc2a497

degrade permissions of some source files

CCzxck001 committed 7 years ago
Unverified
0978076496f600fe92fdb1dd2b78f64c1a0b7216

add sample code for mono queue and mono stack.

CCzxck001 committed 7 years ago
Unverified
4ba41a0d29521bc0569452cc392ebac1afea3a24

fix typos in FFT algorithm description

CCzxck001 committed 7 years ago

README

The README file for this repository.

algorithms

Cool algorithms + implementations.

FFT in a nutshell

Crucial Feature of DFT

Discrete Fourier Transform (DFT) is defined as the discrete Z-transform sampled at each root of unity.

$ F(k) = \sum_{n=0}^N f(n) z^n = \sum_{n=0}^N f(n) U_N^{nk}​$

where $U_N = \exp(\frac{2\pi i}{N})$ is the N-th root of unity.

It has the following feature, which leads to Fast Fourier Transform (FFT) algorithm:

$F(k) = F_e(k) + U_N^k F_o(k),​$

where $F_e(k) = \sum_{n=0}^{N/2} f(2n) U_{N/2}^{nk}$, $F_o(k) = \sum_{n=0}^{N/2} f(2n+1) U_{N/2}^{nk}$.

The $F_e(k)$ and $F_o(k)$ are defined and can be calculated by recursively applying FFT to even and odd subsequences of original signal $f(t)​$.

Proof

Replacing $U_{N/2}​$ in $F_e(k)​$ and $F_o(k)​$ by the following observation:

$U_{N/2}^n = U_N^{2n}$

we'll get

$ F_e(k) =\sum_{n=0}^{N/2} f(2n) U_N^{2nk},$

$ F_o(k) = \sum_{n=0}^{N/2} f(2n+1) U_N^{2nk},$

$U_N^n F_o(k) = \sum_{n=0}^{N/2} f(2n+1) U_N^{(2n+1)k},​$

We now see that $F_e(k)​$ consists of even terms of $F(k)​$, and $U_N^kF_o(k)​$ consists of odd terms of $F(k)​$. QED.

A Detail of Implementation

Originally $F_e(k)$ and $ F(k)$are both arrays of length $N/2$. However, in the last step we need to add the corresponding element from both into $F(k)$ of length $N$.

The key is the fact that $F_e(k)$ and $F_o(k)$ are both $N/2$ periodical. So, $F_e(k) = F_e(k - N/2)$. This also holds for $F_o(k)$. We can calculate $F(k)​$ like this:

int M = N / 2;
for (int k = 0; k < N; k++) {
  F[k] = Fe[k % M] + RU(k, N) * Fo[k % M];
}