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

From: Ehsan Akhgari (ehsan_at_[hidden])
Date: 2003-09-19 09:09:38

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

I think this utility is handy.  Maybe it's not of immediate use for many
of us, but when we need prime number stuff, it's a good tool to have.

[snip]
> 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.

I will try it with VC++ 7.1 and will report the results.  I can test
with Intel C++ 7.1 as well, but I doubt it can outperform VC++ 7.1 on
compiler limits.

[snip]
> 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.

I have some rough idea in my mind which may not be
appropriate/implementable.  I thought of having a bunch of sorted MPL
sequences of prime numbers.  This way, the is_prime template does not
have to perform the actual calculation; it just needs to try to find the
number in the MPL sequences.  Because the sequences are sorted, it can
find the appropriate sequence by checking if the value falls between its
begin< > and end< >, and then look inside the correct sequence to try to
find the value.  The sequences' source code can be generated by a
runtime implementation of the algorithm, and can be applicable for large
numbers as well.  Of course the source code size may well be over
several megabytes (a guess), so maybe you can split different ranges of
sequences in different source files.

You need a benchmark to see how fast this technique will be, but I guess
it pretty well eliminates a large number of compile-time calculations.

-------------
Ehsan Akhgari

List Owner: MSVC_at_[hidden]

[ Email: ehsan_at_[hidden] ]
[ WWW: http://www.beginthread.com/Ehsan ]