Why was 2^127 − 1 an interesting problem for "Baby"?

Question

The BBC News article The 'Baby' that ushered in modern computer age along with the short embedded video begins with:

A machine that took up an entire room at a laboratory in Manchester University ran its first program at 11am on 21 June 1948.

The prototype completed the task in 52 minutes, having run through 3.5 million calculations.

The Manchester Baby, known formally as the Small-Scale Experimental Machine, was the world's first stored-program computer.

It paved the way for the first commercially-available computers in a city known for centuries of science and innovation.

A vignette within the short video shows a clip of someone writing the expression 2¹²⁷ − 1 on a chalk board.

Why would an expression like this be a good test of an early stored-program computing device? It of course would not be the only test, and at some point perhaps computing pi would have also been tried, but why might this have been one important test?

it depends on how the answer to 2^127-1 is solved ... if directly by outputing the number in binary then there is no reason to test this at all as it is just 127 ones but if the output is transformed into decadic then you need to perform a lot of integer arithmetics which would test all the basic instructions of early computer... — Spektre, Jun 22 '18 at 09:42
@Spektre ya it seems quite trivial if the computer was binary, so it piqued my interest. — uhoh, Jun 22 '18 at 09:51
take a look at this str_hex2dec example of hex -> dec conversion on strings I am using for my bignums (as bin <--> hex conversions are trivial) — Spektre, Jun 22 '18 at 10:19
@Spektre Oh, I see! The challenging computation might have been simply the generation of the decadic form itself. It take some time for me to mentally walk back to pre-computer days. — uhoh, Jun 22 '18 at 10:26
For posterity, that's 1121 "FLOPS" (though it likely was not doing floating point). — Will Hartung, Jun 22 '18 at 15:58
Evaluating the ASCII string "2^127-1\n" isn't so trivial, especially if there's no guarantee that the base will be 2. — snips-n-snails, Jun 22 '18 at 17:33
@traal If we're going that route, ASCII didn't exist in 1948. — user, Jun 22 '18 at 22:16
And then try to do it with 32-bit words, 32 words of memory, and a 3-bit instruction set! — snips-n-snails, Jun 23 '18 at 00:29
The Mersenne prime $M_{127}=2^{127}-1$ was the largest known prime from 1876 to 1951. May be they used it to test a prime proving algorithm or some such? — Jyrki Lahtonen, Jun 23 '18 at 05:45
Just as a note, by the way, as to your comment about pi: for primitive computers, calculating multiplication, addition, and subtraction is a much more logical problem than calculating division, which calculating Pi requires. Besides being fundamentally more computationally intensive, division can require arbitrary levels of precision... a simple division problem just a few digits long can yield a real number result with any number of decimal places (for instance, 7/34 or 1/99). Just speculating, but I have to imagine that presented a formidable technical problem to 1948's computing technology. — John Smith, Jun 24 '18 at 05:30
@MichaelKupietz thanks you, I'm so surprised how much I'm learning from responses to this question! This reminds me of even back when I first learned to program one would be very careful to avoid division; e.g. *0.5 versus /2. — uhoh, Jun 24 '18 at 05:40
@JyrkiLahtonen I would guess that this was a large calculation with a known, correct result, so they could just verify that the digits printed were the same and that the computer worked as expected. — Thorbjørn Ravn Andersen, Nov 08 '19 at 12:21
Also the first test for Microsoft Basic was "print 2+2". Apparently that exercised so much of the internal parts that that made them confident they got it right — Thorbjørn Ravn Andersen, Nov 24 '20 at 17:16
The first program? Well you need to test if it works correctly - what would be a good test program? One with a lot of computational steps and a known answer to compare the result with. This sounds like a nice choice. — Thorbjørn Ravn Andersen, Sep 25 '23 at 23:05

score 48 · Accepted Answer · answered Jun 22 '18 at 13:30

48

It's hard to know for sure with just that picture, but that's a Mersenne number and a prime one at that.

When a mathematician writes a Mersenne number on a board they are not thinking about getting all the digits. By far the most interesting and likely question computationally speaking would have been "prove that the number is prime". That could be used as a test since that number was known via e.g. Lucas–Lehmer primality test that indeed it was prime (Mersenne.org says this one was found by Lucas himself, 1876).

However, running a test program that is not supposed to find a result is not necessarily the most robust of tests, because there are many ways the program could fail and still not find anything. Still, it might be helpful if they were able to monitor the progress steps as it ran.

That assumes the question was really used as a reliability test at all. I think it's just as likely that it was put on the board to show the newsreel crew "what kind of problems are of interest to mathematicians, which this machine would be able to resolve a lot faster than humans could". The scientists might have explained how Lucas needed X days/weeks/months to prove that the number is prime but the machine could prove it (e.g. by computing the Lucas-Lehmer test) in seconds/minutes.

Take that and the rest of the reel to the editing room, and it can quickly morph into the narration we are presented with.

answered Jun 22 '18 at 13:30

Euro Micelli

2,685
3
16
24

