• Status: Solved
• Priority: Medium
• Security: Public
• Views: 225

# follow up question - lookup table

http://www.experts-exchange.com/Programming/Programming_Languages/C/Q_22033872.html

If you dont read that this question will not make sense.

What I was thinking now is that since even numbers are never prime anyway, why not leave them out and allow me to fit 64 numbers in a 32bit long..

For example, i will do 8bit for this example starting at 1:

1111 0110 ->  Where each bit corresponds to 1, 3, 5, 7, 9, 11, 13, 15.

Where if I was including the even numbers I would have:

1010 1010 0010 1000, which is 16bits

So by this method I should be able to cut the required memory in half...I'm basically trying to have a list of all prime number between 1 - 10,000,000 with fastest searchtime and smallest amount of memory.

Any thoughts?
0
BrianGEFF719
• 4
• 3
• 3
• +1
3 Solutions

Commented:
Hi BrianGEFF719,

Makes good sense ... good thinking. Even computation would be simple .. if num%2 == 0 skip it else find if it is prime and set num/2th bit

Cheers!
sunnycoder
0

Commented:
Implementing your idea using bitsets it is

int main ()
{
long theNumber,startTick,endTick;
const size_t maxPrime = 1000000;
bool isItPrime;
bitset<maxPrime>>1> primeBits;

cout << "Building bitset...";
startTick = GetTickCount();

long l;
primeBits.reset();

for (l = 0 ; l < maxPrime; ++l )
{
if (isPrime(++l))
{
primeBits.set(l>>1, true);
}
}
primeBits.set(1, true);   // for 2

endTick = GetTickCount();
cout << "Done building array, Time: " << (endTick - startTick) << "ms" << endl << endl;

do
{
cout << endl << "Please enter a number to check between 1 - " << maxPrime << " (0 exits): " << endl;
cin >> theNumber;
if (theNumber > 1 && theNumber < maxPrime)
{
isItPrime = (theNumber%2) != 0 && primeBits[theNumber>>1];

cout << theNumber << ((isItPrime) ? (" is prime") : (" is not prime")) << endl;
}
} while (theNumber > 0 && theNumber < maxPrime);

cout << endl << endl;
system("PAUSE");

return 0;
}

Regards, Alex
0

Commented:
A somewhat more compact way:  just store the distances between the primes-- this can be done in one byte for upwards of 100 million.  ANd once the primes average more than 8 apart (around  3000) this shceme is more compact.

0

Author Commented:
grg99: I was thinking that, since the distance between prime is x/ln x, or so, this would save quite a bit of memory. However, I would have to rebuild the table everytime starting with some known prime.

Brian
0

Commented:
How about access time? I thought you wanted constant time search.
0

Commented:

Worst case for overall access time is when using a bitmap and checking IsPrime for any (odd) number. After the bitmap exists you have const time for each check ... but as any single IsPrime check is less than 1 ms (with GetTickCount you only can measure times > 15ms) I don't know why you actually need const time search later while you don't mind the initial overhead of determining all primes up to some millions.

You could optimize the initial loop by not calling IsPrime for any potential prime but by clearing the bits for all non-primes straight-forward:

long theNumber,startTick,endTick;
const size_t maxPrime = 1000000;
bool isItPrime;
bitset<maxPrime>>1> primeBits;

startTick = GetTickCount();

long count = 0;
primeBits.set();       // initially set all prime
primeBits.reset(0);   // 1 is not prime

for (l = 3 ; l < maxPrime/3; l += 2 )
{
if (primeBits[l>>1])
{
for (int n = l + l + l; n < maxPrime; n += l + l)
primeBits.reset(n>>1);

count++;
}
}

endTick = GetTickCount();
cout << "Done building array, Time: " << (endTick - startTick) << "ms" << endl << endl;

The loop is about 4 times faster (170 to 650 ms) on my system than when calling isPrime for each odd number.

>>>> since the distance between prime is x/ln x, or so, this would save quite a bit of memory.

Indeed, but an array of about 80,000 distances if maxPrime is 1,000,000 needs 40,000 additions on average to find out whether a given number is a prime. I don't think there is any advantage on speed.

You could put all primes to an integer array. Then, you would need 5 times the storage as for a bitset and have a binary speed time what seems to be a bad change as well.

Regards, Alex
0

Author Commented:
>>How about access time? I thought you wanted constant time search.

You're right sunnycoder, i'm trying to do this all with constant search time.
0

Author Commented:
>>I don't know why you actually need const time search later while you don't mind the initial overhead of determining all primes up to some millions.

Because I'm going to save the primes to a file in this format, around 500 million of them, and then later on it becomes rather fast to initlize the array from a file.

Brian

0

Author Commented:
>>Indeed, but an array of about 80,000 distances if maxPrime is 1,000,000 needs 40,000 additions on average to find out whether a given number is a prime. I >>don't think there is any advantage on speed.

Yah i've given up on this idea, the fact is i need constant search time, which requires that I use an array, in order to minimize memory usage, I will need to use a setup that i've mentioned above. I dont think I want to use any classes in this alex, I'd rather use normal datatypes and bitshifts to accomplish this.

-Brian
0

Commented:
>in order to minimize memory usage,

There is always a trade-off between memory usage and search time ... Constant time search is the ultimate prize you are assured of by throwing in lots of memory as in the current case ...
To reduce memory consumption, you can switch to hash tables ... You get good search times but not constant time and waste lesser memory ...
Or as Greg suggested, store distances ... makes it easy to build an array in which you can search using binary search ... ln(n) search time but you only consume as much memory as you really need.
0

Commented:
>>>> I dont think I want to use any classes in this alex, I'd rather use
>>>> normal datatypes and bitshifts to accomplish this

std::bitset is much faster than when using 'normal' bit operations as in some code above. I was surprised myself when I firstly tried to write competitive code but failed. I had to steal code from their most advanced algorithms to draw level with them. In C++ using classes and especially STL classes is the *normal* way - STL is C++ stnadard since 1998 - and you shouldn't go back to pure C if you can avoid it.

Regards, Alex
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.