text:
\section{Computing the bit-reversed TFT by way of the cyclotomic TFT}\label{sec:affine}

The bit-reversed TFT has the property that, for $m<n$, $\TFT_\omega^m(f)$ is merely the first $m$ entries of $\TFT_\omega^n(f)$, whereas the cyclotomic TFT does not, in general.  Hence the bit-reversed TFT lends itself more readily to multivariate polynomial arithmetic.  We show how an algorithm for computing the cyclotomic TFT may be modified to compute a bit-reversed TFT.

As before, let $N=2^p>n=\sum_{i=1}^s n_i = \sum_{i=1}^s 2^{n(i)}$, $\omega \in \mathcal{R}$ be an $N\th$ principal root of unity, and let $\omega_i = \omega^{N/2n_i}$ be a root of $\Phi_i$.  Define
\begin{equation}
\Omega_i = \prod_{l=1}^{i}\omega_l \hspace{0.5cm}\text{ and }\hspace{0.5cm} \Psi_j(z) = z^{n_j} - \Omega_{j-1}^{n_j}
\end{equation}
for $0 \leq i \leq s$, $0 < j \leq s$.  $\TFT_{\omega,n}(f)$ is comprised of the evaluation of $f(z)$ at the roots of the polynomials $\Psi_j(z)$.  If $n_1 + \dots + n_{j-1} \leq l < n_1 + \dots + n_{j}$, we have that $\omega^{[l]_p}$ is a root of $\Psi_j$.  To see this, write $l = n_1 + \dots + n_{j-1} + l'$, $0 \leq l' < n_j$, and observe that
\begin{align}
\omega^{[l]_p n_{j}} &= \omega^{(N/n_1 + \dots + N/n_{j-1})n_j}\omega^{[ l ]_p n_j} \\
&= (\omega_1 \cdots \omega_j)^{n_j} \omega^{[l]_p n_j},\\
&= \Omega_{j-1}^{n_j}\omega^{[l]_p n_j} \label{eqn:OMEGA}
\end{align}
As $l'<n_j$, $\omega^{[l']_p}$ has order dividing $n_j$, and so \eqref{eqn:OMEGA} is precisely $(\Omega_{j-1})^{n_j}$.  Every $n_j-th$ root of unity in $\mathcal{R}$ is of the form $\omega^{[k]_p}$, where $0 \leq k < n_j$.  In particular $\omega^{[l']_p}$ is an $n_j-th$ root of unity.  Thus $\omega^[l]_p\omega^{[l']_p}$ is a root of $\Psi_j$.  As the binary representations of $n_1 + \dots + n_{j-1}$ and $l'$ do not share any $1$ digits at the same precision,
\begin{equation}
[n_1 + \dots + n_{j-1}]_p + [l']_p = [l]_p,
\end{equation}
and so $\omega^{[l]_p}$ is a root of $\Psi_j$.

Consider the affine transformation $z \mapsto \Omega_{s}z$.  Then
\begin{align}
\Psi_i( \Omega_s z) &= \Omega_s^{n_i}\left(z^{n_i} - \Omega_{i-1}^{n_i}\right) \\
 & = \Omega_{i-1}^{n_i}\left( \prod_{j=i}^s \omega_j^{n_i} \right)\left( z^{n_i} - \Omega_{i-1}^{n_i} \right)\\
 & = -\Omega_{i-1}^{n_i}\left( z^{n_i} + 1\right) = -\Omega_{i-1}^{n_i}\Phi_i.
\end{align}

Thus, for a polynomial $f(z)$, $f(z) \bmod \Phi_i(z) = f(z) \bmod \Psi_i( \Omega_s z)$.  We can break $f(z)$ into its images modulo the polynomials $\Phi_i$ as follows:
\begin{enumerate}
\item Replace $f(z)$ with $f( \Omega_s z)$.
\item Break $f( \Omega_s z)$ into its images modulo $\Phi_i(z)$ per a cyclotomic TFT method.  Equivalently, this gives us the images $f( \Omega_sz ) \bmod \Psi_i( \Omega_s z)$.
\item Apply the transformation $z \mapsto \Omega_s^{-1}z$ to each image to give us $f(z) \bmod \Psi_i(z)$ in place of $f( \Omega_s z) \bmod \Psi_i( \Omega_s z)$.
\end{enumerate}

Note that the affine transformations of steps 1 and 3 both have complexity $\mathcal{O}(n)$.  We can get $\TFT_{\omega,n}(f)$ from the images $f \bmod \Phi_i$ by applying a DWT to each image $f \bmod \Phi_i$.  As each step here is invertible, we can invert a bit-reversed TFT using an inverse cyclotomic TFT algorithm.  We can similarly invert a bit-reversed TFT using an inverse cyclotomic TFT algorithm.
\subsection{The Fast Fourier Transform}

We can compute the discrete Fourier transform of $f(z)$, $f$ reduced modulo $(z^n-1)$, by way of a {\em Fast Fourier Transform} (FFT).  The FFT is believed to have been first discovered by Gauss, but did not become well-known until it was famously rediscovered by Cooley and Tukey \cite{CT}.  For a detailed history of the FFT we refer the reader to \cite{history}.

There are many variants of the FFT.  We describe the {\em radix-2} Cooley-Tukey FFT in terms of modular reductions.   Let $n$ be a power of two.  We break $f$ into images modulo polynomials of decreasing degree until we have the images $f \bmod (z-\omega^i) = f(\omega^i)$, $0 \leq i < n$.  At the start of the first iteration we have $f$ reduced modulo $z^n-1$.  After $i$ iterations, we will have the $2^i$ images
\begin{equation}
f \bmod z^{u}-\omega^{ju}, \hspace{0.4cm}\text{ for } 0 \leq j < n/u.
\end{equation}
If $i=\log_2 n$ this gives us the DFT of $f$.  Consider then the image $f' = f(z) \bmod z^{2u} - \omega^{2ju} = \sum_{i=0}^{2u-1}b_i$, for some $j$, $0 \leq j < \tfrac{n}{2u}$.  We break this image into two images $f_0$ and $f_1$, where
\begin{align}
f_0 &= f' \bmod (z^{u} - \omega^{ju}), \text{and} \\
f_1 &= f' \bmod (z^{u} + \omega^{ju}) = f' \bmod (z^u - \omega^{ju + n/2}),
\end{align}
If we write $f' = \sum_{k=0}^{u-1}b_kz^k$, then we can write $f_0$ and $f_1$ in terms of the coefficients $b_k$:
\begin{equation}
f_0 = \sum_{k=0}^{u-1}(b_k + \omega^{v}b_{k+u} )z^k, \hspace{0.4cm} f_1 = \sum_{k=0}^{u-1}(b_k - \omega^{v}b_{k+u})z^k.
\end{equation}
thus, given an array containing the coefficients $b_k$ of $f'$, we can write $f_0$ and $f_1$ in place of $f'$ by way of operations
\begin{equation}\label{eqn:rad2fft}
(b_k, b_{k+u}) \leftarrow (b_k + \omega^{ju}b_{k+u}, b_k - \omega^{ju}b_{k+u}), \hspace{0.4cm} 0 \leq i \leq u
\end{equation}
The pair of assignments \eqref{eqn:rad2fft} are known as a {\em butterfly operation}.  Note $f_0$ and $f_1$ are in the same form as $f'$, and if $u>1$ we can break those images into smaller images in the same fashion.  Starting this method with $f \bmod (z^n-1)$, will give us $f \bmod (z-\omega^j) = f(\omega^j)$, for $0 \leq j < n$.

If the butterfly operations are performed in place, the resulting evaluations $f(\omega^j)$ will be written in {\em bit-reversed} order.  More precisely, if we let $\rev_c(j)$ denote the integer resulting from reversing the first $c$ bits of $j$, we have that $f(\omega^j)$ will be written in place of $a_{k}$, where $k=\rev_{\log(n)}(j)$ and $\log$ is taken to be base-2 throughout.  As an example,
\begin{equation}
\rev_5(11) = \rev_5({\tt 01011}_2) = {\tt 11010}_2 = 16+8+2=26.
\end{equation}

\begin{procedure}
	\caption{FFT(\textbf{a}, $n$, $\omega$), an in-place implementation of the radix-2 Cooley-Tukey FFT}\label{proc:FFT}
	\KwIn{
		\begin{itemize}[noitemsep,nolistsep]
			\item  $\textbf{a} = (\textbf{a}(0), \dots, \textbf{a}(n-1))$, an array containing a vector $a \in\mathcal{R}^n$.
			\item  $\omega$, a root of $z^n-1$, for $n$ a power of two.
		\end{itemize}
	}
	\KwResult{ $\DFT_\omega^n(a)$ is written to the array ${\bf a}$ in bit-reversed order.  }\vspace{0.3cm}

	\For{$i \longleftarrow 1$ \KwTo $\log_2(n)$}{

		$u \longleftarrow n/2^i$\\

		\For{$j \longleftarrow 0$ \KwTo $\tfrac{n}{2u}-1$}{
			$t \longleftarrow \rev_i(j)u$\\
			%
			\For{$k \longleftarrow 0$ \KwTo $u-1$ }{
				\tcp{Butterfly operations \eqref{eqn:rad2fft}}
				$\left[\begin{matrix} {\bf a}(t+k) \\ {\bf a}(t+k+u)\end{matrix}\right] \longleftarrow \left[\begin{matrix} 1 & \omega^{ju} \\ 1 & -\omega^{ju}\end{matrix}\right]\left[\begin{matrix} {\bf a}(t+k) \\ {\bf a}(t+k+u)\end{matrix}\right]$ \\
				\label{line:butterfly}
			}

		}
	}
\end{procedure}

\begin{procedure}
	\caption{IFFT(\textbf{a}, $n$, $\omega$), an in place implementation of the inverse-FFT }\label{proc:IFFT}
	\KwIn{ $\textbf{a} = (\textbf{a}(0), \dots, \textbf{a}(n-1))$, an array containing $\DFT_{\omega}^n(a)$, for a vector $a \in \mathcal{R}^n$, for $n$ a power of two, in bit-reversed order.
	}
	\KwResult{ The vector $a$ is written to array ${\bf a}$ in place of its DFT. }\vspace{0.3cm}

	\For{$i \longleftarrow 1$ \KwTo $\log_2(n)$}{
		$u \longleftarrow n/2^i$\\

		\For{$j \longleftarrow 0$ \KwTo $\tfrac{n}{2u}-1$}{
			$t \longleftarrow \rev_{i}(j)\tfrac{n}{2u}$\\
			\For{$k \longleftarrow 0$ \KwTo $u-1$}{
				\tcp{Butterfly operations \eqref{eqn:rad2fft}}
				$\left[\begin{matrix} {\bf a}(t+\tfrac{kn}{u} ) \\ {\bf a}( t+\tfrac{kn}{u}+ \tfrac{n}{2u}) \end{matrix}\right] \longleftarrow
				\left[\begin{matrix} 1 & \omega^{-ju} \\ 1 & -\omega^{-ju}\end{matrix}\right]$
				$\left[\begin{matrix} {\bf a}(t+\tfrac{kn}{u} ) \\ {\bf a}( t+\tfrac{kn}{u}+ \tfrac{n}{2u}) \end{matrix}\right]$

			}
		}
	}\vspace{0.3cm}

	\lFor{$i \longleftarrow 0$ \KwTo $n-1$}{ $\textbf{a}(i) \longleftarrow \tfrac{1}{n}{\bf a}(i)$ }

\end{procedure}

Procedures {\tt\ref{proc:FFT}} and {\tt\ref{proc:IFFT}} describe implementations of this in-place FFT and its inverse.  {\tt\ref{proc:IFFT}} computes the inverse as $\tfrac{1}{n}\DFT_\omega^n$, and requires that the input is in bit-reversed order.

Normally one would pre-compute powers of $\omega$ and store them in an array in bit-reversed order.  To avoid this space overhead we perform the butterfly operations in an order such that we can compute the required powers of $\omega^m$ sequentially.  For better memory performance, one can produce the powers of $\omega$ in an order that allows us to traverse the array in sequential order, at the cost of an additional $\mathcal{O}(n)$ ring multiplications.

Our only ring operations required are those in butterfly operations (line \ref{line:butterfly}) and the computation of the powers of $\omega^{ju}$.  $\omega^u$ can be computed by a square-and-multiply approach using $\mathcal{O}(\log u)$ multiplications.  Enumerating these operations gives us the following cost:

\begin{lem}
Let $n$ be a power of two and let ${\bf a}$ be an array containing the coefficients of a polynomial $f(z)$ reduced modulo $(z^n-1)$.  Computing $\DFT_{\omega}^n(a)$ by way of procedure {\tt\ref{proc:FFT}}, requires $n\log n + \mathcal{O}(1)$ additions and $\tfrac{1}{2}n\log n + \mathcal{O}(n)$ multiplications in $\mathcal{R}$.  Procedure ${\tt\ref{proc:IFFT}}$ has similar complexity.
\end{lem}

The approach described for $n$ a power of two generalizes for $n$ a prime power or a product of small primes, though in practise $n$ is almost always chosen to be a power-of-2.

Using the radix-2 FFT, if $d = \deg(fg)$, we choose $n$ to be the least power of $2$ exceeding $d$.  This entails appending zeros to the input arrays $a$ and $b$.  By this method, computing a product of degree $2^k$ requires the same time and space cost as computing a product of degree $2^k+m$, for $0 \leq m < 2^k$.  It would be preferable to have a radix-2 FFT algorithm whose time cost grows smoothly relative to $n$, and which requires $n+\mathcal{O}(1)$ space for arbitrary integers $n>0$, and not just for $n$ a power of two.  Crandall's {\em devil's convolution} algorithm \cite{scicomp} somewhat flattens these jumps in complexity, though not entirely.  It works by reducing a discrete convolution of arbitrary length into more easily computable convolutions.  More recently, truncated Fourier transform (TFT) algorithms, described hereafter, have addressed this issue.

