#!/usr/bin/python
""" Division by Multiplication Considered More Generally
Handles arbitrary max dividends (not necessarily of the form 2**W -
1), and bignums.
Computes the magic number for unsigned division, given a max value of
the dividend, and a divisor.
This uses equations (26) and (27) on page 181, but with nc determined
from the maximum value of n, which is not necessarily 2**W - 1 for W =
the word size of n. It finds the smallest number that can serve for a
multiplier for all n in the range 0 <= n <= nmax.
It is much simpler than the programs given in Hacker's Delight (e.g.,
that of Figure 10-2) because in Python, one need not be concerned about
overflowing the word size in which the computations are done.
Example: magicgu(255, 7) is a 9-bit number, but magicgu(200, 7) is an
8-bit number.
Also, magicgu(127, 7) is an 8-bit number, but magicgu(90, 7) is a
6-bit number. """
import sys
# ----------------------------- magicgu --------------------------------
def magicgu(nmax, d):
nc = ((nmax + 1)//d)*d - 1
nbits = len(bin(nmax)) - 2
for p in range(0, 2*nbits + 1):
if 2**p > nc*(d - 1 - (2**p - 1)%d):
m = (2**p + d - 1 - (2**p - 1)%d)//d
return (m, p)
print "Can't find p, something is wrong."
sys.exit(1)
# ------------------------------ main ----------------------------------
args = sys.argv[1:] # This is to work with Python 2.6 and 2.7.
if len(args) == 1:
args = args[0].split()
if len(args) != 2: print "Wrong number of args, need 2."; sys.exit(1)
nmax = eval(args[0]) # Max value of dividend.
d = eval(args[1]) # Divisor.
if (nmax <= 0 or d <= 0):
print "Both arguments must be > 0."
sys.exit(1)
(m, s) = magicgu(nmax, d)
print "For nmax %d, divisor %d, magic number = hex %X (%d bits), shift = %d" % \
(nmax, d, m, len(bin(m)) - 2, s)
sys.exit(0)