[Tapas Bose]

So there is no way to allocate memory for 10000000000?

[NickDMax]

First off - DO NOT USE GLOBAL VARIABLES!!! ESPECIALLY REALLY REALLY REALLY BIG ONES. You are just looking for trouble!

Secondly, you have a problem because 10000000000 is too large to fit into a size_t -- so you can't use vector<bool> either (because you can not index past 2^32).

That is to say that the vector's operator[] function will look something like this:

bool std::vector<bool> operator[](size_t index); and since 10000000000 > numeric_limits<size_t>::max()

So you will HAVE to do something custom. You will have to invent your own data structure to do this.

[Tapas Bose]

Okay I understand now. array of vector. I will try to do this. If I face any problem I will contact you sir.

[NickDMax]

Tapas Bose, on 21 May 2010 - 11:37 AM, said:

So there is no way to allocate memory for 10000000000?

well sure you can do that... you just have to do thinks custom.

You only need 10000000000/8 bytes right that is only 1250000000 bytes which new can do for you...

#include <vector>
#include <iostream>
#include <limits>

using namespace std;

typedef char BigBitArray[1250000000];

int main() {
    //cout << numeric_limits<size_t>::max() << endl;
    char *allocated_memory = new char[1250000000];
    if (allocated_memory) {
        BigBitArray & bits = *((BigBitArray*)allocated_memory);
        cout << "We allocated the memory!!!" << endl;
        delete allocated_memory;
    } else {
        cout << "oopse memory not available! :(/> " << endl;
    }
    
    return 0;
}

but it is up to you to write the routines to get access to the individual bits.

[NickDMax]

I have not tried it at the full 10000000000 yet... but it seems to work for now...

#include <vector>
#include <iostream>
#include <iomanip>
#include <limits>

using namespace std;

class BigBitSet {
    unsigned char* bits;
    public:
    typedef unsigned long long int size_t;
    explicit BigBitSet(BigBitSet::size_t size) : bits(NULL) {
        BigBitSet::size_t  arraySize = size / 8;
        if (arraySize > numeric_limits<std::size_t>::max()) {
            cout <<"Array size is TOO big to allocate." << endl;
        }
        bits = new unsigned char[size_t(arraySize)];
        if (!bits) {
            cout <<"Array did not allocate." << endl;
        }
    }
    ~BigBitSet() {
        if (bits) { delete bits; }
        bits = NULL;
    }
    
    BigBitSet& set(BigBitSet::size_t index) {
        std::size_t byte = index / 8;
        std::size_t bit = index % 8;
        bits[byte] |= 1 << bit;
        return *this;
    }

    BigBitSet& unset(BigBitSet::size_t index) {
        std::size_t byte = index / 8;
        std::size_t bit = index % 8;
        bits[byte] &= ~(unsigned char(1) << bit);
        return *this;
    }

    bool get(BigBitSet::size_t index) const {
        std::size_t byte = index / 8;
        std::size_t bit = index % 8;
        return bits[byte] & unsigned char(1) << bit;
    }

};

//const unsigned long long int Limit = 10000000000ULL;
//const unsigned long long int SqrtLimit = 100000ULL;
const unsigned long long int Limit = 10000ULL;
const unsigned long long int SqrtLimit = 100ULL;


int main() {
    //cout << numeric_limits<size_t>::max() << endl;
    BigBitSet isPrime(Limit);
    cout << "Memory Allocated: Begin initialization" << endl;
    isPrime.unset(0);isPrime.unset(1);isPrime.set(2);
    //unset all even values
    for(BigBitSet::size_t i = 4; i < Limit; i+=2) {
        isPrime.unset(i);
       // cout << isPrime.get(i);
    }
    cout << "Even initialized" << endl;
    //set all odd values
    for(BigBitSet::size_t i = 3; i < Limit; i+=2) {
        isPrime.set(i);
        //cout << isPrime.get(i);
    }
    cout << "Odd initialized" << endl;
    cout << "Done initilizing." << endl;

    for(BigBitSet::size_t i = 3; i < SqrtLimit; i+=2) {
        if (i%10 == 9) { cout << "."; }
        if (isPrime.get(i)) { 
            //cout << i <<"(" << isPrime.get(i) << ") ";
            for(BigBitSet::size_t j = i*i; j < Limit; j+=i) {
                //cout << j << " ";
                isPrime.unset(j);
            }
        }
    }
    cout << "Done Calculation." << endl;
    BigBitSet::size_t count = 0;
    for(BigBitSet::size_t i = 0; i < Limit; ++i) {
        //cout << isPrime.get(i);
        if (isPrime.get(i)) { 
            cout << setw(8) << i; 
            if (count++ % 10 == 9) {
                cout << endl;
            }
        }
    }

    return 0;
}

