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

[John]

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

 

[Niels Dybdahl]

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?

The fastest way is a giant lookup table which maybe is impossible to
implement.
Second fastest (for common 32 bit integers) might be a 16 bit lookup table
and something like:

int logInt[65536]; // Should be initialized properly
....
if (ix & 0xffff0000)
return logInt[ix >> 16]+16;
else
return logInt[ix & 0xffff];

Niels Dybdahl

 

[Risto Lankinen]

What is the fastest way to implement this function if ix is
an integer.

If the design counts as a part of "implementing", just start typing
the first idea you get. If the design does _not_ count as a part of
"implementing", use some time to find the shortest design you can,
and type it in really quickly.

 

[CBFalconer]

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?

What function? Many systems do not show the subject when
displaying the message.

At any rate speed is not the concern of the standard, and depends
on the exact system in use. Thus it is off-topic in c.l.c.
Probably also in c.l.c++, but at any rate that is a different
language and things should not be crossposted between there and
here. F'ups set.

 

[John]

Sorry about that, the function I am interested in is

\floor(\log_2(ix))

And I'm looking towards a more computational solution than
a large table lookup. I can not afford to store large tables. (At
most a few bytes...64/128 bytes space maybe at most).

Thanks,
--j

 

[Chris Croughton]

The fastest way is a giant lookup table which maybe is impossible to
implement.

It's certainly impractical.

Second fastest (for common 32 bit integers) might be a 16 bit lookup table
and something like:

int logInt[65536]; // Should be initialized properly
...
if (ix & 0xffff0000)
return logInt[ix >> 16]+16;
else
return logInt[ix & 0xffff];

If you want to make it generic for any size of integer, you could do the
first part in a loop:

int log2int(uint_type ix)
{
int i;
while (ix & ~0xFFFF)
{
i += 16;
ix >>= 16;
}
return logInt[ix] + i;
}

where uint_type is whatever unsigned integer type you like.

Chris C

 

[Rolf Magnus]

If the design counts as a part of "implementing", just start typing
the first idea you get. If the design does _not_ count as a part of
"implementing", use some time to find the shortest design you can,
and type it in really quickly.

Or write a program that produces the code.

 

[Chris Croughton]

Sorry about that, the function I am interested in is

\floor(\log_2(ix))

And I'm looking towards a more computational solution than
a large table lookup. I can not afford to store large tables. (At
most a few bytes...64/128 bytes space maybe at most).

In that case, the simple one:

int log2int(uint_type ix)
{
int i;
for (i = -1; ix; ix >>= 1)
++i;
return i;
}

will be much faster than converting to float etc. (and is portable
whatever the actual type of uint_type, as long as it's unsigned
integer of some form).

