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

From: Lucas Galfaso (lgalfaso_at_[hidden])
Date: 2003-09-18 16:06:18

"Stephen Nutt" <snutt_at_[hidden]> wrote in message
news:000d01c37de3$6c1acdd0$0d00a8c0_at_dualamd...
> 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.

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
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.

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
not
> 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
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
>

If you give me a good example that would give you an edge over a runtime
verification, I would reconsider my opinion.

Lucas/

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
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
>
> _______________________________________________
> Unsubscribe & other changes:
http://lists.boost.org/mailman/listinfo.cgi/boost
>