1

Thank you for your explanation, this makes a great deal of sense! – uhoh Jun 22 '18 at 14:19
...also thanks for the link; of the fifty or so there it looks like only about twelve were known in 1948. – uhoh Jun 22 '18 at 14:46
2

Nice idea, but I seriously doubt that anything even close to a proof for a number bing prime can be implemented in a computer with only 32 words of storage. Thats for data and program. Lucas-Lehmer requires several variables, some of large size. Even if they fit, there would be no space left for the program. Similar for the program. With only 32 program cells, there is no room for complex operations - further complicated since the only ALU functions the Baby could do where subtractions, negation and test for a negative number. The Baby was a proof of concept, not anything like a full system – Raffzahn Jun 22 '18 at 17:09
@Raffzahn So you are thinking more along the lines of it being part of a background briefing perhaps, but not solvable with this particular machine? "...it's just as likely that it was put on the board to show the newsreel crew "what kind of problems are of interest to mathematicians..." – uhoh Jun 22 '18 at 23:31
6

@uhoh The Mersenne prime problem was actually the first problem for the Manchester Mark I, which was developed from the Baby. https://en.wikipedia.org/wiki/Manchester_Mark_1 It's more likely that this made the news than the Baby. – David Marshall Jun 22 '18 at 23:35
7

@uhoh I think Davids comment (see below my answer) might as well have solved this - the picture shown isn't from the introduction of the Baby, but from a news reel about the much later Manchester Mark 1, a greatly enhancement of the Baby (up to 128 instructions on tube and 8000 on drum plus punch tape). The Mark 1 could have been able to solve the mersene problem for 2^127-1 – Raffzahn Jun 22 '18 at 23:37
2

Aha, that makes a lot more sense. I did misread the article as saying 1024 bytes, not bits, which should have been enough for the problem; so I didn't notice just how limited the machine was (but I should have realized. Mea culpa.) – Euro Micelli Jun 23 '18 at 03:20
Even if it is extremely limited, algorithms like the Miller-Rabin primality test require very little state. – forest Jun 23 '18 at 22:27
@Raffzahn, we agree on the whole algorithm being unimplementable on such a limited platform, but I suppose it is still possible to split said algorithm in smaller chunks, on separate punchcards or other loadable media, and run them as separate steps, where the intermediate results will be fed back into the machine at later steps. – sleblanc Jun 24 '18 at 04:09
@sleblanc Sure it may - if the Baby had any means of programmed I/O - except, with only 32 words of storage even the most primitive overlay mechanic would require much of it. Thus it also had no I/O instructions. Keep in mind, each bit of programm and data had to be loaded manually and by hand. – Raffzahn Jun 24 '18 at 09:11

score 33 · Answer 2 · edited Nov 25 '19 at 13:41

Update:

It seems as if David Marshall has found the missing link:

The footage used in the clip is not just from the Manchester Baby, but also from the Manchester Mark 1 which became operational about a year after. As noted its first (useful) program was in fact a proof for Mersenne primes, a perfect fit for the chalkboard scene.

Looks like the combined effort has revealed that this video features less than exact wording (equation vs. expression) and a mixture of pictures, not all belonging to the topic named.

First of all, the clip does not state that this problem was used, especially not used as a test for reliability.

Next a short look at the Baby's Wiki entry would have revealed that one of the first problems used - and indeed used to prove reliability - was to find the highest (all) dividers for a rather large, but still manageable number, in this case 2¹⁸:

The first of three programs written for the machine found the highest proper divisor of 2¹⁸ (262,144), a calculation that was known would take a long time to run—and so prove the computer's reliability—by testing every integer from 2¹⁸ downwards, as division was implemented by repeated subtraction of the divisor. The program consisted of 17 instructions and ran for 52 minutes before reaching the correct answer of 131,072, after the Baby had performed 3.5 million operations (for an effective CPU speed of 1.1 kIPS).

It's all about what to test. In this case it might be not only correct workings, but more about reliability over longer durations. Doing one operation right isn't a big deal and can be tested while building. Doing it a million times under program control is.

Useful programs need to fit several criteria; some may be:

Finish
Finish within a reasonable time
Fit into program space
Use as few instructions as possible

and, most importantly

Have a well known answer

While #1 seems obvious and #2 simple, it isn't, as it needs a problem that scales well, so its input parameter can be used to adjust (expected) runtime. A problem solved in a few seconds doesn't test the machine well; one running for days may be already way outside even the most optimistic guesses about reliability. Being a 32-bit machine, anything between 2⁰ and 2³¹ may have been usable - the latter one with a runtime of maybe a year :))

Similarly, #3, where again #4 is a crucial restriction, as it is less of an issue for a small program to prove its correctness as a transformation of the problem.

And yes, #5 is really obvious. In this case it was perfect as the answers were not only well known, but (back then) known to everyone and a pain in the ass - hence large volumes of books just listing divisors for numbers :))

A problem like finding all divisors or the largest divisor fits well to all of these points and even offers secondary benefits like being repetitive but with changing data.

