box's blog

[Tutorial] Generalized Chirp Z-Transform
By box, history, 4 years ago, In English

My last blog was a bit too esoteric

This blog assumes that you can do a basic convolution (e.g. FFT). After I saw that many people did not know how to do Chirp Z-Transform with arbitrary exponents fast from my blog 9 weeks ago I decided to shitpost write a short tutorial on it.

Let's say we have a polynomial $$$P(x)$$$, such that

$$$\begin{align}P(x)=\sum_{i=0}^{n-1}a_ix^i\end{align}$$$

Now, let's say we have $$$c$$$ and $$$m$$$, and we want to find $$$P(c^0),P(c^1),P(c^2),\dots,P(c^m)$$$. Let $$$b_j=P(c^j)$$$. Consider the implications of having $$$x$$$ as such a form:

$$$\begin{align}b_j=\sum_{i=0}^{n-1}a_ic^{ij}\end{align}$$$

Tinkering around with different expressions for $$$ij$$$, one finds that $$$ij=\frac{(i+j)^2}{2}-\frac{i^2}{2}-\frac{j^2}{2}$$$. This means that

$$$\begin{align}b_j=\sum_{i=0}^{n-1}a_ic^{\frac{(i+j)^2}{2}-\frac{i^2}{2}-\frac{j^2}{2}}\end{align}$$$
$$$\begin{align}b_jc^{\frac{j^2}{2}}=\sum_{i=0}^{n-1}(a_ic^{-\frac{i^2}{2}})c^{\frac{(i+j)^2}{2}}\end{align}$$$

Hence we can find $$$b_j$$$ from the difference-convolution of $$$a_ic^{-\frac{i^2}{2}}$$$ and $$$c^{\frac{i^2}{2}}$$$. However, in many cases — especially when working under a modulus — we can't find the $$$c^{\frac{i^2}{2}}$$$ as $$$i$$$ may be odd. We use a workaround: $$$ij=\binom{i+j}{2}-\binom{i}{2}-\binom{j}{2}$$$. Proof:

$$$ij=\binom{i+j}{2}-\binom{i}{2}-\binom{j}{2}$$$
$$$ij=\frac{(i+j)(i+j-1)}{2}-\frac{(i)(i-1)}{2}-\frac{(j)(j-1)}{2}$$$
$$$2ij=(i+j)(i+j-1)-(i)(i-1)-(j)(j-1)$$$
$$$2ij=(i)(i+j-1)+(j)(i+j-1)-(i)(i-1)-(j)(j-1)$$$
$$$2ij=(i)((i+j-1)-(i-1))+(j)((i+j-1)-(j-1))$$$
$$$2ij=(i)(j)+(j)(i)$$$

Modifying our formula a bit, we get

$$$\begin{align}b_jc^{\binom j2}=\sum_{i=0}^{n-1}(a_ic^{-\binom i2})c^{\binom{i+j}2}\end{align}$$$

As for implmentation details, notice that

$$$\begin{align}b_jc^{\binom j2}=\sum_{i=0}^{n-1}(a_{(n-(n-i))}c^{-\binom{n-(n-i)}2})c^{\binom{i+j}2}\end{align}$$$

Define $$$C_i=a_{n-i}c^{-\binom{n-i}2}$$$; $$$D_i=c^{\binom i2}$$$. We hence have

$$$b_jx^{\binom j2}=\sum_{i=0}^{n-1}C_{n-i}D_{i+j}$$$
$$$b_j=x^{-\binom j2}(C*D)_{n+j}$$$

(the second through definition of convolution)

You can test your implementations here, mod 998244353 and here, mod 10^9+7, although note that the second one is both intense in precision and constant factor.

My code for the former

This method can be used to cheese 1184A3 - Heidi Learns Hashing (Hard) and 1054H - Epic Convolution, and is also a core point in 901E - Cyclic Cipher.

  • Vote: I like it
  • +146
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +35 Vote: I do not like it

Thanks, I didn't really understand the trick before! By the way:

1) Maybe you want to replace $$$x$$$ with $$$c$$$ in all equations since we're trying to find $$$P(c^0), P(c^1), \dots, P(c^m)$$$? I got a bit confused when I saw $$$x^{\binom{i+j}{2}}$$$ and I didn't understand why it wasn't a polynomial of huge degree.

2) Just as a sidenote, a graphical proof of $$$ij = \binom{i+j}{2} - \binom{i}{2} - \binom{j}{2}$$$. Each triangle of side $$$x$$$ contains $$$\binom{x+1}{2}$$$ items. Now, we get that rectangle = huge triangle - '%' triangle - '@' triangle:

        %
       %% j-1
      %%%
     ....
    @....
   @@....
  @@@.... i
 @@@@....
@@@@@....
 i-1  j
→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    1) Thank you for the suggestion! It is a bit unclear, and I have changed all of the incorrect $$$x$$$ es.

    2) I didn't think of this interesting geometrical interpretation. This is a cool different and simpler method of proving the identity :)

    → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +19 Vote: I do not like it

Maybe someone wants another proof for $$${i+j \choose 2} = {i \choose 2} + {j \choose 2} + ij$$$.

LHS: $$${i+j \choose 2}$$$ counts the number of unordered pairs we can pick from $$$\{1, 2, \dots, i+j\}$$$.

RHS: $$${i \choose 2}$$$ counts the number of unordered pairs which only use numbers from $$$A = \{1, 2, \dots, i\}$$$. $$${j \choose 2}$$$ counts the number of unordered pairs which only use numbers from $$$B = \{i+1, i+2 \dots, i+j\}$$$. Now the only pairs we haven't counted yet are of the form $$$\{ x, y \}$$$ where $$$x \in A \wedge y \in B$$$. $$$A$$$ and $$$B$$$ are disjoint so this is just $$$|A| \cdot |B| = ij$$$.

→ Reply