Doing a "binary chop" on it might be even faster but more convoluted
code (so it might actually work out slower for small values of ix, I
haven't timed them):

#include <limits.h>

int log2int(uint_type ix)
{
int shift = (sizeof(ix) * CHAR_BIT) / 2;
int val = 0;
if (ix == 0)
return -1;
while (ix && shift)
{
uint_type tmp = ix >> shift;
if (tmp)
{
val += shift;
ix = tmp;
}
else
{
shift /= 2;
}
}
return val;
}

Note that the initial value of 'shift' can be any positive value ypu
like (as long as it's greater than 0 and less than the number of bits in
uint_type), setting it to half the number of bits in uint_type is the
most efficient but if you don't want to include limits.h you could
hard-code it to 16 for instance.

(Both functions return -1 as an error value if ix is zero. In the first
that just "falls out" of the algorithm, the second tests explicitly for
it otherwise it would return 0 for ix==0.)

Incidentally, if you do want (int)log2() for a floating point number,
frexp() can be used to extract the exponent+1 (because the result is in
the range [0.5,1)). Or if you have a C99 library you can use logb() to
get the integer log2 value.

Chris C

 

[pete]

while (ix & ~0xFFFF)

If 0xFFFF is of type unsigned and if unsigned is a 16 bit type,
then ~0xFFFF equals zero.

 

[pete]

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?

This is the easiest way to implement log2.

#include <math.h>

double l_og2(double x)
{
static double log_2;

if (0.5 > log_2) {
log_2 = log(2);
}
return x > 0 ? log(x) / log_2 : log(x);
}

 

[CBFalconer]

Sorry about that, the function I am interested in is

\floor(\log_2(ix))

And I'm looking towards a more computational solution than
a large table lookup. I can not afford to store large tables. (At
most a few bytes...64/128 bytes space maybe at most).

Now you are compounding the problem by failing to quote. The point
was to tell you about your faulty posting practices, and I am
really not interested in the thread. Now you need to read my sig
line below with care.

 

[Chris Croughton]

If 0xFFFF is of type unsigned and if unsigned is a 16 bit type,
then ~0xFFFF equals zero.

Yes, so the loop will never be executed, which is correct because ix is
already in the range handled by the array lookup. (It might give a
warning about "condition is always false" on some compilers, but in
general the loop should be not executed and may be optimised away).

Chris C

 

[Keith Thompson]

In that case, the simple one:

int log2int(uint_type ix)
{
int i;
for (i = -1; ix; ix >>= 1)
++i;
return i;
}

will be much faster than converting to float etc. (and is portable
whatever the actual type of uint_type, as long as it's unsigned
integer of some form).

It's not guaranteed to be faster than the floating-point equivalent.
Some systems may have very efficient floating-point hardware. Since
the integer solution uses conditional tests and branches, its effects
on CPU pipelining may make it slower than a floating-point equivalent,
or may have the side effect of slowing down other calculations.

I haven't done any measurements; it may well be that the integer
solution really is faster on most or all real-world systems. The
point is that the only way to determine the performance of a piece of
code is to measure it (and the answer will be applicable only to the
system on which you do the measurements). In some cases, it's obvious
that one algorithm will be faster than another (Quicksort vs. Bubblesort
on large arrays, for example); I don't think this is one of those
cases.

 

[pete]

Yes, so the loop will never be executed,
which is correct because ix is
already in the range handled by the array lookup. (It might give a
warning about "condition is always false" on some compilers, but in
general the loop should be not executed and may be optimised away).

No, that's not the situation. Your function interfaces
with a 65536 element array, which is used as a lookup table.
You specify "uint_type is whatever unsigned integer type you like".

I like long unsigned.
If ix is 65537, and UINT_MAX is 65535 and INT_MAX is 32767, then
while (ix & ~0xFFFF)
is false, and
return logInt[ix] + i;
becomes
return logInt[65537] + i;
and that's undefined behavior.

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?

The fastest way is a giant lookup table
which maybe is impossible to implement.

It's certainly impractical.

Second fastest (for common 32 bit integers)
might be a 16 bit lookup table
and something like:

int logInt[65536]; // Should be initialized properly
...
if (ix & 0xffff0000)
return logInt[ix >> 16]+16;
else
return logInt[ix & 0xffff];

If you want to make it generic for any size of integer,
you could do the first part in a loop:

int log2int(uint_type ix)
{
int i;
while (ix & ~0xFFFF)
{
i += 16;
ix >>= 16;
}
return logInt[ix] + i;
}

where uint_type is whatever unsigned integer type you like.

 

[pete]

On Mon, 11 Apr 2005 09:17:20 +0200, Niels Dybdahl

while (ix & ~0xFFFF)

The portable expression is (ix > 0xffff)

 

[Chris Croughton]

No, that's not the situation. Your function interfaces
with a 65536 element array, which is used as a lookup table.
You specify "uint_type is whatever unsigned integer type you like".

I like long unsigned.

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

If ix is 65537, and UINT_MAX is 65535 and INT_MAX is 32767, then
while (ix & ~0xFFFF)
is false, and
return logInt[ix] + i;

Ah, I see, 0xFFFF is an unsigned int. OK:

while (ix & ~(uint_type)0xFFFF)

Better?

Chris C

 

[Martin Eisenberg]

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?

It's equivalent to the position of the highest set bit in ix, and you
can google for algorithms to find that.

 

[pete]

while (ix & ~(uint_type)0xFFFF)

Better?

Yes.

 

[pete]

And remember to initialize i.

while (ix & ~0xFFFF)
{
i += 16;
ix >>= 16;
}
return logInt[ix] + i;
}

 

[John]

I figured that out,
and I figured out that on x86 machines there is a bit scan
command in assembly (bzr or something). What is the
fastest way to do this on portable machines? Right now
I just use a loop to find the largest bit. It's portable and fast.

Is there a bitscan function for opterons by any chance?

Thanks,
--j