A modified algorithm for taking reciprocal of n-bit integers

A modified algorithm for taking reciprocal of n-bit integers

Creators Taniguchi Hiroshi

Creators Takanami Itsuo

Creators Inoue Katsushi

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.

[ISSN]0386-3433

[NCID]AA0086073X