Thread: Bitset initialisation error

  1. #1
    Registered User
    Join Date
    Feb 2012
    Posts
    10

    Bitset initialisation error

    Hi everyone, I'm having trouble compiling a sieve of eratosthenes function. I'm using a bitset. The algorithm should work, but the problem lies in the variable bitset size.

    Code:
    vector<int> Erat(int n)
    {
    bitset<n> sieve;
    
    ...
    
    }
    This won't compile. If I change the bitset<n> to e.g. bitset<100>, it all compiles well. I've tried const int n, unsigned int n, but nothing works.

    Can this problem be solved, or should I use another way of initialising the sieve? (for instance vector<bool>, or memset).

    What's the fastest way in general to implement a sieve of eratosthenes? (not algorithm wise, but which container and operations to use, etc.)

    Thanks in advance!

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Because the template argument for bitset must be a constant. If you want a dynamic bitset, look into boost::dynamic_bitset.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User
    Join Date
    Feb 2012
    Posts
    10
    But then const int n should work?

    In general, is the bitset container for sieve (true or false) purposes the fastest way of implementing? (memory wise it should be best, I assume, but how about speed?)

  4. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by Kappie
    But then const int n should work?
    If n were say, a file scope variable rather than a parameter such that its value is known at compile time.

    Quote Originally Posted by Kappie
    In general, is the bitset container for sieve (true or false) purposes the fastest way of implementing? (memory wise it should be best, I assume, but how about speed?)
    Measure and find out.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  5. #5
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    Clearly representing the numbers to be tested by bits will be best for memory, but it may not be best for speed due to all of the bitwise manipulation going on in the bitset implementation.

    However, due to caching, it may in fact be faster. As laserlight says, you'd have to measure both approaches (bitset vs. vector of ints). Assuming 32-bit ints, you can easily represent 32 times as many numbers with a bitset in the same amount of space.

    Note that in either implementation you can easily only represent the odd numbers (and with a little more complexity, represent only numbers not divisible by 2 or 3), so you can easily halve the memory requirements.
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Bitset
    By Kristyy_mariee in forum C++ Programming
    Replies: 2
    Last Post: 03-03-2012, 09:00 AM
  2. Bitset help
    By Kristyy_mariee in forum C++ Programming
    Replies: 1
    Last Post: 03-02-2012, 10:33 PM
  3. bitset + memcpy
    By KBriggs in forum C++ Programming
    Replies: 7
    Last Post: 08-14-2009, 01:04 PM
  4. Bitset questions
    By serge in forum C++ Programming
    Replies: 17
    Last Post: 05-07-2008, 02:00 PM
  5. errors with bitset
    By Marksman in forum C++ Programming
    Replies: 11
    Last Post: 07-12-2006, 12:15 PM