\section{The cyclotomic TFT}\label{sec:cyclotomicTFT}

\input{ctft_notation}
\input{ctft_dwt}
\input{ctft_mateer}
\subsection{Discrete Weighted Transforms}

Given the images $f_i = f \bmod \Phi_i$, one can evaluate $f$ at the roots of $\Phi_i$ by way of a {\em Discrete Weighted Transform} (DWT), which comprises an affine transformation followed by an FFT \cite{DWT}.

In a more general setting, suppose we have an image $f^* = f(z) \bmod (z^N-c)$, where $N$ is a power-of-two.  Assuming $c$ has an $N\th$ root over our ring $\mathcal{R}$, the roots of $f(z)$ are all of the form $c^{1/N}\gamma^i$, $0 \leq i < N$, where $\gamma$ is an $N\th$ primitive root of unity.  Thus to evaluate $f$ at the roots of $(z^N-c)$ one can replace $f^*(z)$ with $f^*(c^{1/N}z)$, and then compute $\DFT_{\gamma}( f^*(c^{1/N}z))$.  Replacing $f^*(z)$ with $f^*(c^{1/N}z)$ merely entails multiplying the degree-$k$ term of $f^*$ by $c^{k/N}$, for $0 \leq k < N$.  This, combined with computing the powers of $c^{1/N}$ sequentially, entails fewer than $2N$ ring multiplications.

Thus, to evaluate $f$ at the roots of $\Phi_i(z) = z^{n_i}-\omega_i^{n_i}$, one would write $f_i( \omega_i z )$ in place of $f_i(z)$, then compute $\DFT_{\omega_i^2}( f_i( \omega_i z) )$ by way of the FFT.  As both the FFT and the affine transformation are invertible, a Discrete Weighted Transform is easily invertible as well.

\begin{procedure}
	\caption{DWT(\textbf{a}, $N$, $\omega$, $v$), the Discrete Weighted Transform}\label{proc:DWT}
	\KwIn{
		\begin{itemize}[noitemsep,nolistsep]
			\item  $\textbf{a} = (\textbf{a}_0, \dots, \textbf{a}_{N-1})$, an array containing the coefficients of $f(z)=\sum_{i=0}^{N-1}a_iz^i \in \mathcal{R}[z]$.
			\item  $\omega \in \mathcal{R}$, an $N\th$ principal root of unity.
			\item  $v \in \mathcal{R}$, a weight.
		\end{itemize}
	}
	\KwResult{
		$\TFT'_{\omega,n}(f)$ is written in place of $f$
	}

	\lFor{$i \leftarrow 0$ \KwTo $N-1$ }{ $\a_i \longleftarrow v^i\a_i$ }\\
	\ref{proc:FFT}($\a, N, \omega$)
