Faster truncated integer multiplication

arXiv preprint (Mar 2017).

Abstract

We present new algorithms for computing the low n bits or the high n bits of the product of two n-bit integers. We show that these problems may be solved in asymptotically 75% of the time required to compute the full 2n-bit product, assuming that the underlying integer multiplication algorithm relies on computing cyclic convolutions of real sequences.

Code

Here is the demonstration code referred to in the paper.


Back to the main page