The Karatsuba integer middle product

J. Symb. Comp. 47 (2012), 954–967 (DOI).

Preprint (November 2009) (published version is substantially revised and improved).

Abstract

We study the problem of computing middle products of multiple-precision integers. In particular we adapt the Karatsuba polynomial middle product algorithm to the integer case, showing how to efficiently mitigate the failure of bilinearity of the integer middle product noted by Hanrot, Quercia and Zimmermann.

Code

This patch may be applied to the GMP 4.3.1 repository (changeset 2ceda39b5a7f). See here for hints on how to build from the repo.

It contains several new files/routines, and some test/profiling code in the mulmid-test subdirectory.

Most of the code is licensed under a BSD-style license, except for files derived from GMP 4.3.1, which are licensed under LGPLv3+.

This patch is similar but includes code for approximate reciprocal (and no B-adic division code). Search for "mpn_invert_mp".

I have also written proof-of-concept approximate division code. Please email me if you are interested in seeing the code.


Back to the main page