Re: [boost] Re: Re: Compile time prime numbers, powers and roots

From: Stephen Nutt (snutt_at_[hidden])
Date: 2003-09-18 07:50:21

It's main purpose is to generate/validate prime number constants to used by
the compiler.  My example earlier included a hash table in which it is
frequently desired that the number of entries be prime.  Another example may
be the default seed value of a random number generator.

In both of these cases, only a single prime number is generated, or checked.
As you point out, this is not suitable for the generation of large arrays of
prime numbers, only for single instances.

As for the scale, my original goal was to be able to generate any 32 bit
prime number.  The code I published will only check 28 bit numbers or less
with MSVC 6.0.  I can increase this to 29 bits, but granted, I'm still a few
bits off.  This may be an issue for some people, especially those who need
very large prime numbers for random number seed values.  However it should
suffice for people requiring prime numbers for hash table sizes.  It is
quite likely that better compilers will be able to handle larger numbers,
but I have not tried.  If anyone has MSVC 7.0, or another C++ compiler and
wishes to see how high they can go I'd be interested to know.

The compiler performance is not bad.  It takes the compiler just over a
second to can check the primality of all numbers from 0-199.
 BOOST_STATIC_ASSERT (!is_prime<0>::val);
 BOOST_STATIC_ASSERT (!is_prime<1>::val);
 BOOST_STATIC_ASSERT (is_prime<2>::val);
...
 BOOST_STATIC_ASSERT (is_prime<199>::val);

And in two seconds the compiler can check all 27 prime numbers from 999007
to 999389 inclusive.   Larger numbers of course do take longer.  It takes
almost 2 seconds to check that 450000007 is prime.  However none of these
times I consider an issue as typical use should only include a handful of
primes at most.  I have a 1.6GHz machine, so not to shabby but certainly not
the fastest beast about.

Is there a better algorithm for checking primes?  I was looking into
Fermat's little theorem, but I haven't worked out how to calculate 2^(p -1)
modulus p where p can be any arbitrary 32 bit prime number candidate.  I
believe I can do it for p up to 65535 (which gives 2^p of 1e+19728), but
I've gained nothing as my brute force method handle primes 12 bits larger.
However, I'd be the first to admit that my math theory is poor, and mostly
forgotten so it is possible I've overloked a better method.

Stephen

----- Original Message ----- 
From: "Lucas Galfaso" <lgalfaso_at_[hidden]>
To: <boost_at_[hidden]>
Sent: Thursday, September 18, 2003 1:06 AM
Subject: [boost] Re: Re: Compile time prime numbers, powers and roots

> If such a poor algorithm is implemented, is it really that usefull the
> detection of primes at compile time (and on such a small scale) that is
> worth the compiler to work that hard?
>
> Lucas/
>
> "Stephen Nutt" <snutt_at_[hidden]> wrote in message
> news:001501c37d6c$3f79e940$0d00a8c0_at_dualamd...
> > Lucas,
> >
> > If only prime number detection were that easy :)  I do it the hard way,
> > divide the suspected prime by all numbers >=2 and <= the square root of
> the
> > candidate.  I skip even numbers, but found it was easier to use all odd
> > numbers than to try and determine if the divisor were prime.
> >
> > So to compile is_prime<450000007> I force the compiler to do well over
> > 10,000 divisions before it comes back and says "you've got a prime on
your
> > hands!"
> >
> > Steve
> >
> > ----- Original Message ----- 
> > From: "Lucas Galfaso" <lgalfaso_at_[hidden]>
> > To: <boost_at_[hidden]>
> > Sent: Wednesday, September 17, 2003 8:58 AM
> > Subject: [boost] Re: Compile time prime numbers, powers and roots
> >
> >
> > > how you test if a number is prime. As you might know, verifying that
> > > m for a specific s, is not enough.
> > >
> > > Lucas/
> > >
> >
> > _______________________________________________
> > Unsubscribe & other changes:
> http://lists.boost.org/mailman/listinfo.cgi/boost
> >
>
>
>
> _______________________________________________
> Unsubscribe & other changes:
http://lists.boost.org/mailman/listinfo.cgi/boost