A vignette within the short video shows a clip of someone writing the expression 2¹²⁷ - 1 on a chalk board.

Well, as usual with such an out-of-context picture, multiple explanations are possible.

First 2¹²⁷-1 is not a problem but a number (the largest number that can be written using 127 bits). And we can only guess what it should mean. Then there is a question mark below, so maybe that is part of the notation? As in "What's the largest divisor for 2¹²⁷-1"?

Then there's a separate section in the Wiki article naming the first three programs, with the third being one for long divisions (written by Turing), so maybe the above describes exactly this program as in allowing to "dividing (anything up to) 2¹²⁷-1 by some number" (*1). This would, of course, mean that the pictures taken where not from first operation but at least 3-4 weeks later (*2) when Turing wrote that program (*3). Above clip being obviously edited and merged from original reels and pictures, this might be quite possible.

Or it is, as so often when media report about something, a staged setup. Just a scientist writing something on a chalkboard to make it look good. After all, the reporter and film crew may have had - as so often - no idea what it's about and were just looking to make it work on the screen. The text "...equations like this..." might be another hint, as it's obviously not an equation - journalists often use words they believe to be fitting but not really words that describe what's shown or happening. Remember how often some stupid header files are dumped on screen when there is some reporting about programming or anything computer related? Not a new invention.

Make your pick, I would name the second one to be true - but I can't rule out the last one.

*1 - 2¹²⁷-1 would be the largest number that can be packed into four 32-bit words while still leaving one bit for a sign or other markings (like NaN). Again a little hint on multi-word arithmetic as Turing obviously programmed. Of course, without more detailed information about how many words that program used (or maybe a variable number) for its 'BigNum' representation, it is just a little hint supporting this explanation.

*2 - Back then that was well within the news cycle :))

*3 - More support for this comes by the fact be that it is hard to imagine that any other, more complex problem (like proving a Mersenne prime) is described, as such would clearly go beyond the abilities of the Manchester Baby. It was only a demonstrator with 32 words of memory, usable either as program or data storage. Already the (rather simple) first program used up 25 of them (17 instructions, 8 data).

Further the machine offered only 3 ALU instructions (subtraction, negation and test for a negative number), so any higher function must be replaced by looping around these. I can see no chance to implement something as complicated as a Lucas Lehmer Test.

"...equations like this" is shown in the screen shot I've included, I can adjust the wording of the question to reflect that if you'd like. — uhoh, Jun 22 '18 at 09:49
The BBC has a bit of history with computers itself, so I wouldn't reflexively assume the video clip is poorly researched or thoughtlessly edited just because it doesn't mirror a Wikipedia article. Let's see what others have to say. — uhoh, Jun 22 '18 at 10:31
To start with, what's shown is not an equation but a number and a questionmark in two lines with no visible relation. So much for 'BBC' has knowledge. Beside, THE BBC has no knowledge, it got employees like any other company, in this case journalists doing their work like anywhere else. They are selected for their ability to tell stories, handle their equipment and finish in time. This hasn't anything to do with 'poor' research. Especially when considering, that you assume something of this clip that has not been said that way. Not the editors fault. — Raffzahn, Jun 22 '18 at 10:45
According to Early British Computers by Simon Lavington (Manchester University Press, 1980), this machine was built to test the Williams tube storage. It was later expanded to become the Manchester Mark I. It is stated that the first realistic problem that it solved was an investigation into Mersenne primes run in April 1949. The footage the BBC used was probably from around this time rather than 1948. — David Marshall, Jun 22 '18 at 23:24
@DavidMarshall that sounds like quite a helpful answer to me! — uhoh, Jun 22 '18 at 23:32
@DavidMarshall Now that's an interesting information and may as well solve the puzzle. The Mark 1 had not only a greatly increased memory (64 words) and two instructions per Word, backt by a comparably huge backstorage, but also a way more sophisticated instruction set which for sure would allow such a calculation. Thanks for the information. — Raffzahn, Jun 22 '18 at 23:33
If this program was a year after Baby, doesn't that make it the same year that the prime solver was run on EDSAC? — Maury Markowitz, Jun 26 '18 at 14:22
@MauryMarkowitz We might have to add the month here I guess. — Raffzahn, Jun 26 '18 at 15:27
@Raffzahn, They are selected for their ability to tell stories, handle their equipment and finish in time et al. That's a pretty sweeping and uninformed set of speculations put across as facts for convenience. — TonyM, Oct 22 '20 at 08:46
I wonder how much storage would have been required to compute the residue of 2^127-1 mod a programmable value in the range 2^30 to 2^31? I would think that would be possible by "set counter to 126. Loop: If MSB or register is set, subtract modulus. Add register to itself. Add 1 to register. Subtract 1 from counter. If MSB of counter isn't set, go to loop. Fitting that into 32 words doesn't seem impossible. — supercat, Sep 28 '23 at 21:20

Why was 2^127 − 1 an interesting problem for "Baby"?

2 Answers2