Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > quick question: \floor(\log_2(ix))

Reply
Thread Tools

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

 
 
John
Guest
Posts: n/a
 
      04-11-2005
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

 
Reply With Quote
 
 
 
 
Niels Dybdahl
Guest
Posts: n/a
 
      04-11-2005
> 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


 
Reply With Quote
 
 
 
 
Risto Lankinen
Guest
Posts: n/a
 
      04-11-2005

"John" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed) 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.



 
Reply With Quote
 
CBFalconer
Guest
Posts: n/a
 
      04-11-2005
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

 
Reply With Quote
 
Chris Croughton
Guest
Posts: n/a
 
      04-11-2005
On Mon, 11 Apr 2005 09:17:20 +0200, Niels Dybdahl
<(E-Mail Removed)-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
 
Reply With Quote
 
Rolf Magnus
Guest
Posts: n/a
 
      04-11-2005
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.

 
Reply With Quote
 
pete
Guest
Posts: n/a
 
      04-11-2005
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
 
Reply With Quote
 
Martin Eisenberg
Guest
Posts: n/a
 
      04-12-2005
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.
 
Reply With Quote
 
John
Guest
Posts: n/a
 
      04-13-2005

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

 
Reply With Quote
 
Kanenas
Guest
Posts: n/a
 
      04-13-2005
On 10 Apr 2005 23:03:46 -0700, "John" <(E-Mail Removed)> 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.

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Adding quick-release to a non-quick-release tripod head ste7esmith@hotmail.com Digital Photography 4 11-20-2006 03:19 PM
Quick question, hopefully quick answer. ~misfit~ NZ Computing 114 01-06-2005 01:36 PM
Quick Question Quick Answer JKop C++ 11 05-24-2004 09:46 PM
Quick Restore for a Compaq not so quick! Croos Bustamunky Computer Support 2 05-15-2004 04:17 AM
PanasonicBQ390 "quick" charger - How quick? Ol' Bab Digital Photography 1 01-17-2004 06:54 AM



Advertisments