\end{procedure}
\subsection{Mateer's TFT algorithm}

Algorithm \ref{alg:mat} gives a short description of Mateer's algorithm \cite{Todd} for computing $\TFT_{\omega,n}'(f)$.

\begin{algorithm}
\caption{Mateer's algorithm for computing $\TFT_{\omega,n}'(f)$}\label{alg:mat}
\KwIn{
	$n<N$, $f(z) \in \mathcal{R}[z]$, $f$ reduced modulo $z^N-1$
}
\KwResult{ $\TFT'_{\omega, n}(f)$ is written in place of $f$ }
	$(i,K) \longleftarrow (1,N)$\\

	\While{$K > n_s$}{
		Separate $f \bmod (z^K-1)$ into the images $f \bmod (z^{K/2}-1)$ and $f \bmod (z^{K/2}+1)$.\\
		\If{ $K/2 = n_i$}{
			Note $\Phi_i = z^{K/2}+1$.  Use a DWT to write the evaluation of $f$ at the roots of $\Phi_i$ in place of $f_i = f \bmod \Phi_i$.\\
			$i \longleftarrow i+1$
		}
		$K \longleftarrow K/2$
	}

\end{algorithm}

On input we are given $f(z)$ reduced modulo $z^N-1$.  If $N=n=n_1$ we can just perform a DWT on $f$ to get $\TFT_{n,\omega}'(f)$, so suppose $n$ is not a power of two and $n<N$.  We reduce the image into two images $f(z) \bmod (z^{N/2}-1)$ and $f(z) \bmod (z^{N/2}+1)$, in the same manner as described in the FFT.  This process strictly entails ring additions.  If $f(z)=\sum_{i=0}^{N-1}a_iz^i$, then $f_0$ and $f_1$ can be computed by way of $N/2$ butterfly operations.
\begin{align}
f_0(z) &= \sum_{i=0}^{N/2}(a_i + a_{i+N/2})z^i, \\
f_1(z) &= \sum_{i=0}^{N/2}(a_i - a_{i+N/2})z^i.
\end{align}
It should be noted that these particular butterfly operations will not require ring multiplications, as their twiddle factors are all $1$.  As $n_1 = N/2$, we keep the image $f_1 = f \bmod (z^{N/2}+1)$, and use a DWT on $f_1$ to evaluate $f$ at the roots of $\Phi_1$.  We then break $f \bmod (z^{N/2}-1)$ into the images $f \bmod (z^{N/4}-1)$ and $f \bmod (z^{N/4}+1)$ in a similar fashion.  If $n_1 < N/4 < n_2$, we ignore the image $f \bmod (z^{N/4}+1)$ for the remainder of the computation.  We continue in this fashion until we have $f_s = f \bmod (z^{n_s}+1)$, after which we should have $\TFT'_{\omega,n}(f)$ in place of $f$, albeit scattered throughout our array of working space.

Performing the aforementioned modular reductions amounts to $\mathcal{O}(n)$ additions.  Accounting for the cost of the DWTs, we have that the number of multiplications becomes
\begin{equation}
\sum_{i=1}^s \tfrac{1}{2}n_i \log n_i + \mathcal{O}(n_i) < \tfrac{1}{2}n \log n + \mathcal{O}(n).
\end{equation}
A similar analysis for the ring additions due to the DWTs gives us the following complexity:
\begin{Lem}[Mateer]
$\TFT'_{\omega,n}(f)$ can be computed using $\tfrac{1}{2}n \log n + \mathcal{O}(n)$ ring multiplications plus $\mathcal{O}(n \log n)$ ring additions.
\end{Lem}
Since each of the steps of Mateer's method amounts to a series of butterfly operation, the algorithm is invertible with comparable complexity.  One advantage of Mateer's TFT is that inverting it is relatively straightforward: we invert the DWTs and then invert the butterflies.

Mateer's method, however, requires space for $N$ ring elements, as the images $f \bmod (z^{N/2}-1)$ and $f \bmod (z^{N/2}+1)$ may have maximal degree.
\subsection{Notation}

We use the following notation throughout section \ref{sec:cyclotomicTFT} and thereafter.  Suppose now that we have a polynomial $f(z) = \sum_{j=0}^{n-1}a_jz^j \in\mathcal{R}[z]$ of degree at most $n-1$, where $n$ can be any positive integer.  For the remainder of this paper, we write $n$ as
$n = \sum_{i=1}^{s}n_i$, where $n_i = 2^{n(i)}$, $n(i) \in \mathbb{Z}_{\geq 0}$ and $n_i > n_j$ for $1 \leq i < j \leq s$.  Again $N$ is the least power of two at least $n$.  For $1 \leq i \leq s$, we let
\begin{equation}
\Phi_i =  z^{n_i}+1.
\end{equation}

The TFT algorithms of sections \ref{sec:cyclotomicTFT} and thereafter will compute the evaluations of $f(z)$ at the roots of $\Phi_i$.  Namely, if we fix a canonical root $\omega=\omega_1$ of $\Phi_1$, and then let, for $2 \leq i \leq s$, $\omega_i=\omega_1^{n(1)/n(s)}$, a root of $\Phi_i$, these algorithms will compute
\begin{equation}
f(\omega_i^{2j+1})  \hspace{0.5cm}\text{for}\hspace{0.5cm} 0 \leq j < n_i, \hspace{0.5cm} 1 \leq i \leq s.
\end{equation}
It is the evaluation of $f(z)$ at the roots of the cyclotomic polynomials $\Phi_i$.  As such, we will call it here the {\em cyclotomic} TFT and denote it by $\TFT'_{\omega,n}(f)$.  The choice of $\omega$ only affects the ordering of the elements of the cyclotomic TFT.  If we let
\begin{equation}
S(n) = \{ n_i \leq k < 2n_i : 1 \leq i \leq s \},
\end{equation}
then we have that $\TFT'_{\omega,n}$ uses the same set of evaluation points as $\TFT_{\omega, S(n)}(f)$.

The roots of unity used as evaluation points in $\TFT'_{\omega,n}(f)$ will differ from those used in $\TFT_{\omega,n}(f)$.  For instance, $\TFT_{\omega,n}(f)$ will always use all roots-of-unity of order dividing $n_1$, whereas $\TFT'_{\omega,n}(f)$ will instead use all roots of unity of order $2n_1$.  We define, for $1 \leq i \leq s$, the images
\begin{equation}
f_i = f \bmod \Phi_i.
\end{equation}

The algorithms for computing a cyclotomic TFT all follow a similar template: we will produce the images $f_i$ sequentially, and then write the evaluation of $f$ at the roots of $\Phi_i$ in place of each image $f_i$.
\subsection{The Discrete Fourier Transform}

The {\em Discrete Fourier Transform} (DFT) of a polynomial $f(z)$ is its vector of evaluations at the distinct powers of a root of unity.  Specifically, if $f(z) = \sum_{i=0}^{N-1}a_iz^i$ is a polynomial over a ring $\mathcal{R}$ containing an $N\th$ primitive root of unity $\omega$, then we define the discrete Fourier transform of $f(z)$ as
\begin{equation}
\DFT_\omega( f ) = \left( f(\omega^j) \right)_{0 \leq j < N }.
\end{equation}
We treat the polynomial $f$ and its vector of coefficients $a  = ( a_0, a_1, \dots, a_{N-1} )$ as equivalent and use the notation $\DFT_\omega( a )$ and $\DFT_\omega( f )$ interchangeably.  If we take addition and multiplication to be pointwise in $\mathcal{R}^N$, then the map $\DFT_\omega:\mathcal{R}[z]/(z^N-1)\rightarrow \mathcal{R}^N$ forms a ring homomorphism.  If $\omega$ is a {\em principal} root of unity, that is, for $j$ not divisible by $N$, $\sum_{i=0}^{N-1} \omega^{ij} = 0$,
then $\DFT_\omega$ has an inverse map $\IDFT_{\omega} : \mathcal{R}^N \rightarrow \mathcal{R}[z]/(z^N-1)$, defined by
\begin{equation}
\IDFT_{\omega}( \hat{a} ) = \tfrac{1}{N}\DFT_{\omega^{-1}}( \hat{a} ),
\end{equation}
where $\hat{a} \in \mathcal{R}^N$ and we again we treat a polynomial as equivalent to its vector of coefficients.  This suggests a multiplication algorithm for $f,g \in \mathcal{R}[z]$.
\begin{Thm}[The Convolution Theorem]
Suppose $\mathcal{R}$ is a ring containing an $N\th$ principal root of unity $\omega$ and let $f,g \in \mathcal{R}[z]$.  Then
\begin{equation}
fg \bmod (z^N-1) = \IDFT_\omega\left( \DFT_\omega(f)\cdot \DFT_\omega(g) \right),
\end{equation}
where ``$\cdot$'' is the vector component-wise product, and, given two polynomial $g(z), h(z) \in \mathcal{R}[z]$, $g(z) \bmod h(z)$ denotes the unique polynomial $r(z)$ such that $h(z)$ divides $g(z)-r(z)$ and $\deg(r)<\deg(h)$ throughout.
\end{Thm}
Thus to multiply $f$ and $g$, we can choose $N>\deg(fg)$ and an $N\th$ principal root of unity $\omega \in \mathcal{R}$, compute the length-$N$ DFTs of $f$ and $g$, take their pointwise product, and take the inverse DFT of the pointwise product.
\subsection{The discrete Fourier transform and its inverse}

The {\em discrete Fourier transform} (DFT) of a polynomial $f(z)$ is its vector of evaluations at the distinct powers of a root of unity.  Specifically, if $f(z) = \sum_{i=0}^{n-1}a_iz^i$ is a polynomial over a ring $\mathcal{R}$ containing an $n\th$ primitive root of unity $\omega$, then we define the discrete Fourier transform of $f(z)$ as
\begin{equation}
\DFT^n_\omega( f ) = \left( f(\omega^j) \right)_{0 \leq j < n }.
\end{equation}
We treat the polynomial $f$ and its vector of coefficients $a  = ( a_0, a_1, \dots, a_{n-1} )$ as equivalent and use the notation $\DFT_\omega^n( a )$ and $\DFT_\omega^n( f )$ interchangeably.  If we take addition and multiplication to be pointwise in $\mathcal{R}^n$, then the map $\DFT_\omega^n:\mathcal{R}[z]/(z^n-1)\rightarrow \mathcal{R}^n$ forms a ring homomorphism.  If $\omega$ is a {\em principal} root of unity, that is, for $j$ not divisible by $n$, $\sum_{i=0}^{n-1} \omega^{ij} = 0$,
then, $\DFT_\omega^n$ has an inverse map $\IDFT^n_{\omega} : \mathcal{R}^n \rightarrow \mathcal{R}[z]/(z^n-1)$, defined by
\begin{equation}
\IDFT^n_{\omega}( \hat{a} ) = \tfrac{1}{n}\DFT_{\omega^{-1}}( \hat{a} ),
\end{equation}
where $\hat{a} \in \mathcal{R}^n$ and we again we treat a polynomial as equivalent to its vector of coefficients.  This suggests a multiplication algorithm for $f,g \in \mathcal{R}[z]$.
\begin{thm}[The Convolution Theorem]
Suppose $\mathcal{R}$ is a ring containing an $n\th$ principal root of unity $\omega$ and let $f,g \in \mathcal{R}[z]$.  Then
\begin{equation}
fg \bmod (z^n-1) = \IDFT_\omega^n\left( \DFT_\omega(f)\cdot \DFT_\omega(g) \right),
\end{equation}
where ``$\cdot$'' is the vector dot-product, and, given two polynomial $g(z), h(z) \in \mathcal{R}[z]$, $g(z) \bmod h(z)$ denotes the unique polynomial $r(z)$ such that $h(z)$ divides $g(z)-r(z)$ and $\deg(r)<\deg(h)$ throughout.
\end{thm}
Thus to multiply $f$ and $g$, we can choose $n>\deg(fg)$ and an $n\th$ principal root of unity $\omega \in \mathcal{R}$, compute the length-$n$ DFTs of $f$ and $g$, take their pointwise product, and take the inverse DFT of the result.  If $\mathcal{R}$ does not contain such a root of unity $\omega$, we can choose $n>\deg(fg)$ such that $n$ and the characteristic of $\mathcal{R}$ are relatively prime and instead use the ring $\mathcal{R}[w]/(w^n-1)$ containing $n\th$ principal root of unity $w$.
\subsection{The Fast Fourier Transform}

We can compute the Discrete Fourier †ransform of $f(z)$, $f$ reduced modulo $(z^N-1)$, by way of a {\em Fast Fourier Transform} (FFT).  The FFT is believed to have been first discovered by Gauss, but did not become well-known until it was famously rediscovered by Cooley and Tukey \cite{CT}.  For a detailed history of the FFT we refer the reader to \cite{history}.

The simplest and most widely-used FFT, the {\em radix-2} FFT, assumes $N=2^p$ for some $p \in \mathbb{Z}_{\geq 0}$.  We describe the radix-2 FFT in terms of modular reductions.   Let $N$ be a power of two.  We break $f$ into images modulo polynomials of decreasing degree until we have the images $f \bmod (z-\omega^i) = f(\omega^i)$, $0 \leq i < N$.  At the start of the first iteration we have $f$ reduced modulo $z^N-1$.  After $i$ iterations, we will have the $2^i$ images
\begin{equation}
f \bmod (z^{u}-\omega^{uj}), \hspace{0.4cm}\text{ for } 0 \leq j < 2^i,
\end{equation}
where $u=N/2^i$.  If $i=p$ this gives us the DFT of $f$.  Consider then the image $f' = f(z) \bmod (z^{2u} - \omega^{2uj}) = \sum_{i=0}^{2u-1}b_i$, for some $j$, $0 \leq j < \tfrac{N}{2u}$.  We break this image into two images $f_0$ and $f_1$, where
\begin{align}
f_0 &= f' \bmod (z^{u} - \omega^{uj}), \text{ and} \\
f_1 &= f' \bmod (z^{u} + \omega^{uj}) = f' \bmod (z^u - \omega^{uj + N/2}),
\end{align}
If we write $f' = \sum_{k=0}^{u-1}b_kz^k$, then we can write $f_0$ and $f_1$ in terms of the coefficients $b_k$:
\begin{equation}
f_0 = \sum_{k=0}^{u-1}(b_k + \omega^{uj}b_{k+u} )z^k, \hspace{0.4cm} f_1 = \sum_{k=0}^{u-1}(b_k - \omega^{uj}b_{k+u})z^k.
\end{equation}
thus, given an array containing the coefficients $b_k$ of $f'$, we can write $f_0$ and $f_1$ in place of $f'$ by way of operations
\begin{equation}\label{eqn:rad2fft}
\left[\begin{matrix} b_k \\ b_{k+u}\end{matrix}\right] \longleftarrow \left[\begin{matrix} 1 & \omega^{uj} \\ 1 & -\omega^{uj}\end{matrix}\right]\left[\begin{matrix} b_{k} \\ b_{k+u}\end{matrix}\right], \hspace{0.4cm} 0 \leq i \leq u.
\end{equation}

The pair of assignments \eqref{eqn:rad2fft} are known as a {\em butterfly operation}, and can be performed with a ring multiplication by the {\em twiddle factor} $\omega^{uj}$, and two additions.  Note $f_0$ and $f_1$ are in a similar form as $f'$, and if $u>1$ we can break those images into smaller images in the same fashion.  Starting this method with input $f \bmod (z^N-1)$, will give us $f \bmod (z-\omega^j) = f(\omega^j)$, for $0 \leq j < N$.

If the butterfly operations are performed in place, the resulting evaluations $f(\omega^j)$ will be written in {\em bit-reversed} order.  More precisely, if we let $[j]_p$ denote the integer resulting from reversing the first $p$ bits of $j$, $0 \leq j <2^p$, we have that $f(\omega^j)$ will be written in place of $a_{k}$, where $k=[j]_p$ and $\log$ is taken to be base-2 throughout.  As an example,
\begin{equation}
[11]_5 = [{\tt 01011}_2]_5 = {\tt 11010}_2 = 16+8+2=26.
\end{equation}

We can make the FFT entirely in-place by computing the powers of $\omega^u$ sequentially at every iteration.  This entails traversing the array in a non-sequential order.  Procedure {\tt\ref{proc:FFT}} describes such an implementation.

If we observe that
\begin{equation}\label{eqn:invButterfly}
\left[\begin{matrix} 1 & \omega^{uj} \\ 1 & -\omega^{uj}\end{matrix}\right]^{-1} = \frac{1}{2}\left[\begin{matrix} 1 &  1\\ \omega^{-uj} & -\omega^{-uj}\end{matrix}\right],
\end{equation}
then we can implement an inverse FFT by inverting the butterfly operations in reversed order.  We can, moreover, delay multiplications by powers of $\tfrac{1}{2}$ until the end of the inverse FFT computation.  This entails multiplying each coefficient by $\tfrac{1}{N}$.

\begin{procedure}
	\caption{FFT(\textbf{a}, $N$, $\omega$), an in-place implementation of the radix-2 Cooley-Tukey FFT}\label{proc:FFT}
	\KwIn{
		\begin{itemize}[noitemsep,nolistsep]
			\item  $\textbf{a} = (\textbf{a}_0, \dots, \textbf{a}_{N-1})$, an array vector $a \in\mathcal{R}^N$.
			\item  $\omega$, a root of $z^N-1$, with $N=2^p$
		\end{itemize}
	}
	\KwResult{ $\DFT_\omega(a)$ is written to the array ${\bf a}$ in bit-reversed order.  }\vspace{0.3cm}

	\For{$i \longleftarrow 1$ \KwTo $p$}{
		$u \longleftarrow N/2^i$\\
		\For{$j \longleftarrow 0$ \KwTo $\tfrac{N}{2u}-1$}{
			$t \longleftarrow 2\rev_i(j)u$\\
			%
			\For{$k \longleftarrow 0$ \KwTo $u-1$ }{
				\tcp{Butterfly operations \eqref{eqn:rad2fft}}
				$\left[\begin{matrix} {\bf a}_{t+k} \\ {\bf a}_{t+k+u}\end{matrix}\right] \longleftarrow \left[\begin{matrix} 1 & \omega^{uj} \\ 1 & -\omega^{uj}\end{matrix}\right]\left[\begin{matrix} {\bf a}_{t+k} \\ {\bf a}_{t+k+u}\end{matrix}\right]$ \\
				\label{line:butterfly}
			}

		}
	}
\end{procedure}

\begin{Thm}
Let $N$ be a power of two and $\omega$ an $N\th$ root of unity.  Then $\DFT_{\omega}(f)$ can be computed in place using $\tfrac{1}{2}N\log N + \mathcal{O}(N)$ ring multiplications.  The inverse FFT can interpolate $f(z)$ from its DFT with similar complexity.
\end{Thm}

Using the radix-2 FFT, if $d = \deg(fg)$, we choose $N$ to be the least power of $2$ exceeding $d$.  This entails appending zeros to the input arrays containing the coefficients of $f$ and $g$ respectively.  By this method, computing a product of degree $2^p$ costs roughly double that a product of degree $2^p-1$.  Crandall's {\em devil's convolution} algorithm \cite{scicomp} somewhat flattens these jumps in complexity, though not entirely.  It works by reducing a discrete convolution of arbitrary length into more easily computable convolutions.  More recently, truncated Fourier transform (TFT) algorithms, described hereafter, have addressed this issue.

\section{Introduction}

Let $\mathcal{R}$ be a ring containing an $N$-th principal root of unity $\omega$.  Given two polynomials $f,g \in \mathcal{R}[z]$, $\deg(fg)<N$, we can compute $fg$ by way of the Discrete Fourier Transform (DFT): a linear, invertible map which evaluates a given polynomial at the powers of $\omega$.

Computing the DFT naively is quadratic-time.  If, however, $N$ is comprised of strictly small prime factors, one can compute a DFT using $\mathcal{O}(N \log N)$ arithmetic operations by way of the Fast Fourier Transform (FFT).  The most widely-used FFT, the {\em radix-2} FFT, requires that $N$ is a power of two.  To compute the DFT of an input of arbitrary size, one typically appends zeroes to the input to give it power-of-two length, then applies a radix-2 FFT.  This results in significant jumps in the time and space complexities of the radix-2 FFT.

Truncated Fourier Transforms (TFTs) smooth these jumps in complexity.  A TFT takes a length-$n$ input, $n\leq N$, and returns a size-$n$ subset of its length-$N$ DFT, with time complexity that grows comparatively smoothly with $n \log n$.  Typically one chooses the first $n$ entries of the DFT, with the DFT sorted in bit-reversed order.  This is natural choice as it comprised the first $n$ entries of the output of an in-place FFT, if no re-sorting is performed.  We will call such a TFT the {\em bit-reversed} TFT.

Van der Hoeven \cite{vdH:tft} showed how one could obtain a polynomial $f(z)$ from its bit-reversed TFT, provided one knows the terms of $f(z)$ with degree at least $n$.  This allows for faster FFT-based polynomial multiplication, particularly for products whose degree is a power of two or slightly larger.  Harvey and Roche showed further in \cite{HR} how the bit-reversed TFT transform can be made in-place, at the cost of a constant factor additional ring multiplications.

Mateer \cite{Todd} devised a TFT algorithm based on a series of modular reductions, that acts as a preprocessor to the FFT.  Mateer's TFT algorithm, which we discuss in section \ref{sec:cyclotomicTFT} breaks an input $f(z)$ with $\deg(f)<n$, into its images modulo cyclotomic polynomials of the form $z^{k}+1$, $k$ a power-of-two.  We will call this TFT the {\em cyclotomic} TFT.  In \cite{Igor}, Sergeev showed how the cyclotomic TFT can be made in-place, with time complexity comparable to not-in-place TFT algorithms.  In section \ref{sec:newTFT}, we restate Sergeev's algorithm.  In section \ref{sec:ctft}, we present a new in-place algorithm, related to Sergeev's, for computing the cyclotomic TFT.

One caveat of the cyclotomic TFT is that different-sized inputs may use entirely different sets of evaluation points.  This is problematic in applications to multivariate polynomial multiplication.  In section \ref{sec:affine}, we show how an algorithm that computes the cyclotomic TFT can be modified to compute a bit-reversed TFT by way of an affine transformation.

As a proof of concept we implemented the algorithms introduced in this paper in python.  These implementations can be found at the author's website at:
\begin{center}
\url{http://cs.uwaterloo.ca/~a4arnold/tft}.
\end{center}
\section{In-place methods for computing the cyclotomic TFT}\label{sec:newTFT}

\input{newtft_notation}
\input{newtft_lemmas}
\input{newtft_sergeev}

\section{A new in-place cyclotomic TFT algorithm}\label{sec:ctft}

In order to compute a new coefficient of an image of $f$ in Sergeev's algorithm, one has to effectively make a pass through the array in order to sum the contributions from images $f_j$.  Instead of summing the contributions and then adding that into our array, we will add contributions directly back into our array of coefficients.  In order to do this, we will work with the {\em weighted} images,
\begin{equation}
f_i^*(z) = 2^{-i+1}f_i,
\end{equation}
this allows us to add all the contributions to a new polynomial image with a single pass over our array.  Moreover, unlike Sergeev's algorithm, we will forego producing part of the images $f \bmod (z^K-1)$, $K$, a power of two.  We will compute $f_{i+1}$ immediately after producing $f_i$.

Our transform has three steps: we first iteratively compute the remainders produced by dividing $q_{i-1}$ by $\Phi_i$,
\begin{equation}
r_i = q_{i-1} \bmod \Phi_i, \hspace{0.3cm} 1 \leq i \leq s.
\end{equation}
in place of $f$; we then iteratively write $f_i^*$ in place of $r_i$ for $i=1,2,\dots,s$; lastly we reweigh the weighted images $f_i^*$ to get $f_i$ and compute a DWT of each image $f_i$ separately to give us the weighted evaluation points.

\subsection{Breaking $f$ into the remainders $r_1, \dots, r_s$}\label{sec:ri}

We first break $f=q_0$ into its quotient and remainder dividing by $z^{n_1}+1$,
\begin{align}
r_1 = f &\bmod \left(z^{n_1}+1\right) = \sum_{i=0}^{n_1-1}\left( a_i - a_{i+n_1} \right)z^i,\\
q_1 = f &\quo \left(z^{n_1}+1\right) = \sum_{i=0}^{n_1^*}a_{i+n_1}z^i,
\end{align}
where $a_i=0$ for $i \geq n$.  This can be done in place with $n_1^*$ subtractions in $\mathcal{R}$.  We then similarly break $q_1$ into $r_2$ and $q_2$, then $q_2$ into $r_3$ and $q_3$, and continue until we have $r_1, \dots, r_{s-1}$ and $q_{s-1}$.  Since $\deg(q_{s-1})<n_s = \deg(\Phi_s)$, $r_s$ is exactly $q_{s-1}$.

\subsection{Writing the weighted images $f_i^*$ in place of the remainders $r_i$}

We first note that $f_1^*$ is precisely $r_1$.  We will iteratively produce the remaining weighted images.

Suppose, at the start of the $i\th$ iteration, we have $f_1^*, \dots, f_{i}^*$, and $r_{i+1}, \dots, r_s$, and we want to write $f_{i+1}^*$ in place of $r_{i+1}$.  We have
\begin{align}
f_{i+1}^* &= 2^{-i}f \bmod \Phi_{i+1}, \\
&=2^{-i}\left(\Gamma_{i}q_i + C_{i} \right) \bmod \Phi_{i+1}, \\
&= \left( q_i + 2^{-i}C_{i} \right) \bmod \Phi_{i+1},\\
&= r_{i+1} + \left( 2^{-i}C_i \bmod \Phi_{i+1}. \right)\label{eqn:ith_iteration}
\end{align}

Unfortunately, we don't have the combined image $C_{i}$, but rather the weighted images $f_j^*$, $1 \leq j \leq i$, from which we can reconstruct $C_i$.  We would like to be able to compute $C_i \bmod \Phi_{i+1}$ in place from the weighted images $f_j^*$.

Corollary \ref{lem:crt} tells us the {\em contribution} of $f^*_i$ towards subsequent images.  If $e$ satisfies the non-zero criterion of the lemma, then by \eqref{eqn:ith_iteration}, a term $c_{j,e}z^e$ of $f^*_j$, $j\leq i$ will contribute $\tfrac{1}{2}(-1)^{e[n(i+1)]}z^{ (e \bmod n_{i+1}) }$ to $f^*_{i+1}$.  In order to make the contributions have weight $\pm 1$, we instead first reweigh $r_i$ by $2$ and compute $2f^*_i$, and then divide by $2$ thereafter.  {\tt\ref{proc:addContribution}} adds the contribution of $f^*_1,\dots, f^*_{i-1}$ to $f^*_i$.
\input{proc_addContribution}

According to corollary \ref{lem:crt}, $f^*_j$, $0 \leq j \leq i$, only a proportion of $2^{i-j}$ of the terms of $f^*_j$ will have a non-zero contribution to $f^*_{i+1}$.  Thus the total cost of adding contributions of $f^*_j$ towards $f^*_i$, $i>j$, is less than $2\#f^*_j = 2n_j$.  It follows that the total additions and subtractions in $\mathcal{R}$ required to add all these contributions is bounded by $2n$.  Since {\tt\ref{proc:addContribution}} only scales array ring elements by $\pm 1$, we have the following complexity:

\begin{Lem}\label{ref:contrib}
Calling {\tt\ref{proc:addContribution}}$({\bf a}, n, i)$ for $i$ from 1 to $s$ entails no more than $2n$ ring additions and no ring multiplications.
\end{Lem}

In the manner we have chosen to add these contributions, we will have to make $s-1$ passes through our array to add them all.  One way we could avoid this is to instead add all the contributions from $f^*_1$, and then all the contributions from $f^*_2$, and so forth, adding up all the contributions from a single term at once.  We could use that a term $c_{j,e}z^e$ of $f^*_j$ that does not contribute towards $f^*_{i+1}$ will not contribute to $f^*_k$ for any $k > i$.  This would reduce the number of passes we make through the larger portion of the array, though the cache performance of potentially writing to $s-1$ images at once raises questions.

When adding contributions to $f^*_i$, any two terms $c_{j,e}z^e$ and $c_{j,e^*}z^{e^*}$ of $f^*_j$ whose bits $e[n(l)], e^*[n(l)]$ agree for $j < l < i$ will both contribute to $f^*_i$ in the same fashion (i.e. we will either add or subtract both coefficients $c_{i,e}$ and $c_{i,e*}$ to an image, or do nothing).  Thus we need only inspect the non-zero criterion of one exponent $e$ in a block of exponents $kn_{i-1} \leq e < (k+1)n_{i-1}$.  Similarly, we need only inspect one exponent in a contiguous block of $n_i$ exponents in order to determine their shared value of $(-1)^{e[n(i)]}$.

Given an exponent that does not satisfy the non-zero criterion, our implementation will generate the next exponent that does satisfy the non-zero criterion, by way of bit operations.

\input{proc_break}

Procedure {\tt\ref{proc:break}}$(\a, n)$ breaks $f$ into the images $f_i$.  The procedure effectively has three sections.  In the first section of the algorithm, we break $f$ into the remainders $r_i$.  Producing $r_i$ entails $n_i^* < n_i$ additions, and so producing all the $r_i$ entails less than $\sum_{i=1}^s n_i = n$ ring additions.

In the second section we write the weighted images $f_i^*$ in place of the $r_i$.  Adding all the contributions, per lemma \ref{ref:contrib}, requires $2n$ additions.  We reweigh the last $n-n_1$ coefficients of $f$ by $2$, then by $\tfrac{1}{2}$.  This constitutes less than $n$ such multiplications.

In the third section we reweigh the weighted images $f_i^*$ to get the images $f_i$.  This entails less than $n$ multiplications by $2$.  This gives us the following complexity:

\begin{Lem}\label{lem:break}
Procedure {\tt\ref{proc:break}}$(\a, n)$ entails no more than $3n$ additions and $2n$ multiplications by $2^{\pm 1}$.
\end{Lem}

Thus, like Mateer's and Sergeev's algorithms, the TFT algorithm presented amounts to linearly many ring operations plus the cost of performing FFTs of size $n_i$, $1 \leq i \leq s$.
Inverting the TFT is straightforward.  Given the images $f_1, \dots, f_s$, we can reobtain the polynomial $f$ by effectively reversing the steps of procedure {\tt\ref{proc:break}}.  Since {\tt\ref{proc:break}} strictly entails 1) multiplying arrays elements by nonzero scalars and 2) adding or subtracting one array element from another, it is straightforward to undo each of the steps to get back $f$, with similar complexity.

