Paperlane

no. 16 · Tuesday 17 November 2026

Quasilinear multiplication in the Cayley-Dickson tower

Harrison Lemley

math.RA · v3 · 45 pp

Abstract

Direct evaluation of the defining product of the Cayley-Dickson algebra $A_n$ of rank $N:=2^n$ over a unital commutative ring $R$ requires a quadratic number of arithmetic operations. This paper gives a uniform bilinear algorithm for multiplication in this algebra when $2 \in R^\times$, costing $O(N \log N)$ arithmetic operations in $R$ and $O(N)$ auxiliary storage when the doubling parameters of $A_n$ are units whose square roots lie in a fixed commutative coefficient algebra $S$ finitely generated as an $R$-module and admitting an $R$-linear map $π\colon S \to R$ with $π(1) = 1$. In particular, the algorithm applies to every Cayley-Dickson tower over $\mathbb{R}$ and finite fields $\mathbb{F}_q$ of odd characteristic, and the tensor rank of multiplication in $A_n$ over these fields is at most $(36n-69)2^{n-3}+10$ when $n\ge4$. To the author's knowledge, the algorithm presented in this paper is the first uniform subquadratic algorithm for multiplication in $A_n$. An implementation for the standard tower over $\mathbb{R}$, $\mathbb{C}$, and $\mathbb{F}_q$ for $q = p^k$ with $p \le 2^{31}-1$ an odd prime and $k \le 12$ is available in the MIT-licensed C11 library fastCD, with a NumPy-backed Python interface pyfastcd, available on PyPI. In single-core benchmarks against direct multiplication and the uniform Cariow-Cariowa method over $\mathbb{R}$, the quasilinear implementation had the lowest mean time of the three at every tested dimension $N\ge32$ for both single and batched products and was over $17$ times faster than direct multiplication.

comments
45 pages, 7 tables. v3: Added appendix for octonion base case used in fastCD and the tensor rank bound; extended Section 5 with results for the complex numbers and finite fields; added floating-point error measurements to Section 5; updated disclosures in Section 7. Code: https://git.tanuki-cd.com/algebraity/fastCD
fields
Rings and Algebras, Numerical Analysis
pdf ↗ page arXiv:2609.11588 ↗