Asymptotic Optimality of Parallel Short Division

摘要

In 2011 we published a practical algorithm for short division (division of a multiple precision dividend by a single precision divisor) on a parallel processor (HiPC 2011) with a run time of O(n/p+log p). Our algorithm, based on parallel computation of remainder sequences, is an improvement of Takahashi's earlier work (LSSC 2007) which has a run time of O((n/p) log p). Here we prove that Omega(n/p+log p) is a tight lower bound for short division (using a conventional fixed radix number system) on EREW and CREW PRAMs when the divisor d is not simply a power of two. The proof is based on an application of Cook, Dwork, and Reischuk's work on Boolean function complexity. The result itself is especially significant because it establishes a novel tight lower bound for two fundamental arithmetic operations, short division and division by a fixed constant, on an important class of parallel machines.