fastCD

fastCD is a mathematics library written in C11 for arithmetic in the standard real Cayley–Dickson algebras. It implements a quasilinear multiplication algorithm, which requires O(N log N) real arithmetic operations and O(N) auxiliary storage for an algebra of dimension N. The supported tower includes the real numbers, complex numbers, quaternions, octonions, sedenions, and higher power-of-two dimensions, subject to storage and checked size limits.

The library serves both as an implementation of the algorithm for research and as a numerical kernel for scientific, engineering, and commercial applications. Its C interface uses caller-owned arrays of double coefficients, performs no allocation during arithmetic, and requires only the C standard library and the system math library. The accompanying pyfastcd package provides Python objects and compiled NumPy array operations over the same kernel.

fastCD concentrates on numerical arithmetic and matrix-free operators. It does not provide symbolic algebra, arbitrary coefficient fields, or linear solvers. All code is distributed under the MIT License.

The canonical source repository is git.tanuki-cd.com/algebraity/fastCD.

Features

• Quasilinear Cayley–Dickson multiplication in arbitrary power-of-two dimensions.
• Scalar and basis construction, coordinate arithmetic, conjugation, inner products, norms, normalization, and reciprocals.
• Imaginary alternating products, commutators, associators, and left/right multiplication-operator commutators without constructing dense matrices.
• Allocation-free C operations, explicit workspace queries, checked dimensions and buffer relationships, and strided batch multiplication.
• Immutable Python elements and compiled operations on arrays with shape (..., dimension), including NumPy broadcasting.
• Independent defining-doubling reference implementations and retained Karatsuba-style, Cariow–Cariowa, and direct multiplication for verification and benchmarking.
• Reproducible research benchmarks with shared random corpora, source-level operation counts, repeated measurements, and machine-readable results.

Mathematical convention

For the standard tower, fastCD uses

A_0 = R
A_n = A_(n-1) + A_(n-1)
(a,b)(c,d) = (ac - conjugate(d)b, da + b conjugate(c)).

An element is a contiguous array of N = 2^n C double coefficients in the recursive standard basis. Coordinate zero is scalar. See the mathematical conventions for identities and operator ordering, and the multiplication guide for the algorithm, arithmetic counts, and scratch schedule.

Building and testing

A C11 compiler and CMake 3.18 or newer are required. On Unix-like systems, the library links the standard math library, libm.

From the repository root, run:

cmake -S . -B build -DCMAKE_BUILD_TYPE=Release
cmake --build build --config Release --parallel
cmake -E chdir build ctest -C Release --output-on-failure

The default builds a static library, tests, benchmarks, and development tools. Use -DBUILD_SHARED_LIBS=ON for a shared library. For a library-only build, disable BUILD_TESTING, FASTCD_BUILD_BENCHMARKS, and FASTCD_BUILD_TOOLS. The development guide lists all options and validation recipes.

Install the C library with:

cmake --install build --config Release --prefix /desired/prefix

The installation includes <fastcd/fastcd.h>, libfastcd, the MIT license, and a CMake package. Applications can use find_package(fastcd CONFIG REQUIRED) and link fastcd::fastcd. Diagnostic algorithms and private headers are excluded from the installed C library.

C use

#include <stdlib.h>
#include <fastcd/fastcd.h>

int main(void) {
    double x[16] = {1.0, 2.0};
    double y[16] = {3.0, 4.0};
    double product[16];
    size_t scratch_length;

    if (fastcd_mul_workspace_size(16, &scratch_length) != FASTCD_SUCCESS)
        return 1;

    double* scratch = scratch_length == 0
            ? NULL : malloc(scratch_length * sizeof(*scratch));
    if (scratch_length != 0 && scratch == NULL)
        return 1;

    FastCDWorkspaceF64 workspace = {scratch, scratch_length};
    FastCDStatus status = fastcd_mul_f64(product, x, y, 16,
            scratch_length == 0 ? NULL : &workspace);

    free(scratch);
    return status == FASTCD_SUCCESS ? 0 : 1;
}

Workspace lengths count double elements, not bytes. Query the required length and reuse scratch sequentially. Multiplication output, inputs, and active scratch must be disjoint, except that the two inputs may be the same complete array. See the C API reference for all contracts, including batching and concurrent calls.

Python use

The Python interface requires CPython 3.10 or newer and NumPy 1.26 or newer. Install from a source checkout:

python -m pip install .

Then construct an algebra and use ordinary Python operators:

import numpy as np
import pyfastcd as fcd

O = fcd.Algebra(dimension=8)
a = O([1, 2, 3, 4, 5, 6, 7, 8])
b = O.basis(2)

product = a * b
square = a ** 2
commutator = a.commutator(b)

x = O.asarray(np.ones((1000, 8), dtype=np.float64))
y = x * b

Element is immutable. ElementArray processes batches in compiled code. Use O.array(values) for an owning copy and O.asarray(values, copy=False) when compatible zero-copy storage is required. Ordinary multiplication uses the quasilinear kernel; named diagnostic methods expose comparison algorithms. The extension statically links fastCD, so no separate libfastcd installation is needed. See the Python guide for usage, array interoperability, and supported interpreter configurations.

Numerical behavior

Multiplication uses ordinary double arithmetic. Different schedules can round differently, lose precision through cancellation, or overflow intermediates even when the exact result is representable. Scale inputs where needed and validate error for your workload; the complexity bound is not an accuracy guarantee. Norms, normalization, and reciprocals use scaled evaluation.

Reciprocals compute conjugate(x) / norm_squared(x); they do not solve general left or right division equations. Above the octonions, multiplication is not alternative and nonzero zero divisors exist. Explicit parenthesization matters. See the mathematical guide for these distinctions.

Benchmarking

A local correctness and arithmetic-count comparison is:

./build/fastcd_benchmark \
    --level 6 \
    --trials 10000 \
    --methods reference,cc,karatsuba,quasilinear,default \
    --verify \
    --count-ops

With a multi-configuration generator, use ./build/Release/fastcd_benchmark (with .exe on Windows).

default measures the public production call. quasilinear and karatsuba measure the two algorithms through the same private diagnostic interface. Whole Cariow–Cariowa multiplication is available at power-of-two dimensions from 2 through 64.

The publication protocol uses 10,000 deterministic random multiplication pairs per dimension, one logical CPU, independent reference verification, balanced method order, and repeated aggregate timing. The Xeon Gold 6148 results include C and Python timings through dimension 1024, including 512, with confidence intervals and verification errors. The benchmark guide supplies reproduction commands and defines the timing boundaries and provenance. Timings describe the recorded machine, build, and workload.

Documentation

The library guide links the complete C and Python references, mathematical definitions, multiplication algorithms, operator conventions, benchmark protocol, and development checks.

License and attribution

fastCD and its associated code are licensed under the MIT License.

The quasilinear algorithm and retained Karatsuba-style construction are due to Harrison Lemley, Quasilinear multiplication in the Cayley–Dickson algebras (September 2026 manuscript). The diagnostic fixed-kernel construction follows Aleksandr Cariow and Galina Cariowa, An unified approach for developing rationalized algorithms for hypercomplex number multiplication, Przeglad Elektrotechniczny 91(2), 36–39 (2015).