15 Some Routines involving Large Integers: Prof M H A Newman

It may illustrate the general principles of programming that have been the subject of some other contributions, to describe an actual routine run in Manchester. This has some interest in being, I believe, the first routine for a problem with some intrinsic interest to have been run on a general-purpose machine.

The problem is to test, for prime character, integers of the so-called Mersenne type i.e. numbers M_p = 2^p - 1, where p is itself a prime. The answer to the question is M_p prime or not ? has been found by hand computations for all values of p up to and including p = 257. Our object was to check these values, and to go somewhat further, and we actually reached 353. All the new numbers have negative results, so that it can now be asserted that 2^p - 1 is composite for 127 < p < 353.

When p has values of the order of 300, no direct search by trying factors is feasible even with the fastest imaginable machine. Some 10⁴⁰ years would be needed with present speeds. We use the Lucas test, which answers Yes or No without giving any factor, even when Mp is composite. The test is as follows. Let s₁ = 4, s_n = s_n-1 ² - 2. (Thus s₂ = 14, s₃ = 194). Then for p ≥ 3, M_p is prime if and only if it is divided exactly into S_p-1. The value of the test lies in the fact that we can work modulo M_p at each stage. As soon as we get to an s_h exceeding M_p we replace it by x_h which is equal to the remainder on dividing s_h by M_p. Then X_h+1 is defined to be the remainder of (x_h ² -2) mod M_p ; and so on. Thus a typical step in the computation to be performed is: given x (= x_n-l) find x², subtract 2, divide by M_p and call the remainder z. This is the x of the next step. We do this p-2 times, starting from x=4, and M_p is prime if the final result is 0.

The interest of the calculation from the machine point of view is that the numbers involved have several hundred digits, and it appears that we are faced not only with the exact multiplication, but also the exact division of numbers of this size. However, here we have some luck. In the scale of 2, in which the machine works, M_p is simply 111...11 (p digits), and it is easy to see that the rule analogous to casting out nines works for finding the remainder mod such a number; i.e. to find the remainder of x mod Mp, chop x into lengths of p digits and add them together; then repeat this process till the result is ≤ M_p. Our typical step is thus reduced to this. Given x of p digits calculate x × x, a number z of 2_p digits. Move the most significant p digits of z below the least significant p, and add. (N.B. Numbers are written from left to right, as on the machine, i.e. with the biggest powers on the right). If there is a carry it is at most a single 1, and if this is brought across and added in we obtain the final answer.

The multiplier in the Manchester machine multiplies 40-digit positive numbers, giving the full answer in an 80 digit accumulator. The exact multiplication of two numbers, X and Y, with more than 40 digits, (say 97) is treated as a long multiplication in which the digits are the 40-digit-segments of X and Y.

Here, a,b,u,v are each of length 40; c and w of length 17.

The successive steps are as follows (we write (a) for content of line a:

(1) (a)×(u) to A (= accumulator); thence l.s. (= least significant 40) to line z, m.s. (most significant 40) to line q, say.

In brief, send A to lines z and q.

(2) (b)×(u) to A; add (q) into A; send to lines z + 1, q.

(3) (c)×(u) to A; send to x+2, z+3.

We now have X×(u) in z, z+1, z+2, z+3.

(4) (a)×(v) to A; add (z + 1); send to z+1, q.

(5) (b)×(v) to A; add (z + 2) and (q) and send to z+2, q.

(6) (c)×(v) to A; add (z + 3) and (q.) and send to z+3, z+4.

We now have X×[ (u)+2⁴⁰(v)] in z to z + 4; and it is obvious how the last part, 2⁸⁰(w) is to be added in.

There is one interesting point. Any carry over 80 digits is lost, and the process would therefore go wrong if in step (5) the sum
(b)×(v) + (z+2) + (q) could reach 2⁸⁰. But in fact
(b)×(v), (z+2) and (q) are all ≤ 2⁴⁰ -1, and therefore
(b)×(v) + (z+2) + (q) ≤ (2⁴⁰ -1)² +2 (2⁴⁰ -1) = 2⁸⁰ -1; there is no carry.

The bringing round of the m.s. digits for the reduction mod M_p is also of some interest, but there is no time to give details.

The routine of which this is an outline took about one hour to run, including some checking repetitions not mentioned above.

The total number of digits available to hold programme and working was 128 rows of 40, i.e. 5120.

Discussion on papers by Dr. TURING and Prof. NEWMAN.

Prof. HARTREE said that he thought that Dr. TURING had used the terms induction and inductive variable in a misleading sense since to most mathematicians induction would suggest mathematical induction whereas the process so called by von Neumann and Turing often consisted of repetition without logical connection. Prof, NEWMAN suggested that the term recursive variable should be used. Dr. TURING, however, still thought that his original terminology could be justified.

In reply to a question about future problems to be done on the machine Prof. NEWMAN said that the over-riding consideration was for the engineers and mathematicians to obtain experience. If the problems chosen could have some interest in themselves so much the better. He thought it likely that they would leave number theory for the time being and turn to some problem involving approximation to continuous functions.