[boost] Re: A question about static_log2

From: Vesa Karvonen (vesa_karvonen_at_[hidden])
Date: 2003-01-24 05:55:56

Gennaro Prota:
>Vesa, I really appreciate your attempt but your code assumes the
>required number to be a power of two (it just tries 32, 64, 128,
>etc.). What about 48 bits unsigned long?[...]

If unsigned long has 48 bits, then an n of 32 would be chosen.

There are good reason to choose an n that is a power of two:
1) The initial n can be calculated quickly. It will take Theta(log(M)) steps 
to find a proper n when unsigned long has M (value) bits. In other words, 
choose_n<> is simple and efficient.
2) Using only powers of two for n, you will need a maximum of one extra 
recursion of the core algorithm. In the worst case, both algorithms need 
exactly as many recursions.
3) if you want to allow other than powers of two in the core algorithm, and 
especially if you want to make it possible to save the one recursion, you 
would need to complicate the algorithm considerably. Specifically, if you 
are not using only powers of two,
3.b) you will need to round-up when you divide n by 2, in order to have a 
correct algorithm (consider the case when n would be 3).
3.c) you would have to distinguish between cases when the number is 
higher-than-or-equal-to and lower-than 1ul<<n, in order to save the one 
recursion (consider the case when n is 2, but you know that the "reduced" 
value has only 3 (rather than 4) bits).

-Vesa

_________________________________________________________________
Add photos to your messages with MSN 8. Get 2 months FREE*. 
http://join.msn.com/?page=features/featuredemail