Want to win a PS4? Go Premium and enter to win our High-Tech Treats giveaway. Enter to Win

x
Solved

# follow up question - lookup table

Posted on 2006-10-23
Medium Priority
221 Views
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
Question by:BrianGEFF719
[X]
###### Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

• Help others & share knowledge
• Earn cash & points
• 4
• 3
• 3
• +1

LVL 45

Expert Comment

ID: 17786922
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

LVL 39

Expert Comment

ID: 17787425
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

LVL 22

Accepted Solution

grg99 earned 1200 total points
ID: 17787593
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

LVL 19

Author Comment

ID: 17793664
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

LVL 45

Assisted Solution

sunnycoder earned 400 total points
ID: 17793673
How about access time? I thought you wanted constant time search.
0

LVL 39

Assisted Solution

itsmeandnobodyelse earned 400 total points
ID: 17797610

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

LVL 19

Author Comment

ID: 17798088
>>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

LVL 19

Author Comment

ID: 17798096
>>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

LVL 19

Author Comment

ID: 17798134
>>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

LVL 45

Expert Comment

ID: 17800854
>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

LVL 39

Expert Comment

ID: 17828364
>>>> 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

## Featured Post

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

When writing generic code, using template meta-programming techniques, it is sometimes useful to know if a type is convertible to another type. A good example of when this might be is if you are writing diagnostic instrumentation for code to generatâ€¦
Looking for a way to avoid searching through large data sets for data that doesn't exist? A Bloom Filter might be what you need. This data structure is a probabilistic filter that allows you to avoid unnecessary searches when you know the data definâ€¦
The viewer will learn additional member functions of the vector class. Specifically, the capacity and swap member functions will be introduced.
The viewer will be introduced to the member functions push_back and pop_back of the vector class. The video will teach the difference between the two as well as how to use each one along with its functionality.
###### Suggested Courses
Course of the Month8 days, 4 hours left to enroll