OFFSET
0,1
COMMENTS
For many odd numbers z, it is possible to compute the integer division of y / z for 0 <= y < 2^64 (that is, floor(y/z)) by multiplying by a suitable constant a and shifting right: floor((a*y)/(2^(64+e))). a is computed as a = ceiling((2^(64+e))/z), where e is such that 2^e < z < 2^(e+1).
Knuth showed that the formula floor((a*y)/(2^(64+e))) = floor(y/z) holds for all y, 0 <= y < 2^64, if and only if it holds for the single value y = 2^64 - 1 - (2^64 mod z).
There are 189 odd divisors z less than 1000 for which this method cannot be used to find the division result for all y, 0 <= y < 2^64.
REFERENCES
Donald Ervin Knuth, The Art of Computer Programming, fascicle 1, _MMIX_. Addison Wesley Longman, 1999. Zeroth printing (revision 8), 24 December 1999. Exercise 19 in section 1.3.1', page 25 and the answer on page 95.
LINKS
EXAMPLE
For the first term in the sequence, 7, floor(ay/(2^(64+e))) = 2635249153387078802 for y = 2^64 - 1 - (2^64 mod z) = 18446744073709551613, while floor(y/z) = 2635249153387078801.
Example for a term not in the sequence: for 9, both floor(ay/(2^(64+e))) and floor(y/z) are 2049638230412172400 for y = 2^64 - 1 - (2^64 mod z) = 18446744073709551608.
CROSSREFS
KEYWORD
nonn
AUTHOR
Philip Newton, Dec 22 2000
EXTENSIONS
Name corrected by Boon Suan Ho, Feb 27 2023
STATUS
approved