quick question: \floor(\log_2(ix))

[Kanenas]

What is the fastest way to implement this function if ix is
an integer. Would i need to convert ix to float? What is the
fastest way to code this function?

Thanks,
--j

As CBFalconer said, this really isn't a C/C++ question. I think
there's a newsgroup which covers numeric programming;
sci.math.num-analysis may be it (check its FAQ). You've faced enough
ribbing, though, so here's a little more help.

A binary search algorithm on an integer using integer powers of 2 as
bounds will give you O(lg(n)) timing, where n is the number of bits in
the integer representation (assuming multiplication and division by
powers of 2 and calculating powers of 2 are O(1)). This technique can
be extended to representations in base b, using integer powers of b as
bounds. Timing for the algorithm for base b will be:
O(lg(n))*T(a*B)*T(a/B)*T(b**k),
where T(f) is the timing for f, B is any integer power of b and x**y
is x to the y-th power.

There may be a HAKMEM about floorlg which has better timing using some
number theoretic approach or involving properties of a specific
representation.

Kanenas

 

[pete]

On Tue, 12 Apr 2005 08:36:12 GMT, pete


I prefer unsigned long, but to each his own...

I call it long unsigned to help me remember %lu.

 

[Chris Croughton]

I call it long unsigned to help me remember %lu.

I don't think I've ever seen it written that way round in code. Your
mnemonic is logical but (in my experience) not at all common...

Chris C