Solved

follow up question - lookup table

Posted on 2006-10-23
11
216 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
Networking for the Cloud Era

Join Microsoft and Riverbed for a discussion and demonstration of enhancements to SteelConnect:
-One-click orchestration and cloud connectivity in Azure environments
-Tight integration of SD-WAN and WAN optimization capabilities
-Scalability and resiliency equal to a data center

 
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
 
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 Tool: Postgres Monitoring System

A PHP and Perl based system to collect and display usage statistics from PostgreSQL databases.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

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

Often, when implementing a feature, you won't know how certain events should be handled at the point where they occur and you'd rather defer to the user of your function or class. For example, a XML parser will extract a tag from the source code, wh…
  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 …
The goal of the tutorial is to teach the user how to use functions in C++. The video will cover how to define functions, how to call functions and how to create functions prototypes. Microsoft Visual C++ 2010 Express will be used as a text editor an…
The viewer will be introduced to the technique of using vectors in C++. The video will cover how to define a vector, store values in the vector and retrieve data from the values stored in the vector.

839 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