Efficient multiple-precision integer division algorithm

Design and implementation of division algorithm is one of the most complicated problems in multi-precision arithmetic. Huang et al. 1] proposed an efficient multi-precision integer division algorithm, and experimentally showed that it is about three times faster than the most popular algorithms proposed by Knuth 2] and Smith 3]. This paper reports a bug in the algorithm of Huang et al. 1], and suggests the necessary corrections. The theoretical correctness proof of the proposed algorithm is also given. The resulting algorithm remains as fast as that of 1].