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