Faster truncated integer multiplication

arXiv preprint (Mar 2017).


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.


Here is the demonstration code referred to in the paper.

Back to the main page