2017/03/02 by Harvey, David
#68W30 (Primary) #Data Structures and Algorithms (cs.DS) #F.2.1 #FOS: Computer and information sciences #G.1.0 #Symbolic Computation (cs.SC)
paper · doi:10.48550/arxiv.1703.00640
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.