\subsection{Computing images of $C_i$ without explicitly computing $C_i$}

We will express the combined image $C_i$, $C_i$ reduced modulo $\Phi_{i+1}$ or a polynomial $z^k-1$ with $k=2^q$, in terms of the coefficients of the images $f_1, \dots, f_i$.  To this end we introduce the following notation.  Given an integer $e$, we will let $e[i]$ refer to the $i\th$ bit of $e$, i.e.
\begin{equation}
e=\sum_{i=0}^{\lfloor \log(e) \rfloor}e[i]2^i, \hspace{0.5cm}e[i] \in \{0,1\}.
\end{equation}

Sergeev's TFT relies on the following property, albeit stated differently here than in \cite{Igor}.

\begin{Lem}\label{lem:crt2}
Fix $i$, $j$ and $k$, $1 \leq j \leq i < k \leq s$.  Suppose that $f_j=z^e$ and $f_l = 0$ for $l \neq j$, $0 \leq l \leq i$.  Let $m$ be a power of two at most $n_i$.  Then $C_{i} \bmod z^m-1$ is nonzero only if
$e[ n(l) ] = 1$ for $j < l \leq i$, in which case,
\begin{align}
C_i \bmod (z^m-1) &= 2^{i-j}z^e \bmod (z^m-1) \\
&= 2^{i-j}z^{e \bmod m}.
\end{align}
\end{Lem}