[NickDMax]

actually that does not seem to work at 10000000000ULL, it will work at 100000000 but something is going wrong with the larger number...

[baavgai]

Since the source is out, I also gave this a go.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define BOOL int
#define TRUE 1
#define FALSE 0
#define BYTE unsigned char
#define BITS_IN_BYTE 8

typedef unsigned long long int SizeType;

typedef struct {
	BYTE *storage;
	SizeType size;
	SizeType byteCount;
} Sieve;



int getBit(Sieve *sieve, SizeType pos) {
	int offset = pos % BITS_IN_BYTE;
	pos /= BITS_IN_BYTE;
	return (sieve->storage[pos] >> offset) & 1;
}

void setBit(Sieve *sieve, SizeType pos, BOOL value) {
	int offset = pos % BITS_IN_BYTE;
	int mask = (1 << offset);
	pos /= BITS_IN_BYTE;
	if (value) {
		sieve->storage[pos] = sieve->storage[pos] | mask;
	} else {
		sieve->storage[pos] &= (0xFF ^ mask);
	}
}

BOOL initSieve(Sieve *sieve, SizeType bitCount, BOOL value) {
	sieve->size = bitCount;
	sieve->byteCount = bitCount/BITS_IN_BYTE + 1;
	sieve->storage = malloc(sieve->byteCount);
	if (sieve->storage!=NULL) {
		memset (sieve->storage, (value) ? 0xFF : 0, sieve->byteCount);
	}
	return sieve->storage!=NULL;
}

void freeSieve(Sieve *sieve) { 
	sieve->byteCount = 0;
	sieve->size = 0;
	free(sieve->storage);
	sieve->storage = NULL;
}


void markOff(Sieve *s, int i) {
	SizeType j = i*i;
	for (; j <s->size; j += i) { 
		setBit(s, j, FALSE);
	} 
}

void primeGen(Sieve *s) {
	SizeType size=s->size, i;
	
	markOff(s, 2);
	for (i=3; i*i < size; i+=2) { 
		if (getBit(s, i))  { markOff(s, i); }
	} 
}


SizeType countPrimes(Sieve *s) {
	SizeType i, count = 1;
	for(i=3; i<s->size; i += 2) { 
		if (getBit(s, i)) { count++; }
	}
	return count;
}


unsigned GetTickCount() {
	struct timeval tv;

	if (gettimeofday(&tv, NULL) != 0) {  return 0; }
	return (tv.tv_sec * 1000) + (tv.tv_usec / 1000);
}


void testSieve(SizeType limit) {
	Sieve sieve;
	if (!initSieve(&sieve, limit, TRUE)) {
		printf("Too damn big.\n");
		
	} else {
		unsigned endTime, startTime = GetTickCount();
		
		primeGen(&sieve);
		endTime = GetTickCount();
		printf("Size:  %lu\n", sieve.size);
		printf("Number of Prime:  %lu\n", countPrimes(&sieve));
		printf("Execution time:  %lu ms.\n", (endTime - startTime));
		freeSieve(&sieve);
	}
}


int main () {
	testSieve(10000000000ULL);
	return 0;
}

With small numbers it seems to be doing a fair job:

Size:  1000000
Number of Prime:  78498
Execution time:  76 ms.

I'm still waiting on the big damn number...

[baavgai]

Update.

To simply mark off all the even numbers where size=10000000000 took my not insignificant workstation 71491 ms. Clearly, this size set requires special consideration.

[NickDMax]

Turns out the program DOES work with the big value... I just forgot to add a flush() to my little progress bar so I could see that it was doing something.

I was able to calculate 455052511 Primes in 460.938 seconds so it takes a little while but its not too bad (I remember waiting hours for fractals to generate!).


here is my updated code, you need to update the constants to use the correct size:

#include <vector>
#include <iostream>
#include <fstream>
#include <iomanip>
#include <limits>
#include <ctime>

using namespace std;

