magicgu.py.txt

#!/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)