As $\Phi_k$, $k>i$, divides $z^{n_i}-1$.  Lemma \ref{lem:crt2} gives us the following corollary.

\begin{Cor}\label{lem:crt}
Fix $i$, $j$ and $k$, $1 \leq j \leq i < k \leq s$.  Suppose that $f_j=z^e$ and $f_l = 0$ for $l \neq j$, $0 \leq l \leq i$.  Then $C_{i} \bmod \Phi_{k}$ is nonzero only if
$e[ n(l) ] = 1$ for $j < l \leq i$, in which case
\begin{equation}\label{eqn:lem}
C_{i} \bmod \Phi_{k} = 2^{i-j}z^e \bmod \Phi_{k}.
\end{equation}
\end{Cor}
Given that $z^{n_k} \bmod \Phi_k = -1$, we have that
\begin{equation}\label{eqn:explicitForm}
2^{i-j}z^e \bmod \Phi_{k} = (-1)^{e[n(k)]}2^{i-j}z^{ (e \bmod n_k) },
\end{equation}
where $e \bmod n_k$ is the integer $e^*$ such that $n_k | (e-e^*)$ and $0 \leq e^* < n_k$.  The values $e[n(l)]$ can be determined from $n_l=2^{n(l)}$ and $e$ by way of a bitwise ``and'' operation.