class BigBitSet {
    unsigned char* bits;
    public:
    typedef unsigned long long int size_t;
    explicit BigBitSet(BigBitSet::size_t size) : bits(NULL) {
        BigBitSet::size_t  arraySize = size / 8;
        if (arraySize > numeric_limits<std::size_t>::max()) {
            cout <<"Array size is TOO big to allocate." << endl;
        }
        bits = new unsigned char[size_t(arraySize)];
        if (!bits) {
            cout <<"Array did not allocate." << endl;
        }
    }
    ~BigBitSet() {
        if (bits) { delete bits; }
        bits = NULL;
    }
    
    BigBitSet& set(BigBitSet::size_t index) {
        std::size_t byte = index / 8;
        std::size_t bit = index % 8;
        bits[byte] |= 1 << bit;
        return *this;
    }

    BigBitSet& unset(BigBitSet::size_t index) {
        std::size_t byte = index / 8;
        std::size_t bit = index % 8;
        bits[byte] &= ~((unsigned char)1 << bit);
        return *this;
    }

    bool get(BigBitSet::size_t index) const {
        std::size_t byte = index / 8;
        std::size_t bit = index % 8;
        return bits[byte] & (unsigned char)1 << bit;
    }

};

//const unsigned long long int Limit = 10000000000ULL;
//const unsigned long long int SqrtLimit = 100000ULL;
const unsigned long long int Limit = 1000000ULL;
const unsigned long long int SqrtLimit = 1000ULL;

const unsigned long long int ReportDepth = SqrtLimit / 100;
const unsigned long long int ReportAt = ReportDepth - 1;

const int ColSize = 12;


int main() {
    //cout << numeric_limits<size_t>::max() << endl;
    BigBitSet isPrime(Limit);
    cout << "Memory Allocated: Begin initialization" << endl;
    isPrime.unset(0);isPrime.unset(1);isPrime.set(2);
    //unset all even values
    for(BigBitSet::size_t i = 4; i < Limit; i+=2) {
        isPrime.unset(i);
       // cout << isPrime.get(i);
    }
    cout << "Even initialized" << endl;
    //set all odd values
    for(BigBitSet::size_t i = 3; i < Limit; i+=2) {
        isPrime.set(i);
        //cout << isPrime.get(i);
    }
    cout << "Odd initialized" << endl;
    cout << "Done initilizing." << endl;
    
    clock_t beginTimer = clock();
    for(BigBitSet::size_t i = 3; i < SqrtLimit; i+=2) {
        if (i%ReportDepth == ReportAt) { (cout << ".").flush(); }
        if (isPrime.get(i)) { 
            for(BigBitSet::size_t j = i*i; j < Limit; j+=i) {
                isPrime.unset(j);
            }
        }
    }
    clock_t endTimer = clock();
    
    cout << "Done Calculation." << endl;
    BigBitSet::size_t count = 0;
    ofstream output;
    output.open("calculated_primes.txt");
    if (output) {
        cout << "Writing Primes to file: calculated_primes.txt" << endl;
        
        for(BigBitSet::size_t i = 0; i < Limit; ++i) {
            //cout << isPrime.get(i);
            if (isPrime.get(i)) { 
                output << setw(ColSize) << i; 
                if (count++ % 10 == 9) {
                    output << endl;
                }
            }
        }
        output.close();
        cout << "Calculated " << count << " primes in " << ((double)endTimer - beginTimer)/CLOCKS_PER_SEC << " Seconds." << endl;
    }
    
    

    return 0;
}

[Tapas Bose]

Thank you very much sir, its really working. Sir I have a request. Can you please explain me the set(), unset(), get() function? Actually I am poor in bit-shift. There is several problems. I can not understand the whole concept. No doubt it is WONDERFUL. What is the reason behind the explicit constructor? Can you please comment in your code?

This post has been edited by Tapas Bose: 22 May 2010 - 07:12 AM

[Tapas Bose]

Atlast... As sir NickDMax said, to use some array of vectors, I did it that way. But it is taking too much time. Here is my code :

#include <iostream>
#include <vector>
#include <cmath>
#include <ctime>

using namespace std;

//const unsigned long long int tenbillion = 1000000ULL;

class SieveOfEratosthenes {
	private :
	unsigned long long int Limit;
	vector<bool> *isPrime;
	unsigned long long int row;
	unsigned long long int col;
	
	
	public :
	SieveOfEratosthenes(unsigned long long int lim) : Limit(lim) {
		isPrime = new vector<bool>[10];		
		row = 10ULL;
		col = Limit / 10ULL;
	}
	
