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

Collapse
This topic is closed.
X
X
 
  • Time
  • Show
Clear All
new posts
  • John

    #1

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

    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

    #2
    Re: quick question: \floor(\log_2(i x))

    > What is the fastest way to implement this function if ix is[color=blue]
    > an integer. Would i need to convert ix to float? What is the
    > fastest way to code this function?[/color]

    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


    Comment

    • Risto Lankinen

      #3
      Re: quick question: \floor(\log_2(i x))


      "John" <weekender_ny@y ahoo.com> wrote in message
      news:1113199426 .528789.281990@ o13g2000cwo.goo glegroups.com.. .[color=blue]
      > What is the fastest way to implement this function if ix is
      > an integer.[/color]

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



      Comment

      • CBFalconer

        #4
        Re: quick question: \floor(\log_2(i x))

        John wrote:[color=blue]
        >
        > 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?[/color]

        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.c om, 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

        Comment

        • John

          #5
          Re: quick question: \floor(\log_2(i x))

          Sorry about that, the function I am interested in is

          \floor(\log_2(i x))

          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

          Comment

          • Chris Croughton

            #6
            Re: quick question: \floor(\log_2(i x))

            On Mon, 11 Apr 2005 09:17:20 +0200, Niels Dybdahl
            <ndy@fjern.dett eesko-graphics.com> wrote:
            [color=blue][color=green]
            >> 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?[/color]
            >
            > The fastest way is a giant lookup table which maybe is impossible to
            > implement.[/color]

            It's certainly impractical.
            [color=blue]
            > 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];[/color]

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

            int log2int(uint_ty pe 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

            Comment

            • Rolf Magnus

              #7
              Re: quick question: \floor(\log_2(i x))

              Risto Lankinen wrote:
              [color=blue][color=green]
              >> What is the fastest way to implement this function if ix is
              >> an integer.[/color]
              >
              > If the design counts as a part of "implementi ng", just start typing
              > the first idea you get. If the design does _not_ count as a part of
              > "implementi ng", use some time to find the shortest design you can,
              > and type it in really quickly.[/color]

              Or write a program that produces the code.

              Comment

              • pete

                #8
                Re: quick question: \floor(\log_2(i x))

                Chris Croughton wrote:
                [color=blue]
                > while (ix & ~0xFFFF)[/color]

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

                --
                pete

                Comment

                • pete

                  #9
                  Re: quick question: \floor(\log_2(i x))

                  John wrote:[color=blue]
                  >
                  > 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?[/color]

                  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

                  Comment

                  • Chris Croughton

                    #10
                    Re: quick question: \floor(\log_2(i x))

                    On 11 Apr 2005 02:06:07 -0700, John
                    <weekender_ny@y ahoo.com> wrote:
                    [color=blue]
                    > Sorry about that, the function I am interested in is
                    >
                    > \floor(\log_2(i x))
                    >
                    > 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).[/color]

                    In that case, the simple one:

                    int log2int(uint_ty pe 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_ty pe 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

                    Comment

                    • CBFalconer

                      #11
                      Re: quick question: \floor(\log_2(i x))

                      John wrote:[color=blue]
                      >
                      > Sorry about that, the function I am interested in is
                      >
                      > \floor(\log_2(i x))
                      >
                      > 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).[/color]

                      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.

                      --
                      "If you want to post a followup via groups.google.c om, 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


                      Comment

                      • Chris Croughton

                        #12
                        Re: quick question: \floor(\log_2(i x))

                        On Mon, 11 Apr 2005 11:01:15 GMT, pete
                        <pfiland@mindsp ring.com> wrote:
                        [color=blue]
                        > Chris Croughton wrote:
                        >[color=green]
                        >> while (ix & ~0xFFFF)[/color]
                        >
                        > If 0xFFFF is of type unsigned and if unsigned is a 16 bit type,
                        > then ~0xFFFF equals zero.[/color]

                        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

                        Comment

                        • Keith Thompson

                          #13
                          Re: quick question: \floor(\log_2(i x))

                          Chris Croughton <chris@keristor .net> writes:[color=blue]
                          > On 11 Apr 2005 02:06:07 -0700, John
                          > <weekender_ny@y ahoo.com> wrote:
                          >[color=green]
                          >> Sorry about that, the function I am interested in is
                          >>
                          >> \floor(\log_2(i x))
                          >>
                          >> 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).[/color]
                          >
                          > In that case, the simple one:
                          >
                          > int log2int(uint_ty pe 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).[/color]

                          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.

                          --
                          Keith Thompson (The_Other_Keit h) kst-u@mib.org <http://www.ghoti.net/~kst>
                          San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
                          We must do something. This is something. Therefore, we must do this.

                          Comment

                          • pete

                            #14
                            Re: quick question: \floor(\log_2(i x))

                            Chris Croughton wrote:[color=blue]
                            >
                            > On Mon, 11 Apr 2005 11:01:15 GMT, pete
                            > <pfiland@mindsp ring.com> wrote:
                            >[color=green]
                            > > Chris Croughton wrote:
                            > >[color=darkred]
                            > >> while (ix & ~0xFFFF)[/color]
                            > >
                            > > If 0xFFFF is of type unsigned and if unsigned is a 16 bit type,
                            > > then ~0xFFFF equals zero.[/color]
                            >
                            > 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).[/color]

                            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.
                            [color=blue]
                            > Chris Croughton wrote:[color=green]
                            >> On Mon, 11 Apr 2005 09:17:20 +0200, Niels Dybdahl
                            >> <ndy@fjern.dett eesko-graphics.com> wrote:[color=darkred]
                            >> >> 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.[/color]
                            >>
                            >> It's certainly impractical.
                            >>[color=darkred]
                            >> > 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];[/color]
                            >>
                            >> If you want to make it generic for any size of integer,
                            >> you could do the first part in a loop:
                            >>
                            >> int log2int(uint_ty pe ix)
                            >> {
                            >> int i;
                            >> while (ix & ~0xFFFF)
                            >> {
                            >> i += 16;
                            >> ix >>= 16;
                            >> }
                            >> return logInt[ix] + i;
                            >> }
                            >>
                            >> where uint_type is whatever unsigned integer type you like.[/color][/color]


                            --
                            pete

                            Comment

                            • pete

                              #15
                              Re: quick question: \floor(\log_2(i x))

                              Chris Croughton wrote:[color=blue]
                              >
                              > On Mon, 11 Apr 2005 09:17:20 +0200, Niels Dybdahl
                              > <ndy@fjern.dett eesko-graphics.com> wrote:[/color]
                              [color=blue][color=green]
                              > > if (ix & 0xffff0000)[/color][/color]
                              [color=blue]
                              > while (ix & ~0xFFFF)[/color]

                              The portable expression is (ix > 0xffff)

                              --
                              pete

                              Comment

                              Working...