[oclug] Programming Wars 2.0 - September 2001

[cbbrowne at ntlug.org]

On Fri, 03 Aug 2001 09:55:33 MDT, the world broke into rejoicing as
Taavi Burns <tburns at ualberta.ca>  said:
> (of course someone is going to write an arbitrary-precision prime
> finder...but if they're the only one, why not recognise them!  It's tough
> work!)

No, it's not, at least not from the "arbitrary precision" side of things.

The problem is that in order to run out of bits in 64 bits, you need to
have a whole lot of virtual memory, so if the plan is to generate a list,
and walk through it, to verify primality, you need to have storage for
something on the order of 10^18 values.  That's probably more memory
than you have on your Linux box.

The alternative is to, as you get to larger values, use Fermat's 
probabilistic primality test; at that point, if you're using a language
that supports bignums, it's no big deal :-).

By the way, this latter strategy is effectively what I was thinking about
in looking at "priming" the system with a set of primes.  Fermat's test
requires testing against several prime numbers, and so, you need a list...
--
(reverse (concatenate 'string "gro.mca@" "enworbbc"))
http://www.ntlug.org/~cbbrowne/xwindows.html
:FATAL ERROR -- YOU ARE OUT OF VECTOR SPACE