	void set() {
		unsigned long long int jLim = Limit / 10;
		for (int i = 0; i < 10; i++) {
			cout << "  Initializing " << (i + 1) << " th row ";
			for (unsigned long long int j = 0; j < jLim; j++) {
				isPrime[i].push_back(true);
				
				/*if (j % tenbillion == 0) {
					(cout << ".").flush();
				}*/
			}
			
			cout << endl;
		}
	}
	
	void primegen() {
		unsigned long long int sqrtLim = (unsigned long long int)sqrt(Limit);
		bool flag = true;
		
		cout << "  Prime computation started ";
		for (unsigned long long int i = 0; i < row && flag; i++) {
			for (unsigned long long int j = 0; j < col; j++) {
				if (i == 0 && (j == 0 || j == 1)) {
					isPrime[i][j] = false;
					continue;
				}
				
				if (isPrime[i][j]) {
					unsigned long long int num = 10 * i + j;
					
					if (num > sqrtLim) {
						flag = false;
						break;
					}
					
					for (unsigned long long int k = num * num; k < Limit; k += num) {
						isPrime[k / col][k % col] = false;
						
						/*if ((k % tenbillion == 1) || (k % tenbillion == 3) || 
							(k % tenbillion == 7) || (k % tenbillion == 9)) { 
							(cout << ".").flush(); 
						}*/
					}
				}
			}
			
			//(cout << "...").flush();
		}
		
		cout << endl;
		cout << "  Prime computation end." << endl;
	}

	void primecount() {
		cout << "  Prime count started ";
		unsigned long long int count = 0;
		
		for (unsigned long long int i = 0; i < row; i++) {
			for (unsigned long long int j = 0; j < col; j++) {
				if (isPrime[i][j]) {
					//cout << (10 * i + j) << " "; 
					count++;
					
					/*if ((j % tenbillion == 1) || (j % tenbillion == 3) || 
					      (j % tenbillion == 7) || (j % tenbillion == 9)) { 
						(cout << ".").flush(); 
					}*/
				}	
			}
			
			//(cout << "...").flush();
		}
		
		cout << endl;
		cout << "  Prime count end." << endl;		
		cout << "  Total number of prime upto " << Limit << " : " << count << endl;
	}
};

int main() {
//	clock_t start = clock();
	
	SieveOfEratosthenes Prime(10000000000ULL);
	Prime.set();
	Prime.primegen();
	Prime.primecount();
	
//	clock_t end = clock();
	
//	cout << "  Run time : " << (end - start)/ (double)CLOCKS_PER_SEC << endl;
	
	return 0;
}

I have still doubt in the previously shown code by sir NickDMax. Is there any way to optimize my code? Thank you.

This post has been edited by Tapas Bose: 22 May 2010 - 09:01 AM

[NickDMax]

sure thing! I should be more in the habit of commenting anyway.

Quote

What is the reason behind the explicit constructor?

This is actually an important thing that you should know. The C++ compiler is very helpful and sometimes it is SO helpful that it does automatic conversions for you. Lets take a little example:

#include <iostream>

using namespace std;

struct Foo {
    int value;
    //we have a non expicit constructor
    Foo(int v) : value(v) { cout << "Constructor v = " << v << endl; }
};


int main() {
    Foo foo(6); // nice constructor
    foo = 8; //opse explicit conversion of int into Foo
    
    cout << "foo.value = " << foo.value  << endl;
    return 0;
}

The compiler used the constructor Foo(int) to convert the integer 8 into a Foo object which it assigned to foo -- Sometimes this is a really NEAT feature that saves us a lot of awkward syntax, sometimes however it is NOT very convent and can result in strange bugs. Imagine if you will writing something like this:

vector<int> myvector;
//use the vector a bunch and built up a large set of data
myvector = 8; //oopse I meant myvector.push_back(8) but I wasn't thinking! 
//POW the constructor vector<int>(size_t capacity) was called and 8 was converted to vector with a capacity of 8
// all data in myvector is gone
cout << myvector[100]; //OOPSE error there are only 8 elements now!!!

this of course does not happen because the designers of STL made the vector's constructors explicit, so the compiler cannot convert from an int into a vector using a constructor.

The problem is that such errors will compile just fine but will give you run time errors - even though it really should be caught at compile time.

So whenever you make a class with a constructor that takes only 1 argument you have to ask yourself: would it be an error for the compiler to do a conversion here?

For more information on explicit keyword see here and here.

as for some commented code.. I have to leave right now. Maybe someone can show you what the I did using bitsets (when you using a bitset with cout it will display the binary).

I will post commented code later today.

[Tapas Bose]

Thank you sir. I will wait for you. If I face any doubt I will contact you. I want to know the logic of your awesome creation. Sir as you instructed me to use something like array of vector, I did it. Is it okay? Thank you very sir.

[NickDMax]

here is a short program to demonstrate the shift operators:

#include <iostream>
#include <bitset>

using namespace std;

int main() {
    unsigned char ch = 1;
    cout << "Shift Operators:" << endl;
    cout << " ch       = " << bitset<8>(ch) << endl;
    cout << "(ch << 0) = " << bitset<8>(ch << 0) << endl; //00000001
    cout << "(ch << 1) = " << bitset<8>(ch << 1) << endl; //00000010
    cout << "(ch << 2) = " << bitset<8>(ch << 2) << endl; //00000100
    cout << "(ch << 3) = " << bitset<8>(ch << 3) << endl; //00001000
    cout << "(ch << 4) = " << bitset<8>(ch << 4) << endl; //00010000
    cout << "(ch << 5) = " << bitset<8>(ch << 5) << endl; //00100000
    cout << "(ch << 6) = " << bitset<8>(ch << 6) << endl; //01000000
    cout << "(ch << 7) = " << bitset<8>(ch << 7) << endl; //10000000
    cout << "(ch << 8) = " << bitset<8>(ch << 8) << endl; //00000000 -- bit shifted right out of the data!
    cout <<"\n--------------------------------\n" << endl;
    ch = 128;
    cout << " ch       = " << bitset<8>(ch) << endl;
    cout << "(ch >> 0) = " << bitset<8>(ch >> 0) << endl; //10000000
    cout << "(ch >> 1) = " << bitset<8>(ch >> 1) << endl; //01000000
    cout << "(ch >> 2) = " << bitset<8>(ch >> 2) << endl; //00100000
    cout << "(ch >> 3) = " << bitset<8>(ch >> 3) << endl; //00010000
    cout << "(ch >> 4) = " << bitset<8>(ch >> 4) << endl; //00001000
    cout << "(ch >> 5) = " << bitset<8>(ch >> 5) << endl; //00000100
    cout << "(ch >> 6) = " << bitset<8>(ch >> 6) << endl; //00000010
    cout << "(ch >> 7) = " << bitset<8>(ch >> 7) << endl; //00000001
    cout << "(ch >> 8) = " << bitset<8>(ch >> 8) << endl; //00000000 -- bit shifted right out of the data!
    //note that this last one actually generates a warning from the compiler! because it shifts too far.
    
    cout <<"\n--------------------------------\n" << endl;
    
    cout << "Note that the right shift operator (>>) behaves differently\n"
         << "when given signed or unsigned values!" << endl;;
    signed sch = -128;
    cout << " sch       = " << bitset<8>(ch) << endl;
    cout << "(sch >> 0) = " << bitset<8>(sch >> 0) << endl; //10000000
    cout << "(sch >> 1) = " << bitset<8>(sch >> 1) << endl; //11000000
    cout << "(sch >> 2) = " << bitset<8>(sch >> 2) << endl; //11100000
    cout << "(sch >> 3) = " << bitset<8>(sch >> 3) << endl; //11110000
    cout << "(sch >> 4) = " << bitset<8>(sch >> 4) << endl; //11111000
    cout << "(sch >> 5) = " << bitset<8>(sch >> 5) << endl; //11111100
    cout << "(sch >> 6) = " << bitset<8>(sch >> 6) << endl; //11111110
    cout << "(sch >> 7) = " << bitset<8>(sch >> 7) << endl; //11111111
    cout << "(sch >> 8) = " << bitset<8>(sch >> 8) << endl; //11111111 

    return 0;
}

So in my program I used the shift operator to place a 1 in a specific point in the byte.

say I have the index of 18. The byte would be ( 19 / 8 = 2 ) and the bit would be (19 % 8 = 3)

so (1 << 3) is 00001000

so lets say our second byte is 10000001. So if we do 10000001 | 00001000 we will get a 1 everywhere a 1 occurs in either number:
10000001 | 00001000 = 10001001 So we set the bit we needed,

note that the bits are numbered 0 - 7 as :76543210 in in the above result bit 7, 3, and 0 are set.

The unset need to place a 0 in the proper place... this I did with a little more work:

~(1 << 3) is 11110111 -- that is every bit BUT 3 is set. This is because the NOT operator flips each bit, if it was 0 it is now 1 and if it was 1 it is 0. So I use shift to put the bit where I want it, then NOT the value.

so the AND operator can now be used.

Say our byte was 01111110.

01111110 & 11110111 = 01110110 -- only when a 1 exists in both operands will the result have a bit set. So bits 7 and 0 are unset in the original byte and bit 3 unset in our byte, so the result has bits 7, 3, and 0 unset.

#include <iostream>
#include <bitset>

using namespace std;

int main() {
    unsigned char ch1 = 129;
    unsigned char ch2 = 1 << 3;
    
    cout << bitset<8>(ch1) << " | " << bitset<8>(ch2) << " = " << bitset<8>(ch1 | ch2) << endl;

    ch1 = ~ch1;
    ch2 = ~ch2;
    cout << bitset<8>(ch1) << " & " << bitset<8>(ch2) << " = " << bitset<8>(ch1 & ch2) << endl;
    
    return 0;
}

You might pick up on a little symmetry in my example! ~( a | b ) = ~a & ~b -- though it really does not have too much to do with how my set() and unset() functions worked.


Anyway here is a commented version of my source.

#include <vector>
#include <iostream>
#include <iomanip>
#include <limits>
#include <ctime>

using namespace std;

/** 
 * A class to represent a large field of bits.
 */
class BigBitSet {
    unsigned char* bits; //a pointer to our data.
    public:
    typedef unsigned long long int size_t; // a typedef to indicate what is needed to index this container
    
    //explicit is used 
    explicit BigBitSet(BigBitSet::size_t size) : bits(NULL) {
        BigBitSet::size_t  arraySize = size / 8;
        if (arraySize > numeric_limits<std::size_t>::max()) {
            cout <<"Array size is TOO big to allocate." << endl;
        }
        bits = new unsigned char[size_t(arraySize)];
        if (!bits) {
            cout <<"Array did not allocate." << endl;
        }
    }
    ~BigBitSet() {
        if (bits) { delete bits; }
        bits = NULL;
    }
    
    //copy constructor/assignment operator, if we need a deconstructor, we also NEED to define a copy constructor and
    // and an assignment operator. -- since I didn't keep track of the array size I will just make these private.
    private:
    BigBitSet(const BigBitSet& other) { } // no copy (because I didn't keep track of the size or the array)
    BigBitSet& operator=(const BigBitSet& other) { } // no assign (again, because I didn't keep track of the array size).
    public:
    
    
    /** Set a bit at a particular index in our array of bits */
    BigBitSet& set(BigBitSet::size_t index) {
        std::size_t byte = index / 8;  // determine which byte the index falls into
        std::size_t bit = index % 8; // determine which bit 0-7 to set
        bits[byte] |= 1 << bit; // use the shift operator to place 1 in correct postion and then or
        return *this; //Rather than just a void function I returned the Set so if you wanted to you can do isPrime.set(1).set(2).unset(3)
    }

    /** unset a bit at a particular index in our array of bits */
    BigBitSet& unset(BigBitSet::size_t index) {
        std::size_t byte = index / 8; // get the byte in our array the index falls into
        std::size_t bit = index % 8; // get the bit 0-7
        bits[byte] &= ~(unsigned char(1) << bit); // Shift our but to the right place, then do a not to mask out all but that bit to 1 & will only clear that bit
        return *this; // return the set you that you can go: isPrime().unset(0).unset(1035) etc.
    }

    /** Return a particular bit form our set */
    bool get(BigBitSet::size_t index) const {
        std::size_t byte = index / 8;
        std::size_t bit = index % 8;
        return bits[byte] & (unsigned char(1) << bit); // return a 1 only if the bit in bits[byte] is 1
    }
};

//const unsigned long long int Limit = 10000000000ULL;
//const unsigned long long int SqrtLimit = 100000ULL;

const unsigned long long int Limit = 10000000000ULL;
const unsigned long long int SqrtLimit = 100000ULL;

