A modified algorithm for taking reciprocal of n-bit integers
Technology reports of the Yamaguchi University Volume 2 Issue 3
Page 307-315
published_at 1979-12
Title
A modified algorithm for taking reciprocal of n-bit integers
Creators
Taniguchi Hiroshi
Creators
Takanami Itsuo
Creators
Inoue Katsushi
Source Identifiers
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.
Languages
eng
Resource Type
departmental bulletin paper
Publishers
山口大学工学部
Date Issued
1979-12
File Version
Version of Record
Access Rights
open access
Relations
[ISSN]0386-3433
[NCID]AA0086073X
Schools
工学部