Author fredrikj
Recipients fredrikj, loewis, mark.dickinson, rhettinger, terry.reedy
Date 2008-10-14.10:38:43
SpamBayes Score 6.02613e-10
Marked as misclassified No
Message-id <1223980726.37.0.561874485137.issue3439@psf.upfronthosting.co.za>
In-reply-to
Content
Some elaboration (that perhaps could be adapted into the documentation
or at least source comments).

There are two primary uses for numbits, both of which justify
(0).numbits() == 0.

The first is that for positive k, n = k.numbits() gives the minimum
width of a register that can hold k, where a register can hold the 2**n
integers 0, 1, ..., 2**n-1 (inclusive). This definition continues to
make sense for k = 0, n = 0 (the empty register holds the 2**0 = 1
values 0).

In Python terms, one could say that self.numbits() "returns the smallest
n such that abs(self) is in range(2**n)". Perhaps this would make a
clearer docstring?

Second, k.numbits() (plus/minus 1, or perhaps multiplied by a constant
factor) measures the number of steps required to solve a problem of size
k using various divide-and-conquer algorithms. The problem of size k = 0
is trivial and therefore requires (0).numbits() == 0 steps.

In particular, if L is a sorted list, then len(L).numbits() exactly
gives the maximum number of comparisons required to find an insertion
point in L using binary search.

Finally, the convention (-k).numbits() == k.numbits() is useful in
contexts where the number k itself is the input to a mathematical
function. For example, in a function for multiplying two integers, one
might want to choose a different algorithm depending on the sizes of the
inputs, and this choice is likely to be independent of signs (if not,
one probably needs to check signs anyway.)
History
Date User Action Args
2008-10-14 10:38:46fredrikjsetrecipients: + fredrikj, loewis, rhettinger, terry.reedy, mark.dickinson
2008-10-14 10:38:46fredrikjsetmessageid: <1223980726.37.0.561874485137.issue3439@psf.upfronthosting.co.za>
2008-10-14 10:38:45fredrikjlinkissue3439 messages
2008-10-14 10:38:43fredrikjcreate