The Butterfly and Bit Reversal

Direct evaluation costs $n^2$. This note replaces it with a network of $\frac{n}{2}\log_2 n$ small operations, and runs the whole network by hand for $n = 4$.

01.The butterfly

The recursive split from Evaluation and Interpolation bottoms out in one repeated operation. Two values go in, a constant multiplies one of them, and two values come out.

Given two coefficients $A$ and $B$ and a twiddle factor $t$, the Cooley-Tukey butterfly computes

$$A' \;=\; A + t \cdot B, \qquad B' \;=\; A - t \cdot B .$$

The name comes from the shape of the data-flow diagram: two lines in, two lines out, crossing in the middle.

One multiplication, one addition, one subtraction. That is the whole primitive, and it is what a hardware NTT engine is built out of. Everything else in an accelerator exists to feed butterflies with the right operands.

02.Counting them

The transform has $\log_2 n$ levels, since each level halves the problem. Each level performs $n/2$ butterflies, since each butterfly consumes two of the $n$ values.

So the total is

$$\frac{n}{2}\log_2 n$$

butterflies, each with one multiplication.

At $n = 4$: $2 \times 2 = 4$ butterflies. At $n = 256$: $128 \times 8 = 1024$.

Compare with the $n^2$ of direct evaluation: $16$ at $n = 4$, and $65{,}536$ at $n = 256$. The first pair is a tie. The second is a factor of sixty-four.

The whole network for $n = 4$

Run it on the running example, $q = 17$, $\zeta = 2$, $a = (3, 1, 4, 2)$, which The Negacyclic NTT transformed by direct evaluation to $(3, 16, 1, 9)$.

The twiddle factors are powers of $\zeta$, stored in a small table in bit-reversed order. For $n = 4$ that table is

$$(\zeta^0, \zeta^2, \zeta^1, \zeta^3) \;=\; (1,\; 4,\; 2,\; 8) \pmod{17},$$

and where that ordering comes from is the last section of this note.

Level 1. Two butterflies, both with twiddle $t = 4$, pairing entries two apart.

First, $A = a_0 = 3$ and $B = a_2 = 4$:

$$t \cdot B = 4 \cdot 4 = 16, \qquad A' = 3 + 16 = 19 \equiv 2, \qquad B' = 3 - 16 = -13 \equiv 4 \pmod{17}.$$

Second, $A = a_1 = 1$ and $B = a_3 = 2$:

$$t \cdot B = 4 \cdot 2 = 8, \qquad A' = 1 + 8 = 9, \qquad B' = 1 - 8 = -7 \equiv 10 \pmod{17}.$$

After level 1 the array holds $(2,\; 9,\; 4,\; 10)$.

Level 2. Two butterflies with different twiddles, now pairing adjacent entries.

First, $A = 2$ and $B = 9$ with $t = 2$:

$$t \cdot B = 18 \equiv 1, \qquad A' = 2 + 1 = 3, \qquad B' = 2 - 1 = 1 .$$

Second, $A = 4$ and $B = 10$ with $t = 8$:

$$t \cdot B = 80 \equiv 12, \qquad A' = 4 + 12 = 16, \qquad B' = 4 - 12 = -8 \equiv 9 \pmod{17}.$$

After level 2 the array holds

$$(3,\; 1,\; 16,\; 9).$$

Four butterflies, four multiplications, done.

04.Where the output ordering went

Compare that with the direct evaluation result:

$$\text{butterflies: } (3,\; 1,\; 16,\; 9), \qquad \text{direct: } (3,\; 16,\; 1,\; 9).$$

The two middle entries are swapped.

This is not an error. The fast algorithm produces its output in bit-reversed order, and the swap is exactly that.

Write each index in binary using $\log_2 n = 2$ bits, and reverse the bits:

So position $1$ of the fast output holds what direct evaluation put at position $2$, and vice versa. Positions $0$ and $3$ are fixed points and do not move. That is precisely the observed swap.

The reason is structural. The recursion repeatedly separates even-indexed from odd-indexed coefficients. After $\log_2 n$ rounds of that separation, an element's final position is determined by its index bits read in the opposite order.

05.Why nobody fixes it

The natural instinct is to add a reordering pass and restore the natural order. Implementations deliberately do not.

The reason is that the ordering cancels. Pointwise multiplication does not care what order the values are in, as long as both operands use the same order, since it multiplies position by position. And the inverse transform can be written to consume bit-reversed input and produce natural-order output.

So the standard arrangement is a forward transform that takes natural order to bit-reversed order, pointwise multiplication in bit-reversed order, and an inverse transform that takes bit-reversed order back to natural. The permutation appears and disappears without a single element ever being moved.

That saves a full pass over memory in each direction, which on a memory-bound workload is a real saving rather than a micro-optimisation. It is also why reading NTT code for the first time is confusing: the arrays are permuted for most of the computation and nothing in the code says so.

06.In place

One more property, which matters most to hardware.

Look again at the butterfly. It reads $A$ and $B$, and writes $A'$ and $B'$. Once both outputs are computed, the inputs are never needed again, so the outputs can be written back over them.

The whole transform therefore runs in place, using the original array and a couple of temporaries. No second buffer of size $n$ is needed at any point.

For a hardware accelerator working with limited on-chip memory, that is close to decisive. A length-$256$ transform over $12$-bit coefficients needs a single $256 \times 12$-bit memory, and the datapath is one butterfly unit reading two values, multiplying by a twiddle from a small ROM, and writing two values back. Everything else in the design is control logic deciding which addresses to read and which twiddle to use.

The next note gives the actual roots and dimensions that logic is built around.