# 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 2*n*-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