Efficient multiple-precision integer division algorithm |
| |
Authors: | Debapriyay Mukhopadhyay Subhas C. Nandy |
| |
Affiliation: | 1. IXIA Technologies Pvt. Ltd., Kolkata 700091, India;2. Indian Statistical Institute, Kolkata 700108, India |
| |
Abstract: | 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]. |
| |
Keywords: | Division algorithm Normalization Computational arithmetic Cryptography |
本文献已被 ScienceDirect 等数据库收录! |