\begin{Exam}[Example of corollary \ref{lem:crt}]
Suppose $n=86$ $(n=64+16+4+2)$, and suppose that
\begin{align*}
f_1 = f \bmod z^{64}+1 = z^e, \hspace{0.5cm} f_2 = 0, \hspace{0.5cm} f_3 = 0,
\end{align*}
and $\deg(f) < 64+16+4$.  In this example,
\begin{equation}
C_3 = f \bmod \left[ (z^{64}+1)(z^{16}+1)(z^4+1) \right].
\end{equation}
Let $g(z) = C_3 \bmod (z^2+1)$.  Then by lemma \ref{lem:crt},
\begin{equation*}
g(z) = \left\{ \begin{array}{lll}
0 & \text{ if } e \in [0,20) \cup [24,28) \cup [32,52) \cup [56,60),\\
4 & \text{ if } e = 20,28,52, \text{ or }56,\\
4z & \text{ if } e = 21,29,53, \text{ or }57,\\
-4 & \text{ if } e = 22,30,54, \text{ or }58,\\
-4z & \text{ if } e = 23, 31, 55, \text{ or }59.
\end{array}\right.
\end{equation*}
\end{Exam}

\begin{Rem}\label{rem:nonzero}
Let $1 \leq j \leq i \leq s$.  A proportion of $2^{j-i}$ terms of $f_j$ have an exponent satisfying the nonzero criterion of lemmas \ref{lem:crt} and \ref{lem:crt2}.  Moreover, this nonzero criterion may be easily checked using a bitwise ``and'' operation.
\end{Rem}

\begin{proof}[\bf Proof of lemma \ref{lem:crt2}]
We fix $e$ and $j$ and prove by induction on $i$.

{\em Base case:} Let $i=j$.  As in the proof of lemma \ref{lem:crt} we have $C_i = 2^{1-i}\Gamma_{i-1}z^e$.  As $\Phi_l \bmod z^m-1 = 2^i$ for $m$ a power of two dividing $n_l$, it follows that
$C_i \bmod z^m-1 = z^e \bmod z^m-1$.

{\em Inductive step:}  Suppose now that the lemma holds for a fixed $i\geq j$, and consider $C_{i+1} \bmod z^m-1$, $m$ a power of two dividing $n_{i+1}$.  We suppose that $f^*_l = 0$ for $1 \leq l \neq j \leq i+1$ and $f^*_j = z^e$.  By Chinese remaindering,
\begin{equation}\label{eqmod}
C_{i+1} = C_i - \Gamma_i\left( \Gamma_i^{-1}C_i \bmod \Phi_{i+1}\right).
\end{equation}.
Reducing this expression modulo $z^m-1$ gives us
\begin{equation}
C_{i+1} = C_i - \Gamma_i\left( \Gamma_i^{-1}C_i \bmod \Phi_{i+1} \right) \bmod z^m-1.
\end{equation}

{\em Case 1:}  If $e[n(l)]=0$ for some $l$, $j<l\leq i$, then by the induction hypothesis, $C_i \bmod z^m-1 = 0$.  By lemma \ref{lem:crt}, $C_i \bmod \Phi_{i+1}=0$.  Thus we have $C_{i+1} \bmod z^m-1 = 0$ as well.

{\em Case 2:}  If $e[n(l)]=0$ for $j<l \leq i$, then by the induction hypothesis, $C_i \bmod z^m-1 = 2^{i-j}z^e \bmod z^m-1$.  By lemma \ref{lem:crt}, $C_i \bmod \Phi_{i+1} = z^e \bmod \Phi_{i+1}$
\begin{align}
&C_{i+1} \bmod z^m-1 \notag \\
&= 2^{i-j}z^e - \Gamma_i\left( \Gamma_i^{-1} z^e \bmod \Phi_{i+1} \right) \bmod z^m-1 \\
&= 2^{i-j}z^{e \bmod m} - \left( z^e \bmod \Phi_{i+1} \right) \bmod z^m-1\\
&= 2^{i-j}\left(1 + (-1)^{e[n(i+1)]} \right)z^{e \bmod m}.
\end{align}
As $1 + (-1)^e[n(i+1)]$ evaluates to $2$ if $e[n(i+1)]=1$ and $0$ otherwise, this completes the proof.
\end{proof}

Lemma \ref{lem:crt2} can be derived from lemma 1 in \cite{Igor}.

\subsection{Sergeev's in-place cyclotomic TFT}

In \cite{Igor}, Sergeev describes an arithmetic circuit for computing a cyclotomic TFT.  Such a circuit for computing $\TFT'_{\omega,n}(f)$ has a depth of $n + \mathcal{O}(1)$.  That is, it requires space for $n + \mathcal{O}(1)$ ring elements.  This algorithm, like Mateer's breaks $f$ into the images $f_i$ in linear time, and then applies a DWT on each image.  Algorithm \ref{alg:serg} describes how $f$ is broken into the images $f_i^*$.

\begin{algorithm}
\caption{Sergeev's algorithm for computing $f_1,\dots,f_s$ in place of $f$}\label{alg:serg}
\KwIn{
	$n<N$, $f(z) \in \mathcal{R}[z]$, $f=\sum_{i=0}^{n-1}a_iz^i$
}
\KwResult{ $f_1,\dots,f_s$ are written in place of $f$ }

	$(i,K) \longleftarrow (0,N)$\\

	\While{$K > n_s$}{
		{\bf Loop invariant:}  We have the images $f_j$, $1 \leq j \leq i$, and the first $n_i^*$ coefficients of $f \bmod (z^K-1)$.\\
		\If{ $K/2 = n_{i+1}$}{
			Compute $f_{i+1}$ and the first $n_{i+1}^*$ coefficients of $f \bmod (z^{K/2}-1)$ in place of the first $n_i^*$ coefficients of $f \bmod (z^K-1)$.\\
			$i \longleftarrow i+1$
		}
		\Else{
			Write the first $n_i^*$ coefficients of $f \bmod (z^{K/2}-1)$ in place of the coefficients of $f \bmod (z^K-1)$.
		}
		$K \longleftarrow K/2$
	}
\end{algorithm}

Suppose we have $f_1, \dots, f_i$, and the first $n_i^*$ coefficients of $g = f \bmod (z^K-1)$, where $K \leq n_i$ is a power of two.  Note that $K$ may be greater than $n_i^*$.  If we write
\begin{equation}
f(z) \bmod (z^K-1) = \sum_{j=0}^{K-1}b_iz^i,
\end{equation}
then
\begin{align}
f(z) \bmod (z^{K/2}-1) &= \sum_{j=0}^{K/2-1}(b_j + b_{j+K/2})z^j, \text{ and}\label{eqn:serg1}\\
f(z) \bmod (z^{K/2}+1) &= \sum_{j=0}^{K/2-1}(b_j - b_{j+K/2})z^j. \label{eqn:serg2}
\end{align}
If $K/2 > n_i^*$, Sergeev's algorithm will write the first $n_i^*$ coefficients of $f \bmod (z^{K/2}-1)$ in place of $f \bmod (z^K-1)$, i.e. we want to add $b_{i+K/2}$ to $b_i$ for $0 \leq i < n_i^*$.  Reducing $f = C_i + \Gamma_iq_i$ modulo $z^K-1$, we have
\begin{equation}
f \bmod (z^K-1) = C_i + 2^iq_i \bmod (z^K-1).
\end{equation}

\begin{Rem}
As $\deg(q_i) < n_i^* < K/2$, the coefficients $b_{j+K/2}$, $0 \leq j < n_j^*$ depends strictly on $C_i \bmod (z^K-1)$.
\end{Rem}
We use lemma \ref{lem:crt2} to determine the {\em contribution} of each coefficient of $f_j$, $1 \leq j \leq i$, towards $b_{i+K/2}$.  Namely, if a term $cz^e$ appearing in $f_j$ satisfies the nonzero criterion of lemma \ref{lem:crt2}, then it will have a contribution of $2^{i-j}c$ towards $b_{i+K/2}$.  For $0 \leq i < n_i^*$, we compute the sum of these contributions towards $b_{i+K/2}$ and then add that to $b_i$.  In order to minimize the number of multiplications necessary in order to compute the weights $2^{i-j}$, we sum the contributions from $f_1$, then multiply that sum by $2$, then add to that all the contributions from $f_2$, again multiply that by 2, and so forth.

If instead, $K \leq n_i^*$, we have that $K$ must equal $n_{i+1}$, we write $f_{i+1}$ and the first $n_{i+1}^*$ coefficients of $f \bmod (z^{K/2}-1)$ in place of $b_j$, $0 \leq j < n_i^*$.  For $0 \leq j < n_{i+1}^*$, we have both $b_i$ and $b_{i+K/2}$, and can compute the $z^i$ coefficient of $f_{i+1}$ and $f \bmod (z^{K/2}-1)$ in their places accordingly.  What remains is to compute the last $n_i - n_i^*$ coefficients of $f_{i+1}$.  This amounts to computing $b_{i+K/2}$ by way of lemma \ref{lem:crt2}, as in the first case.

\section{Introduction}
The \textit{proceedings} are the records of a conference.
ACM seeks to give these conference by-products a uniform,
high-quality appearance.  To do this, ACM has some rigid
requirements for the format of the proceedings documents: there
is a specified format (balanced  double columns), a specified
set of fonts (Arial or Helvetica and Times Roman) in
certain specified sizes (for instance, 9 point for body copy),
a specified live area (18 $\times$ 23.5 cm [7" $\times$ 9.25"]) centered on
the page, specified size of margins (1.9 cm [0.75"]) top, (2.54 cm [1"]) bottom
and (1.9 cm [.75"]) left and right; specified column width
(8.45 cm [3.33"]) and gutter size (.83 cm [.33"]).

The good news is, with only a handful of manual
settings\footnote{Two of these, the {\texttt{\char'134 numberofauthors}}
and {\texttt{\char'134 alignauthor}} commands, you have
already used; another, {\texttt{\char'134 balancecolumns}}, will
be used in your very last run of \LaTeX\ to ensure
balanced column heights on the last page.}, the \LaTeX\ document
class file handles all of this for you.

The remainder of this document is concerned with showing, in
the context of an ``actual'' document, the \LaTeX\ commands
specifically available for denoting the structure of a
proceedings paper, rather than with giving rigorous descriptions
or explanations of such commands.

\section{The {\secit Body} of The Paper}
Typically, the body of a paper is organized
into a hierarchical structure, with numbered or unnumbered
headings for sections, subsections, sub-subsections, and even
smaller sections.  The command \texttt{{\char'134}section} that
precedes this paragraph is part of such a
hierarchy.\footnote{This is the second footnote.  It
starts a series of three footnotes that add nothing
informational, but just give an idea of how footnotes work
and look. It is a wordy one, just so you see
how a longish one plays out.} \LaTeX\ handles the numbering
and placement of these headings for you, when you use
the appropriate heading commands around the titles
of the headings.  If you want a sub-subsection or
smaller part to be unnumbered in your output, simply append an
asterisk to the command name.  Examples of both
numbered and unnumbered headings will appear throughout the
balance of this sample document.

Because the entire article is contained in
the \textbf{document} environment, you can indicate the
start of a new paragraph with a blank line in your
input file; that is why this sentence forms a separate paragraph.

\subsection{Type Changes and {\subsecit Special} Characters}
We have already seen several typeface changes in this sample.  You
can indicate italicized words or phrases in your text with
the command \texttt{{\char'134}textit}; emboldening with the
command \texttt{{\char'134}textbf}
and typewriter-style (for instance, for computer code) with
\texttt{{\char'134}texttt}.  But remember, you do not
have to indicate typestyle changes when such changes are
part of the \textit{structural} elements of your
article; for instance, the heading of this subsection will
be in a sans serif\footnote{A third footnote, here.
Let's make this a rather short one to
see how it looks.} typeface, but that is handled by the
document class file. Take care with the use
of\footnote{A fourth, and last, footnote.}
the curly braces in typeface changes; they mark
the beginning and end of
the text that is to be in the different typeface.

You can use whatever symbols, accented characters, or
non-English characters you need anywhere in your document;
you can find a complete list of what is
available in the \textit{\LaTeX\
User's Guide}\cite{Lamport:LaTeX}.

\subsection{Math Equations}
You may want to display math equations in three distinct styles:
inline, numbered or non-numbered display.  Each of
the three are discussed in the next sections.

\subsubsection{Inline (In-text) Equations}
A formula that appears in the running text is called an
inline or in-text formula.  It is produced by the
\textbf{math} environment, which can be
invoked with the usual \texttt{{\char'134}begin. . .{\char'134}end}
construction or with the short form \texttt{\$. . .\$}. You
can use any of the symbols and structures,
from $\alpha$ to $\omega$, available in
\LaTeX\cite{Lamport:LaTeX}; this section will simply show a
few examples of in-text equations in context. Notice how
this equation: \begin{math}\lim_{n\rightarrow \infty}x=0\end{math},
set here in in-line math style, looks slightly different when
set in display style.  (See next section).

\subsubsection{Display Equations}
A numbered display equation -- one set off by vertical space
from the text and centered horizontally -- is produced
by the \textbf{equation} environment. An unnumbered display
equation is produced by the \textbf{displaymath} environment.

Again, in either environment, you can use any of the symbols
and structures available in \LaTeX; this section will just
give a couple of examples of display equations in context.
First, consider the equation, shown as an inline equation above:
\begin{equation}\lim_{n\rightarrow \infty}x=0\end{equation}
Notice how it is formatted somewhat differently in
the \textbf{displaymath}
environment.  Now, we'll enter an unnumbered equation:
\begin{displaymath}\sum_{i=0}^{\infty} x + 1\end{displaymath}
and follow it with another numbered equation:
\begin{equation}\sum_{i=0}^{\infty}x_i=\int_{0}^{\pi+2} f\end{equation}
just to demonstrate \LaTeX's able handling of numbering.

\subsection{Citations}
Citations to articles \cite{bowman:reasoning,
clark:pct, braams:babel, herlihy:methodology},
conference proceedings \cite{clark:pct} or
books \cite{salas:calculus, Lamport:LaTeX} listed
in the Bibliography section of your
article will occur throughout the text of your article.
You should use BibTeX to automatically produce this bibliography;
you simply need to insert one of several citation commands with
a key of the item cited in the proper location in
the \texttt{.tex} file \cite{Lamport:LaTeX}.
The key is a short reference you invent to uniquely
identify each work; in this sample document, the key is
the first author's surname and a
word from the title.  This identifying key is included
with each item in the \texttt{.bib} file for your article.

The details of the construction of the \texttt{.bib} file
are beyond the scope of this sample document, but more
information can be found in the \textit{Author's Guide},
and exhaustive details in the \textit{\LaTeX\ User's
Guide}\cite{Lamport:LaTeX}.

This article shows only the plainest form
of the citation command, using \texttt{{\char'134}cite}.
This is what is stipulated in the SIGS style specifications.
No other citation format is endorsed or supported.

\subsection{Tables}
Because tables cannot be split across pages, the best
placement for them is typically the top of the page
nearest their initial cite.  To
ensure this proper ``floating'' placement of tables, use the
environment \textbf{table} to enclose the table's contents and
the table caption.  The contents of the table itself must go
in the \textbf{tabular} environment, to
be aligned properly in rows and columns, with the desired
horizontal and vertical rules.  Again, detailed instructions
on \textbf{tabular} material
is found in the \textit{\LaTeX\ User's Guide}.

Immediately following this sentence is the point at which
Table 1 is included in the input file; compare the
placement of the table here with the table in the printed
dvi output of this document.

\begin{table}
\centering
\caption{Frequency of Special Characters}
\begin{tabular}{|c|c|l|} \hline
Non-English or Math&Frequency&Comments\\ \hline
\O & 1 in 1,000& For Swedish names\\ \hline
$\pi$ & 1 in 5& Common in math\\ \hline
\$ & 4 in 5 & Used in business\\ \hline
$\Psi^2_1$ & 1 in 40,000& Unexplained usage\\
\hline\end{tabular}
\end{table}

To set a wider table, which takes up the whole width of
the page's live area, use the environment
\textbf{table*} to enclose the table's contents and
the table caption.  As with a single-column table, this wide
table will ``float" to a location deemed more desirable.
Immediately following this sentence is the point at which
Table 2 is included in the input file; again, it is
instructive to compare the placement of the
table here with the table in the printed dvi
output of this document.

\begin{table*}
\centering
\caption{Some Typical Commands}
\begin{tabular}{|c|c|l|} \hline
Command&A Number&Comments\\ \hline
\texttt{{\char'134}alignauthor} & 100& Author alignment\\ \hline
\texttt{{\char'134}numberofauthors}& 200& Author enumeration\\ \hline
\texttt{{\char'134}table}& 300 & For tables\\ \hline
\texttt{{\char'134}table*}& 400& For wider tables\\ \hline\end{tabular}
\end{table*}

\subsection{Figures}
Like tables, figures cannot be split across pages; the
best placement for them
is typically the top or the bottom of the page nearest
their initial cite.  To ensure this proper ``floating'' placement
of figures, use the environment
\textbf{figure} to enclose the figure and its caption.

This sample document contains examples of \textbf{.eps}
and \textbf{.ps} files to be displayable with \LaTeX.  More
details on each of these is found in the \textit{Author's Guide}.

\begin{figure}
\centering
\epsfig{file=fly.eps}
\caption{A sample black and white graphic (.eps format).}
\end{figure}

\begin{figure}
\centering
\epsfig{file=fly.eps, height=1in, width=1in}
\caption{A sample black and white graphic (.eps format)
that has been resized with the \texttt{epsfig} command.}
\end{figure}

As was the case with tables, you may want a figure
that spans two columns.  To do this, and still to
ensure proper ``floating'' placement of tables, use the environment
\textbf{figure*} to enclose the figure and its caption.
and don't forget to end the environment with
{figure*}, not {figure}!

\begin{figure*}
\centering
\epsfig{file=flies.eps}
\caption{A sample black and white graphic (.eps format)
that needs to span two columns of text.}
\end{figure*}

Note that either {\textbf{.ps}} or {\textbf{.eps}} formats are
used; use
the \texttt{{\char'134}epsfig} or \texttt{{\char'134}psfig}
commands as appropriate for the different file types.

\begin{figure}
\centering
\psfig{file=rosette.ps, height=1in, width=1in,}
\caption{A sample black and white graphic (.ps format) that has
been resized with the \texttt{psfig} command.}
\vskip -6pt
\end{figure}

\subsection{Theorem-like Constructs}
Other common constructs that may occur in your article are
the forms for logical constructs like theorems, axioms,
corollaries and proofs.  There are
two forms, one produced by the
command \texttt{{\char'134}newtheorem} and the
other by the command \texttt{{\char'134}newdef}; perhaps
the clearest and easiest way to distinguish them is
to compare the two in the output of this sample document:

This uses the \textbf{theorem} environment, created by
the\linebreak\texttt{{\char'134}newtheorem} command:
\newtheorem{theorem}{Theorem}
\begin{theorem}
Let $f$ be continuous on $[a,b]$.  If $G$ is
an antiderivative for $f$ on $[a,b]$, then
\begin{displaymath}\int^b_af(t)dt = G(b) - G(a).\end{displaymath}
\end{theorem}

The other uses the \textbf{definition} environment, created
by the \texttt{{\char'134}newdef} command:
\newdef{definition}{Definition}
\begin{definition}
If $z$ is irrational, then by $e^z$ we mean the
unique number which has
logarithm $z$: \begin{displaymath}{\log e^z = z}\end{displaymath}
\end{definition}

Two lists of constructs that use one of these
forms is given in the
\textit{Author's  Guidelines}.

There is one other similar construct environment, which is
already set up
for you; i.e. you must \textit{not} use
a \texttt{{\char'134}newdef} command to
create it: the \textbf{proof} environment.  Here
is a example of its use:
\begin{proof}
Suppose on the contrary there exists a real number $L$ such that
\begin{displaymath}
\lim_{x\rightarrow\infty} \frac{f(x)}{g(x)} = L.
\end{displaymath}
Then
\begin{displaymath}
l=\lim_{x\rightarrow c} f(x)
= \lim_{x\rightarrow c}
\left[ g{x} \cdot \frac{f(x)}{g(x)} \right ]
= \lim_{x\rightarrow c} g(x) \cdot \lim_{x\rightarrow c}
\frac{f(x)}{g(x)} = 0\cdot L = 0,
\end{displaymath}
which contradicts our assumption that $l\neq 0$.
\end{proof}

Complete rules about using these environments and using the
two different creation commands are in the
\textit{Author's Guide}; please consult it for more
detailed instructions.  If you need to use another construct,
not listed therein, which you want to have the same
formatting as the Theorem
or the Definition\cite{salas:calculus} shown above,
use the \texttt{{\char'134}newtheorem} or the
\texttt{{\char'134}newdef} command,
respectively, to create it.

\subsection*{A {\secit Caveat} for the \TeX\ Expert}
Because you have just been given permission to
use the \texttt{{\char'134}newdef} command to create a
new form, you might think you can
use \TeX's \texttt{{\char'134}def} to create a
new command: \textit{Please refrain from doing this!}
Remember that your \LaTeX\ source code is primarily intended
to create camera-ready copy, but may be converted
to other forms -- e.g. HTML. If you inadvertently omit
some or all of the \texttt{{\char'134}def}s recompilation will
be, to say the least, problematic.

\section{Conclusions}
This paragraph will end the body of this sample document.
Remember that you might still have Acknowledgments or
Appendices; brief samples of these
follow.  There is still the Bibliography to deal with; and
we will make a disclaimer about that here: with the exception
of the reference to the \LaTeX\ book, the citations in
this paper are to articles which have nothing to
do with the present subject and are used as
examples only.

\section{Acknowledgments}
This section is optional; it is a location for you
to acknowledge grants, funding, editing assistance and
what have you.  In the present case, for example, the
authors would like to thank Gerald Murray of ACM for
his help in codifying this \textit{Author's Guide}
and the \textbf{.cls} and \textbf{.tex} files that it describes.

\bibliographystyle{abbrv}

\subsection{Truncated Fourier Transforms}

In many applications, is it useful to compute a {\em pruned} DFT, a subset of a length-$N$ DFT, at a cost less than that computing a complete DFT.  In 2004, van der Hoeven showed in \cite{vdH:issac04} that, given some knowledge of the form of the input, one can invert some pruned DFTs.  The inverse transform relies on the observation that, given any two of the inputs/outputs to a butterfly operation \eqref{eqn:rad2fft}, one can compute the other two values.  Suppose $n \in \mathbb{Z}$ is arbitrary and $N$ is the least power of two at least $n$.  For $\omega$, a primitive root of unity of order $N=2^p$, van der Hoeven showed how to invert the length-$n$ bit-reversed Truncated Fourier Transform,
\begin{equation}
\TFT_{\omega, n}( f ) = \left( f( \omega^{[i]_p} ) \right)_{0 \leq i < n},
\end{equation}
when we know the coefficients of $f(z)$ of degree at least $n$ (e.g. when $\deg(f)<n$ ).  To distinguish this particular TFT we will call it the {\em bit-reversed} TFT.
\begin{Thm}[Van der Hoeven, \cite{vdH:tft}]\label{thm:vdh}
Let $N=2^p$, $n \in (N/2,N]$, $f(z) \in \mathcal{R}[z]$ and let $\omega \in \mathcal{R}$ be a principal $N$-th root of unity.  Suppose $\deg(f)<n$.  Then $\TFT_{\omega,n}(f)$ can be computed using $n \log n + \mathcal{O}(n)$ ring additions and $\tfrac{1}{2}n\log n + \mathcal{O}(n)$ multiplications by powers of $\omega$.

$f(z)$ can be recovered from $\TFT_{\omega,n}(f)$ using $n \log n + \mathcal{O}(n)$ {\em shifted} ring additions and $\tfrac{1}{2}n\log n + \mathcal{O}(n)$ multiplications.
\end{Thm}
A shifted ring addition merely means in this context an addition plus a multiplication by $\tfrac{1}{2}$.  Van der Hoeven's algorithm generalizes to allow us to compute arbitrary subsets of the DFT.  Given a subset $S \subseteq \{0,1,\dots, N-1\}$, we define
\begin{equation}
\TFT_{\omega, S}( f ) = \left( f( \omega^{[i]_p} )\right)_{i \in S},
\end{equation}
where $f$ we now assume $f$ is of the form $f(z) = \sum_{i \in S}a_iz^i$.  However, such a transform may have a greater complexity than stated in theorem \ref{thm:vdh}, taking $n = \#S$.  Moreover, such a map is not necessarily invertible.
\begin{Exam}
Taking $\omega$ an $N=8\th$ principal root of unity with $S = \{0,3,4,5\}$ gives an uninvertible map.  To see that the map $\TFT_{\omega,S}$ is not invertible, one can check that the polynomial $f(z) = (1+\omega^2)z^5 - z^4  + (1-\omega^2)z^3 - 1$ evaluates to $0$ for $z=\omega^k$, $k \in \{ [0]_3, [3]_3, [4]_3, [5]_3\} = \{0,6,1,5\}$.
\end{Exam}
Van der Hoeven's method still exhibits significant jumps in space complexity, as it space for $N$ ring elements regardless of $n$.  In 2010, Harvey and Roche \cite{HR} introduced an in-place TFT algorithm, requiring $n + \mathcal{O}(1)$ ring elements plus an additional $\mathcal{O}(1)$ bounded-precision integers to compute $\TFT_{\omega, n}(f)$.  Their method potentially requires evaluating polynomials using linear-time methods.  This results in a constant factor additionally many ring multiplications in the worst-case.

\begin{Thm}[Roche, Theorem 3.5 of \cite{Rthesis}]
Let $N,n,f$ and $\omega$ be as in theorem \ref{thm:vdh}.  Then $\TFT_{\omega,n}(f)$ can be computed in-place using at most $\tfrac{5}{6}n \log n + \mathcal{O}(n)$ ring multiplications and $\mathcal{O}(n \log n)$ ring additions.
\end{Thm}
The inverse in-place transform entails similarly many ring multiplications and $\mathcal{O}(n \log n)$ shifted ring additions.  As an application, Harvey and Roche used this transform towards asymptotically fast in-place polynomial multiplication.
\section{Preliminaries}\label{sec:prelim}

\input{dft}
\input{fft}
\input{tft}

\input{ctft}
\input{newtft}

\input{affine}

\section{Acknowledgments}
Thanks to: Igor Sergeev for bringing \cite{Todd} and \cite{Igor} to my attention, and for his assistance in helping me understand his TFT algorithm; Mark Giesbrecht for feedback; Joris van der Hoeven for posing the question of non-invertible TFTs; and Dan Roche for providing his implementation of bit-reversed TFT algorithms.

\bibliographystyle{abbrv}