From: Lucas Galfaso (lgalfaso_at_[hidden])
Date: 2003-09-18 16:06:18
"Stephen Nutt" <snutt_at_[hidden]> wrote in message
> It's main purpose is to generate/validate prime number constants to used
> the compiler. My example earlier included a hash table in which it is
> frequently desired that the number of entries be prime. Another example
> be the default seed value of a random number generator.
Nothing that cannot be done at runtime with an extreme performance boost.
> In both of these cases, only a single prime number is generated, or
> As you point out, this is not suitable for the generation of large arrays
> 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
> 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.
So, this implementations is platform dependent. what happens if I want to
compile this on a 64 bit machine?
> 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
> the fastest beast about.
The compiler interprets the code, so, whatever implementation you write
cannot compete with a compiled runtime implementation.
> 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
> 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.
If you give me a good example that would give you an edge over a runtime
verification, I would reconsider my opinion.
PD: With C++ templates you can simulate an entire Turing machine, this is no
reason to use that power to that extent.
> ----- 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
> > > divide the suspected prime by all numbers >=2 and <= the square root
> > the
> > > candidate. I skip even numbers, but found it was easier to use all
> > > 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
> > > 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:
> Unsubscribe & other changes:
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk