Dear members of the Gap forum,

Mathew Johnson recently reported a problem with the IsPrimeInt
function, namely when testing whether the 2971th Fibonacci number is
a prime. As he reported, the problem is not system dependent (it
occurs on NextStep, Mac and his port to Windows NT).

The reason for Mathew's problem is simply a stack overflow, caused
by performing prime tests on large integers (large strong
pseudoprimes for the base 2, to be more precise). In so far, the GAP
manual is wrong in claiming that IsPrimeInt can test numbers with "a
few hundred digits".

To be more technical, IsPrimeInt performs various prime tests (see the
manual and the documentation in Integer.g for details), and the
2971th Fibonacci number is the first to pass all tests except for the
last one (to be more precise, it is a strong pseudoprime for the base
2). The last (probabilistic) prime test uses recursion to check
whether a number is a prime, and for the 2971th Fibonacci number,
this would require a recursion depth of about 2600, each call
requiring about 160 bytes on my Macintosh this should be system
dependent. Thus a (program) stack of about 400 Kilobytes would be
required for this calculation, while the usual stack size for GAP
seems to be about 64 Kilobytes.

There are two things which I would like to suggest:

- Since this phenomenon is very likely to occur also in other
contexts, GAP should check whether there is still enough processor
stack space when doing a (recursive) function call. This is, of
course, system dependent, and there should be a function in the
system dependent part of GAP which would then be called before every
function call. This, of course, does not resolve the problem with
IsPrimeInt, but it helps finding such problems.

- Perhaps it is useful to use another prime test. For example, as far
as I remember from my lectures on number theory, a reasonable
solution is to pick r positive integers n_1, ... n_r at
random, and to check whether the number p in question is a strong
pseudoprime with respect to all the numbers n_1, ... , n_r. Choosing
the number r large enough, the probability that p is not a prime can
be made as close to zero as desired. (But don't quote me on the
details ...).

I hope that I could be of some help.

Burkhard.

> Dear Fellow GAP users:
> I have ported GAP to Windows NT, which port is not quite ready for returning
> to Martin to be included in his revision control system. However, the
> following bug also appears under the Mac and NextStep builds of the same
> version of the kernel and relevant libraries. The bug is largely explained
> in the comments of the code, but I will say here that removing the call to
> IsPrimeInt() makes the problem go away; I will also say that the crash
> may appear with a quite different error message if any other code is
> added to the loop or if run under the Mac or NextStep versions: under
> NextStep (a GUI-enhanced MACH UNIX) I usually get a "Segmentation Fault",
> under NT I usually get a "STack Overflow" (but occasionally as in
> NExtStep), under MacOS 7.5 I get Segmentation Fault.
>
> Thus I am pretty sure that the problem is not in the NT port. The NT
> port does have the advantage that NT has at least _some_ debugging tools,
> although they are not that helpful with an interpreted program, like a
> GAP program.
>
> One peculiarity that may have something to do with the NT port: following the
> DOS tradition, STDERR is unbuffered, with a separate handle from STDOUT even
> when both point to the same physical device. So I am not sure that the
> comment below about the error output taking place during output of the final
> fibonacci number is really significant.
>
> Matthew Johnson
> Firepower Systems
> Menlo Park California
>
> # fibonacci numbers
> # This program computes Fibonacci numbers and culls the same for primes.
>
> # With the call to IsPrimeInt, this program crashes on the 2971st Fibonacci number
> # All I have been able to find with my primitive tools is that the function call stack
> # is filled with repetitive calls to a EvFunccall (apparently to evaluate IsPrimeInt itself)
> # after which the exception is generated on a call to NewBag()
> # Oh yes, running with the '-g' option shows this crash occurs during/after garbage
> # collection, which in turn takes place before the last Fibonacci number has been
> # entirely printed out.
>
> # Use the following for recursive computation of F(n)
> i := 3;
>
> g := 1;
> fib := [1, 1, 2];
> while i<2972 do # On NT crashes on 2971
> j := 1;
> nfib := fib[i] + fib[i-1];
> Add(fib, nfib );
> Print("\nfib[",i+1,"] = ", fib[i+1]);
> test := IsPrimeInt(nfib); # the failure appears to be here
> if test = true then
> Print("\n\tIsPrimeInt = TRUE");
> fi;
> i := i+1;
> od;
>
>
>