magicg.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 signed division, given a max value of
the magnitude of the dividend, and a divisor. The divisor must be > 0.
   This uses equations (5) and (6) on page 162, 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 -nmax <= n <= nmax.
   It is much simpler than the program given in Hacker's Delight
(Figure 10-1) because in Python, one need not be concerned about
overflowing the word size in which the computations are done.
  Check these:
  Example: magicg(255, 7) is a 9-bit number, but magicg(200, 7) is an
8-bit number.
   Also, magicg(127, 7) is an 8-bit number, but magicg(90, 7) is a
6-bit number.
   Good test case: magicg 61 55 = 0x4B, shift = 12,
This has the shift at the maximum value of 2*nbits = 2*6 (c.f. Hacker's
Delight 2nd ed. p. 213 eqn (8), with W = nbits + 1). """

import sys

# ----------------------------- magicg ---------------------------------

def magicg(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 - (2**p)%d):
         m = (2**p + d - (2**p)%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) = magicg(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)