base 2 log of X

This is a discussion on base 2 log of X within the C++ Programming forums, part of the General Programming Boards category; I need to dinamically calculate the necessary bits to hold unsigned integrals subsets of varied size, sum these results and ...

  1. #1
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Portugal
    Posts
    7,581

    base 2 log of X

    I need to dinamically calculate the necessary bits to hold unsigned integrals subsets of varied size, sum these results and construct a std::bitset based on the final result.

    But I can't seem to find a way to solve ceil(log2(x)) with the standard library.

    The problem is with the log2(x), since apparently only the common and natural logarithms are offered.

    Am I failing to see some other function? Is there a mathematical equivalent equation I can use?
    The programmer’s wife tells him: “Run to the store and pick up a loaf of bread. If they have eggs, get a dozen.”
    The programmer comes home with 12 loaves of bread.


    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

  2. #2
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,762
    Am I failing to see some other function? Is there a mathematical equivalent equation I can use?
    logr(x) = logk(x) / logk(r)

    Basically, using any constant radix, put log of x over the log of the desired radix and the answer is converted.

  3. #3
    Captain - Lover of the C
    Join Date
    May 2005
    Posts
    341
    This might help:
    Code:
    loga(b) = log(b) / log (a)
    [edit]beaten by like a second![/edit]
    Don't quote me on that... ...seriously

  4. #4
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Portugal
    Posts
    7,581
    If it wasn't for that crude beard of yours I could kiss you.

    Thanks a bunch!
    The programmer’s wife tells him: “Run to the store and pick up a loaf of bread. If they have eggs, get a dozen.”
    The programmer comes home with 12 loaves of bread.


    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

  5. #5
    Registered User
    Join Date
    Sep 2001
    Posts
    752
    Don't use the log function to count bits. Putting aside the efficiency issue, consider accuracy. Since it turns the problem to floating point numbers, expressions like the following are ambiguous:

    Code:
    int(log(4) / log(2)
    Is it int(.602059991/.301029995), or it int(.602059991/.301029996)? It's impossible to tell because of floating point precision.

    Just shift bits if need be.
    Last edited by QuestionC; 06-25-2007 at 03:16 PM. Reason: Mistyped one of the decimals
    Callou collei we'll code the way
    Of prime numbers and pings!

  6. #6
    Registered User
    Join Date
    Sep 2001
    Posts
    752
    Well, either shift bits or get creative if efficiency matters.
    Callou collei we'll code the way
    Of prime numbers and pings!

  7. #7
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,834
    > But I can't seem to find a way to solve ceil(log2(x)) with the standard library.
    Isn't this going to be in effect the left most bit shifted left one place?

    In binary, say you have 0101b (5) samples to store. The left-most bit is 0100b (4), which then shifted left one place is 1000b (8).
    So you allocate space for 8, to store a maximum of 5 samples.

    OK, maybe it's not the most accurate answer, but it's a lot easier to calculate.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  8. #8
    Registered User
    Join Date
    Sep 2001
    Posts
    752
    Actually, it's the number of bits.

    ciel(log2(1-2)) -> 1
    ciel(log2(3-4)) -> 2
    ciel(log2(5-8)) -> 3

    Well, there's the edge case on powers of 2, so technically floor(log2(x)) + 1. In any case, bit manipulation is totally the way to go.
    Callou collei we'll code the way
    Of prime numbers and pings!

  9. #9
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Portugal
    Posts
    7,581
    Thanks for the info guys. Much better options, no doubt.
    The programmer’s wife tells him: “Run to the store and pick up a loaf of bread. If they have eggs, get a dozen.”
    The programmer comes home with 12 loaves of bread.


    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Code review
    By Elysia in forum C++ Programming
    Replies: 71
    Last Post: 05-13-2008, 10:42 PM
  2. is there a log base 2 function?
    By qubit67 in forum C Programming
    Replies: 3
    Last Post: 05-02-2007, 02:08 AM
  3. Base Converter Part 2
    By encyclopedia23 in forum C Programming
    Replies: 2
    Last Post: 12-30-2006, 02:42 PM
  4. searching problem
    By DaMenge in forum C Programming
    Replies: 9
    Last Post: 09-12-2005, 02:04 AM
  5. Calculate log base e by recursion function.
    By alice in forum C Programming
    Replies: 0
    Last Post: 04-24-2004, 12:51 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21