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

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

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

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

But why would I want to calculate the same constant at run time, when it is
a CONSTANT that can be know at compile time?  If in my lazy way I do
int a = 8 << 256;
I'd hope the compiler would insert the constant 0x800, even though at
runtime the calculation would be much faster.

> > 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?
Sure it would work.  But as I stated before, it will not work for huge
primes.  I now have it working for all 32 bit primes.  What if I had a 64
bit machine and had the following line of code
int x[0x1000000000000]    // 4096 billion integers
Just because I have a 64 bit machine doesn't mean I can expect everything to
work to the new 64 bit limits does it?

> > 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.
I'm not trying to compete with compiled code.  However, if I am compiling on
a 3GHz machine, and running on an embedded 1MHz 6502 which only has 8 bit
registers, no divide or multiplication operators, I'll sure kick the pants
off the 6502 with the compiler version.

OK, extreme.  Static type checking at compile time is slower that dynamic
type checking at run time, but I'd wager that most people here love static
type checking.  I'm adding a method to do static value checking.

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

I have two trivial cases when I would like a prime numbe at run time.

1)
template <typename T, unsigned table_size> hash_table
{
public:
    // ... implementation here

private:
    BOOST_STATIC_ASSERT (is_prime<table_size>::val);
    T hash[table_size];
};

2) Embedded computers typically have limited program space.  I don't want to
bloat my code with a 100+ byte prime number function when the compiler can
figure it out for me and save me 100 bytes.

> Lucas/
>
> PD: With C++ templates you can simulate an entire Turing machine, this is
no
> reason to use that power to that extent.
><snip>