> < ^ From:

< ^ Subject:

Matthew Johnson wrote in his e-mail message of 1996/02/01

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.

Burkhard Hoefling wrote in his e-mail message of 1996/02/05

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

It is correct that 'IsPrimeInt' uses quite a bit of stack space.

'IsPrimeInt' uses a Lucas pseudoprime test for integers that have no

factor less than 1000 and which are strong pseudoprimes for the base 2.

This test computes the trace of an element recursively, where the depth

of the recursion is roughly the number of bits of the tested integer.

What surprises me is that the problem reportedly happens under NextStep.

NextStep should give each process more stack space than what is needed

for 'IsPrimeInt( Fibonacci( 2971 ) );'.

Burkhard continued

In so far, the GAP manual is wrong in claiming that IsPrimeInt can test

numbers with "a few hundred digits".

Well, 'IsPrimeInt' *can* test 'Fibonacci( 2971 )'. But of course it

needs enough resources. On the machine under my desk (a Pentium@90MHz

under FreeBSD 2.1) it needs about 280 KByte stack, 500 KByte heap, and it

takes about 80 seconds.

Burkhard continued

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.

To be precise. 'Fibonacci(2971)' is not the first Fibonacci number that

passes all tests except the last one. The following numbers also pass

all tests except the last one (in fact all also pass the last one too):

3,4,5,7,11,13,17,23,29,43,47,83,131,137,359,431,433,449,509,569,571.

But apparently they are not large enough to trigger this problem.

The recursion depth for 'Fibonacci(2971)', by the way, is 2063.

Burkhard continued

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

The problem with that is, that it would slow down GAP function calls.

For many computations the speed of function calls is critical for the

overall speed. But it could be a compile time option.

Also finding out how much stack space is available and how much is used

for each function frame is very system dependent.

Note that on UNIX workstations this is generally not such a problem.

They provide much (virtual) stack space. Also, if you exhaust the stack

you don't overwrite the heap (I think this is what happens on the Mac).

Instead the GAP kernel is terminated, which is bad enough of course,

but that can't lead to undetected errors.

Burkhard continued

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

The combination of an ordinary pseudoprime test and a Lucas test (as used

in GAP) is generally considered to be stronger than a number of repeated

ordinary pseudoprime tests. One reason is, that an integer that is a

pseudoprime w.r.t. one base is quite likely a pseudoprime w.r.t. other

bases as well. There are known integers that are pseudoprimes w.r.t. to

all bases less than 100. But there are no known integers that fool the

combined test used by GAP.

Furthermore the algorithm used by GAP's 'IsPrime' is not per se

recursive. Only the current implementation of the function 'TraceModQF'

is recursive. This could be replaced by a non-recursive implementation.

Martin.

-- .- .-. - .. -. .-.. --- ...- . ... .- -. -. .. -.- .- Martin Sch"onert, Martin.Schoenert@Math.RWTH-Aachen.DE, +49 241 804551 Lehrstuhl D f"ur Mathematik, Templergraben 64, RWTH, 52056 Aachen, Germany

> < [top]