[prev in list] [next in list] [prev in thread] [next in thread] 

List:       kde-devel
Subject:    Re: Algorithm for finding prime numbers
From:       "Wilco Greven" <j.w.greven () student ! utwente ! nl>
Date:       2000-02-28 11:34:25
[Download RAW message or body]

Thank you for your clear explanation.

On Mon, Feb 28, 2000 at 12:28:18PM +0100, Bo Thorsen wrote:
> On Mon, 28 Feb 2000, Wilco Greven wrote:
> 
> > Hi,
> > 
> > I am looking for an algorithm with which one can determine the next prime
> > number when you start counting at a certain number. I want to use it in
> > combination with QDict. I need a QDict which can store x elements, so 
> > according to the Qt docs the dictionary should have a size of nextPrime(x). 
> > Does anyone know of such an algorithm or can I use QDict's of any size 
> > without a big loss of speed?
> 
> Well then the docs are wrong. There is no way you can be sure that you're
> x objects will be placed in x different buckets in the table, therefore it
> does not always make sense to have the size this large. (That being said, 
> the bigger the size, the better chance that objects actually are placed
> in different buckets.) So you have to ask yourself wether or not you need
> to squeeze every bit of performance out of the dictionary or not. If speed
> is all you care about then the docs give the right direction. If not, you
> don't have to be this precise about the size of the dictionary.
> 
> I can explain what happens. A hashtable calculates a number based on the
> key (the QString here) and sets bucketnumber = hashnumber modulo bucketcount.
> When more entries are placed in the same bucket, they are -- in QDict's --
> placed in lists, which means that searches will go linearly through the
> list of entries in the bucket you search in. This is very slow, if the
> bucket count is far smaller than the number of entries in the dictionary.
> But having a couple of entries in each bucket is not a very big deal.
> 
> For up to a couple of hundred entries, a bucket count (the QDict size) of
> 31 is often Ok -- that is, if you don't want pedal to the metal speed. If
> you expect a larger amount of entries, maybe 59 or 83 will do. In any way,
> if you can't find a reasonably fast algorithm like the one you describe,
> just make a static list of primes up to what you think will be
> appropriate. And don't worry about having all primes there.
> 
> Also, remember that each time you resize the dictionary this occurs a
> growing overhead. This means that you should not start with small primes
> and work your way through every single prime, if you expect your database
> to grow a lot. Then skipping a bunch of primes may give better results.
> 
> Last, if you really need the algorithm, try searching the math faqs on
> news lists. Or ask on one of these. They can probably tell you what to do.
> 
> -- 
> 
> Bo Thorsen
> gobo@imada.sdu.dk
> Lahnsgade 31, st.
> DK-5000 Odense C
> Tlf: +45 66 11 83 85
> 
> 

[prev in list] [next in list] [prev in thread] [next in thread]