Fast Basecases for Arbitrary-Size Multiplication
Multiple precision libraries typically use assembly-optimized loops for basecase operations on variable-length operands. We consider the alternative of generating lookup tables with hardcoded routines for many fixed sizes, e.g. for all multiplications up to 16 by 8 words. On recent ARM64 and x86-64 CPUs, we demonstrate up to a 2x speedup over GMP for basecase-sized multiplication and a 20% speedup for Karatsuba-sized operands. We pay special attention to the computation of approximate products and demonstrate up to a 3x speedup over GMP/MPFR for floating-point multiplication.
Authors
- Fredrik Johansson (ORCID: https://orcid.org/0000-0002-7368-092X)
- Albin Ahlbäck
Institutions
- Centre National de la Recherche Scientifique (FR)
- Institut national de recherche en sciences et technologies du numérique (FR)
- Laboratoire d'Informatique de l'École Polytechnique (FR)
- Institut de Mathématiques de Bordeaux (FR)
Publication Details
- Published
- 2025-05-04
- DOI
- https://doi.org/10.1109/arith64983.2025.00018
- Primary Topic
- Low-power high-performance VLSI design
- Type
- article
- Field-Weighted Citation Impact
- 0.00