Technology reports of the Yamaguchi University

Back to Top

Technology reports of the Yamaguchi University Volume 2 Issue 3
published_at 1979-12

A modified algorithm for taking reciprocal of n-bit integers

A modified algorithm for taking reciprocal of n-bit integers
Taniguchi Hiroshi
Takanami Itsuo
Inoue Katsushi
fulltext
408 KB
KJ00004350999.pdf
Descriptions
For an integer P whose bit-length is just n, its reciprocal is defined by [2^<2n-1>/P], where [x] denotes the greatest integer equal to or less than x. It is well known that the time for taking reciprocal is, to within a constant factor, the same as the time to do integer multiplication in bit operation. So we first explain Cook's Algorithm which requires the same order of time as multiplication. Next, we propose a modified algorithm and prove its correctness and analyse the complexity of computation. This shows that the algorithm is expected to improve constant factor in complexity.