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

Discussion in 'C++' started by John, Apr 11, 2005.

  1. John

    John Guest

    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
    John, Apr 11, 2005
    #1
    1. Advertising

  2. > 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
    Niels Dybdahl, Apr 11, 2005
    #2
    1. Advertising

  3. "John" <> wrote in message
    news:...
    > 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.
    Risto Lankinen, Apr 11, 2005
    #3
  4. John

    CBFalconer Guest

    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
    CBFalconer, Apr 11, 2005
    #4
  5. On Mon, 11 Apr 2005 09:17:20 +0200, Niels Dybdahl
    <-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
    Chris Croughton, Apr 11, 2005
    #5
  6. John

    Rolf Magnus Guest

    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.
    Rolf Magnus, Apr 11, 2005
    #6
  7. John

    pete Guest

    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
    pete, Apr 11, 2005
    #7
  8. 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.
    Martin Eisenberg, Apr 12, 2005
    #8
  9. John

    John Guest

    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
    John, Apr 13, 2005
    #9
  10. John

    Kanenas Guest

    On 10 Apr 2005 23:03:46 -0700, "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?
    >
    >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.
    Kanenas, Apr 13, 2005
    #10
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Carson

    log_2 command in vhdl?

    Carson, Oct 5, 2005, in forum: VHDL
    Replies:
    2
    Views:
    3,546
    Olaf Petzold
    Oct 5, 2005
  2. SpaceCowboy
    Replies:
    6
    Views:
    1,081
    Josef Garvi
    Aug 15, 2003
  3. John
    Replies:
    3
    Views:
    347
    Chris Smith
    Feb 11, 2005
  4. JKop
    Replies:
    11
    Views:
    873
  5. John

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

    John, Apr 11, 2005, in forum: C Programming
    Replies:
    22
    Views:
    738
    Chris Croughton
    Apr 15, 2005
Loading...

Share This Page