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

From: Reid Sweatman (drunkardswalk_at_[hidden])
Date: 2003-09-18 08:33:22

> -----Original Message-----
> From: boost-bounces_at_[hidden]
> [mailto:boost-bounces_at_[hidden]]On Behalf Of Stephen Nutt
> Sent: Thursday, September 18, 2003 6:50 AM
> To: Boost mailing list
> Subject: Re: [boost] Re: Re: Compile time prime numbers, powers and
> roots
>
>
> 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

<snipped>

Knuth pretty well beats the problem to death in the "Seminumerical
Algorithms" volume of "The Art of Computer Programming."  He gives several
algorithmic improvements on Fermat's formula, and discusses how to work with
larger numbers using continued fractions.  I'll refrain from quoting any of
it, as it's quite extensive and messy, and everyone's got a copy anyway,
right? <g>.

Reid Sweatman