Solved

follow up question - lookup table

Posted on 2006-10-23
11
217 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
Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
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

Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

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

Suggested Solutions

Title # Comments Views Activity
Grammars for C C++ and java 1 138
c++ syntax question 9 57
One named event, multiple event handlers 2 40
learn programming 8 66
Errors will happen. It is a fact of life for the programmer. How and when errors are detected have a great impact on quality and cost of a product. It is better to detect errors at compile time, when possible and practical. Errors that make their wa…
Introduction This article is a continuation of the C/C++ Visual Studio Express debugger series. Part 1 provided a quick start guide in using the debugger. Part 2 focused on additional topics in breakpoints. As your assignments become a little more …
The goal of the video will be to teach the user the concept of local variables and scope. An example of a locally defined variable will be given as well as an explanation of what scope is in C++. The local variable and concept of scope will be relat…
The viewer will learn additional member functions of the vector class. Specifically, the capacity and swap member functions will be introduced.

685 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