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]

"John" <we**********@yahoo.com> wrote in message
news:11**********************@o13g2000cwo.googlegr oups.com...

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]

John wrote:

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.

--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson

[Chris Croughton]

On Mon, 11 Apr 2005 09:17:20 +0200, Niels Dybdahl
<nd*@fjern.detteesko-graphics.com> wrote:

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.

Chris C

[Rolf Magnus]

Risto Lankinen wrote:

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.

Or write a program that produces the code.

[pete]

John wrote:

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);
}

--
pete

[Martin Eisenberg]

John wrote:

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.

--
Quidquid latine dictum sit, altum viditur.

[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

[Kanenas]

On 10 Apr 2005 23:03:46 -0700, "John" <we**********@yahoo.com> wrote:

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
--
PROBLEM 96:
Solve Go. About 10^170 positions.