w33z8kqrqk8zzzx33's blog

By w33z8kqrqk8zzzx33, history, 7 weeks ago,

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.

• +146

 » 7 weeks ago, # |   +35 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 
•  » » 7 weeks ago, # ^ | ← Rev. 2 →   +3 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 :)
 » 6 weeks ago, # | ← Rev. 2 →   +19 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$.