Message74725
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.) |
|
Date |
User |
Action |
Args |
2008-10-14 10:38:46 | fredrikj | set | recipients:
+ fredrikj, loewis, rhettinger, terry.reedy, mark.dickinson |
2008-10-14 10:38:46 | fredrikj | set | messageid: <1223980726.37.0.561874485137.issue3439@psf.upfronthosting.co.za> |
2008-10-14 10:38:45 | fredrikj | link | issue3439 messages |
2008-10-14 10:38:43 | fredrikj | create | |
|