Solved

follow up question - lookup table

Posted on 2006-10-23
11
213 Views
Last Modified: 2010-04-01
Please see:
 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
Comment
Question by:BrianGEFF719
  • 4
  • 3
  • 3
  • +1
11 Comments
 
LVL 45

Expert Comment

by:sunnycoder
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

by:itsmeandnobodyelse
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

by:
grg99 earned 300 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

by:BrianGEFF719
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

by:sunnycoder
sunnycoder earned 100 total points
ID: 17793673
How about access time? I thought you wanted constant time search.
0
IT, Stop Being Called Into Every Meeting

Highfive is so simple that setting up every meeting room takes just minutes and every employee will be able to start or join a call from any room with ease. Never be called into a meeting just to get it started again. This is how video conferencing should work!

 
LVL 39

Assisted Solution

by:itsmeandnobodyelse
itsmeandnobodyelse earned 100 total points
ID: 17797610
>>>> How about access time?

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

by:BrianGEFF719
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

by:BrianGEFF719
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

by:BrianGEFF719
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

by:sunnycoder
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

by:itsmeandnobodyelse
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

Free Trending Threat Insights Every Day

Enhance your security with threat intelligence from the web. Get trending threat insights on hackers, exploits, and suspicious IP addresses delivered to your inbox with our free Cyber Daily.

Join & Write a Comment

  Included as part of the C++ Standard Template Library (STL) is a collection of generic containers. Each of these containers serves a different purpose and has different pros and cons. It is often difficult to decide which container to use and …
IntroductionThis article is the second in a three part article series on the Visual Studio 2008 Debugger.  It provides tips in setting and using breakpoints. If not familiar with this debugger, you can find a basic introduction in the EE article loc…
The viewer will learn how to user default arguments when defining functions. This method of defining functions will be contrasted with the non-default-argument of defining functions.
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.

762 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

20 Experts available now in Live!

Get 1:1 Help Now