Cyril Guyot <cyril@zoy.org> writes:
> On Sat, Apr 27, 2002 at 02:06:17PM -0500, J?rgen Tischer wrote:
> > I think it's not a bug, it's a too slow algorithm. Have a look of timings on
> > my Dell 8100
>
> I don't think so since on my machine primep(80630964769); returns FALSE
> and primep(80630965313); returns TRUE both in less than a second.
> However they are both prime.
I tried these examples (repeatedly) with the current Maxima
5.9.0pre-cvs under clisp 2.28 and I get TRUE in both cases. So this
could be some implementation specific issue.
But I think Jürgen Tischer is right with respect to your original
example. Here's a short description of the algorithm (gathered from
looking at rat3c.lisp and rat3d.lisp).
Maxima's `primep' begins by doing a pseudo-prime test and if the given
number N passes it (which your number does) `cfactor' is called, which
performs a straightforward trial division: It factors out the highest
powers of 2 and 3 and then of all numbers <= sqrt(N) which are
congruent to 1 or 5 mod 6. The point is that this takes
sqrt(N)/3+O(1) divisions if N is indeed a prime. For your number this
means over 6.0E18 iterations ...
Btw, you can limit the size of the divisors which are tried by setting
`intfaclim' to a reasonable value and by calling `?primep' instead of
`primep' (at the lisp level `$primep' calls `primep' with `$intfaclim'
set to nil). For example, with the default setting for `intfaclim'
this gives
(C1) intfaclim;
(D1) 1000
(C2) ?primep(340282366762482138434845932244680310783);
(D2) TRUE
(C3)
But of course this can hardly be regarded as a reasonable primality
test.
Wolfgang
--
wjenkner@inode.at