const unsigned int ReportSize = SqrtLimit / 100;
const unsigned int ReportAt = ReportSize - 1;

int main() {
    //create a BigBitSet
    BigBitSet isPrime(Limit);
    cout << "Memory Allocated: Begin initialization" << endl;
    isPrime.unset(0).unset(1).set(2); //basic initialization
    //unset all even values
    for(BigBitSet::size_t i = 4; i < Limit; i+=2) {
        isPrime.unset(i);
    }
    cout << "Even initialized" << endl;
    //set all odd values
    for(BigBitSet::size_t i = 3; i < Limit; i+=2) {
        isPrime.set(i);
    }
    cout << "Odd initialized" << endl;
    cout << "Done initilizing." << endl;

    // make a note of the starting time...
    clock_t beginTimer = clock();
    for(BigBitSet::size_t i = 3; i < SqrtLimit; i+=2) {
        // Print a dot every now and then to let us know the program is running and not locked up...
        // it should print 100 dot (they get faster and faster as the program runns)
        //Note the first dot make take a couple of minutes to show up...
        if (i % ReportSize == ReportAt) { (cout << ".").flush();  }

        // IF the current number is prime (i.e. has not been sieved out yet) we need to mark out all
        //    multiples...
        if (isPrime.get(i)) { 
            // we start at i i * because all multiple of primes LESS than i have already been marked off, so 
            //  for example i * 2 is already 0, if i > 3 then i * 3 is gone, etc.
            for(BigBitSet::size_t j = i*i; j < Limit; j+=i) {
                isPrime.unset(j);
            }
        }
    }
    //make a note of our ending time...
    clock_t endTimer = clock();
    cout << "Done Calculation." << endl;
    // begin to count up all the primes we found. if the number was not unset() then it is a prime
    BigBitSet::size_t count = 0;
    for(BigBitSet::size_t i = 0; i < Limit; ++i) {
        if (isPrime.get(i)) { 
            // This was used to display the primes... 
            //cout << setw(8) << i; 
            // a way to break something into columns of 10... when we reach the last number (9) we print a newline
            //if (count++ % 10 == 9) {
                //cout << endl;
            //}
            count++;
        }
    }
    cout << "calculated: " << count << " primes in " << double(endTimer - beginTimer)/CLOCKS_PER_SEC << " seconds";

    return 0;
}

I will take a look at yours and see what I can see

[NickDMax]

initial comments on you code so far... #1 don't use push_back() to create a vector of known size! push_back() is for DYNAMIC structures that grow unexpectedly. If you did not have an array you could use:
explicit vector ( size_type n, const T& value= T(), const Allocator& = Allocator() );
(note that it is "explicit" because there are default values for the other two arguments, so really there is only 1 needed argument 'n').



BUT since you have an array you can't call a constructor for each element (as far as I know anyway). So you will need to use the resize() function


So you can use:

        void set() {
                //unsigned long long int jLim = Limit / 10; // you already defined this value as col
                for (int i = 0; i < 10; i++) {
                        cout << "  Initializing " << (i + 1) << " th row ";
                        //for (unsigned long long int j = 0; j < jLim; j++) {
                        //        //isPrime[i].push_back(true);
                        //        
                        //        /*if (j % tenbillion == 0) {
                        //                (cout << ".").flush();
                        //        }*/
                        //}
                        //
                        isPrime[i].resize(col, true);
                        cout << endl;
                }
        }

NExt -- you know you don't have to do EVERYTHING in a loop -- actually when you are trying to optimize code, if you can precalculate something it is probably better than adding logic to the loop to calculate it. So I would replace this mess:

                                if (i == 0 && (j == 0 || j == 1)) {
                                        isPrime[i][j] = false;
                                        continue;
                                }

by putting this at the top of the procedure:

                isPrime[0][0] = false;
                isPrime[0][0] = false;

take those clock cycles right out of that inner loop!

You could probably benefit from a different point of view on the indexing of your structure.

Say I have 1000 values broken up into 10 rows, each row has 1000/10 = 100 cols... So bit 847 is located at isPrime[8][47].

Thinking about this this way lets us concentrate MORE on the logic of the sieve and LESS on the logic of sorting out what element we need to access. I suggest you use a little inline member function:

void setbit(unsigned long long int index, bool value) {
    isPrime[i/col][i % col] = value;
}

now you can make you loops a little more traditional so i goes from 0 to sqrt(limit) and j from i*i to limit.