Shakuntala Devi – the Human Computer

Peter S Magnusson ♦ January 15, 2016 ♦ Leave a comment

Shakuntala Devi (AP Wirephoto)

This was originally posted as an answer on Quora to the question “How did Shakuntala Devi mentally calculate the 23rd root of a 201-digit number correctly?“. 

Devi was a very talented mental calculator, but by no means the extreme prodigy that she has been made out to be in the media, and she certainly couldn’t take the 23rd root of a number “faster than a computer”.

She was an accomplished showman – she grew up traveling with her father and giving performances, and when her father got too old, she travelled by herself and sent money to her family. The modern field of mental calculators generally shies away from words like “prodigy” or “genius”. Mental calculation is obviously related to mathematics, but many of the historically great mental calculators were not particularly knowledgeable in mathematics per se.

By calling her an “accomplished showman”, I don’t mean to denigrate her at all, quite to the contrary. It’s an intricate, and old, art form, dating at least to the 1700s, more akin to the work of an illusionist than that of a professor in mathematics. It takes hard work and dedication to be a good illusionist of any sort. Devi was born, and performed, in a simpler era, one before the internet and computers that have deconstructed much of the “magic” of these artists. And her story in particular – as a poor child traveling in India, earning a living for her family with her demonstrations – holds a deep appeal to us. Especially since, by all accounts I’ve read of those who met her, she was a very special person.

(If you want a demonstration of the “powerful magic” of mental calculation, just search the internet for the tricks involved in solving 3rd roots and 5th roots of large integers in your head. You will astonish your friends and family by just a little effort of rote memorization.)

There are a few things you first have to know about mental calculations of this sort. They are mostly related to memorization and pattern matching, and putting various significant constraints on the problems being asked. If you are not versed in the arts, some tricks that appear very difficult are in fact quite simple. That, after all, is the general art of illusion.

Today, this art form is called “mathemagic”, and notable “mathemagicians” include Martin Gardner, Arthur T Benjamin, Raymond Smullyan, and Persi Diaconis.

Let me take an example from Devi’s life, before I jump into the actual question. Famously, Devi travelled to the US in 1988, including a visit to San Francisco. A Psychology Professor at Berkeley attended one such event, and he published an article about it in 1990 (“Speed of Information Processing in a Calculating Prodigy”, Arthur R. Jensen, INTELLIGENCE 14, 259-274). Jensen describes how he gave two questions to Devi on note cards that he had prepared:

“When I handed Devi two problems, each on a separate card, thinking she would solve first one, then the other, my wife was taken by surprise, as there was hardly time to start the stopwatch, so quick was Devi’s response. Holding the two cards side-by-side, Devi looked at them briefly and said, “The answer to the first is 395 and to the second is 15. Right?” Right, of course! (Her answers were never wrong.) Handing the cards back to me, she requested that I read the problems aloud to the audience. They were: (a) the cube root of 61,629,875 (= 395), and (b) the 7th root of 170,859,375 (= 15). I was rather disappointed that these problems seemed obviously too easy for Devi, as I had hoped they would elicit some sign of mental strain on her part. After all, it had taken me much longer to work them with a calculator”

Let’s look closely at the first problem, finding the cube root of 61,629,875. The third root of an 8-digit number will have exactly three digits (because it will be between 215 and 464). The third digit is trivial, because a number cubed, modulo 10, only depends on the last digit. In fact, most of the digits are identical – if the last digit of a cube is 1, 4, 5, 6, 9, or 0, then it’s the same in the root; 2 and 8 swap places as do 3 and 7. So we know the last digit is “5”. The first digit is trivial too, in an 8-digit cube it can only be 2, 3, or 4. In this case 61 is close to 64, which is 4 cubed. In fact, it’s very close, so we know the answer will be just below 400, because 400 cubed is 64,000,000. Now, what 3-digit number is just below 400 and ends in 5?

That’s why it only took Devi a few seconds to answer. Jensen, a psychologist, doesn’t know the art. Just as it takes a magician to explain what another magician does, it takes an accomplished mental calculator to explain the field to you. What seems amazing (cube root of 61,629,875 in two seconds!) might be straight forward if you know the “trade”.

Though Jensen was not an appropriate judge of these mental feats, he did subject her to a full range of psychological testing, and those are the parts that are valuable reading in his article. Notably, she didn’t score exceptional in any cognitive area, except memory for numbers.

In Devi’s case, we don’t know what techniques  she used for this demonstration. Why? Because she never told people. And why would she. She had made a living since kindergarten as a performer. Professional performers don’t reveal their magic. If they do, it’s not magical any more.

But lots of other mental calculators have shared details, many at least on par with Devi’s abilities and several distinctly stronger – people like Wim Klein, Hans Eberstark, Gert Mittring, and Alexis Lemaire, the latter likely the greatest living mental calculator.

Now, let’s get a bit closer to the actual question.

The original story is that in 1977, at the Southern Methodist University in Dallas, Devi extracted the 23rd root of a 201-digit number. As reported at the time (Dallas Morning News, January 26th and later a bit more sensationalized in an editorial on February 6th), the problem was presented to her from a calculation on a Univac 1101 at the Bureau of Standards, and it took the computer over a minute to calculate it, but it took Devi just 50 seconds. Therefore, she had “beaten the computer”, which became the theme of the media coverage and greatly contributed to her fame.

The problem, as posed, was to take the 23rd root of this number:

916, 748, 676, 920, 039, 158, 098, 660, 927, 585, 380, 162, 483, 106, 680, 144, 308, 622, 407, 126, 516, 427, 934, 657, 040, 867, 096, 593, 279, 205, 767, 480, 806, 790, 022, 783, 016, 354, 924, 852, 380, 335, 745, 316, 935, 111, 903, 596, 577, 547, 340, 075, 681, 688, 305, 620, 821, 016, 129, 132, 845, 564, 805, 780, 158, 806, 771

The answer (in case it’s not immediately obvious to you) is 546,372,891.

The first thing to note was that the Univac 1101 and Devi were solving two completely different problems. Raising a nine-digit number to the 23rd power –  e.g. multiplying a number by itself 23 times – is a much harder problem than taking the 23rd root – if you know that the result will be an integer.

(Parenthetically, the “1101” is probably a typo or some other error. That model is a 1951 vacuum-tube computer that could do about three multiplications per second. Other reports said Univac 1106, or 1108, but that was from 1969 and also a bit old at the time. The “Bureau of Standards” was responsible for running US census data, and thus the principal government progenitor of much of the computer industry. Given the year of 1977, my guess would be that it was actually a Univac 1110, which launched in 1972. Though why anybody would chose a Univac in 1977 is another mystery, since by then IBM had long taken over the industry. But “Univac” was famous and known by readers, after having predicted the Presidential election in 1952 live on television. So it was probably equivalent in people’s minds to “big computer”.)

In general, the difficulty lies not in the size of the number (201 digits) or the power (23). It’s the number of digits in the answer. Now, the 23rd root of a 201-digit number will have nine digits. Remember the example above, of a 3rd root that resulted in a 3-digit answer? The beginning and the end are trivial, the middle requires some thought.

The same principle continues to apply to larger powers – except that the notion of “trivial” becomes “quite difficult”, and the notion of “some thought” becomes “that’s really hard”.

In this case, nine digits, the middle two are the hard ones – the first three and the last four are “easy”.

The last four (2891) of the answer is completely determined by the last four (6771) of the cube.

If you want to test that, try raising the number xxx,xx2,891 to the power of 23 – and insert any numbers you want for the “x”:s. In fact, you can take any integer that ends with “2891” and take it to the 23rd power, and the result will end in 6771.

To know what four digits translate to what four digits, there are a bunch of tables you need to memorize, but that’s not as hard as it sounds. For example, the choice of “23” is not a random. Powers of integers where the power is of the form (4n+3) have (simple) patterns for the trailing digits. In particular the last digit is unchanged so you don’t have to remember it at all. Choosing appropriate power (23 in this case) translates to simpler tables to memorize for this step.

Now, look carefully at the first six digits – “916748”. The number “48” is right next to “50”, which means this six-digit number is halfway between “916700” and “916800”. We’ll soon see how this helps.

Let’s start by taking the first four (9167) and factoring it – that’s 89 * 103. Next we apply log tables – at least that’s one of the standard techniques. For this step, I’ll assume Devi has memorized the first 150 or so logs to five decimal digits.

Log (base 10) of each factor is 1.94939 and 2.01284, respectively. Adding the mantissas yield 0.96223. Remember that log(xy) = log(x) + log(y).

Now let’s grab the “other” number, 9168. That factors into 48 and 191. Again taking the mantissas of the logs and adding them we get 0.68124 + 0.28103 = 0.96227.

Since “48” is so near the middle between 0 and 100, in this example interpolation between 0.96223 and 0.96227 is simple, we get 0.96225.

Thus we know that the log base 10 of the whole 201-digit number is approximately 200.96225. We divide this by 23, and we get 8.73749 (we can first simplify by noting that 200 divided by 23 is 8 with remainder 16, and instead divide 16.96225).

The trick now is to estimate the anti log for 0.73749. The more accurate we get it, the closer to the correct answer we are.

There may be more clever techniques at this stage than I know, but if we’ve memorized logs for all numbers up to 1000, then we know:

mantissa(log(546)) = 0.73719
mantissa(log(547)) = 0.73799

Now these logs are 0.0008 apart, so we linearly interpolate 0.0003 into this: and 3/8 = 0.375. This is a curiously simple interpolation.

So our estimated antilog of 0.73749 is 5.46375.

Now it’s a bit tricky, do we round up or down? Does “75” become “7” or “8”? It’s not as hard as it sounds, since “75” is borderline the answer is easy: logarithms grow slower than linear so interpolation will slightly over-estimate.

So we finally have our answer: the first five digits are 54637, and from earlier we knew the last four digits are 2891, and we get:

546,372,891

Simple? Haha, no, not especially.

Did Devi have to memorize 1000 logarithms to 5 digits? That’s not as hard as it sounds for somebody with (a lot of) talent for remembering numbers. There are clear patterns.

The biggest demand for large log tables is in the precision of the antilog. If she instead had memorized “only” 100 log entries, she would be interpolating between these two mantissas:

mantissa(log(54)) = 0.73239
mantissa(log(55)) = 0.74036

With linear interpolation she would get (0.73749 – 0.73239) = 0.00510 which then divides into (0.74036 – 0.73239) = 0.00797, for an estimate of 5.4640. That’s a little far from 5.4637.

This is where the real talent kicks in. In the 23rd root of a 201-digit number, the first 3 digits, and the last 4, are trivial. The middle two are tricky. You either memorize a log table with 1000 entries, or you have some clever tricks for iterative antilog interpolation, or you’ll get one or two of those digits wrong. On that day in 1977, Devi got it right.

But wait: how was the number “201” chosen, as in, “23rd root of a 201-digit number”? If it was Devi that chose the number, then the log tables you need are much smaller. For a 201-digit number, the 23rd root will have the first 3 digits in the range of 496 to 548. That’s not 1000 different logs to remember, that’s only 53, that’s 95% less stuff to remember for that stage. Because 9-digit numbers can be anywhere from 185 to 207 digits long. Limiting it to 201 digits simplifies it a lot.

Is that what happened? Quite possibly, because we have another hint that I will wrap up with: at the time in 1977, it was reported that “somebody” was worried that she would simply memorize all possible roots. It was reported at the time that “the computer was asked” what the probability was that she guess the right answer, and it reported that the odds were 1 in 58 million. This number also became a part of the legend (mis-characterized as “the odds of her doing this feat was 1 in 58 million”).

I don’t have a Univac 1101, but I with slightly more recent tools I can calculate that for the 23rd power to be 201 digits, the root needs to be between 496,194,761 and 548,441,657, precisely.

In other words, there are 52,246,897 possible numbers if her request was “only 201-digit powers”. That’s awfully close to “58 million”. Somehow she limited her range. Either they miscalculated the number “58 million” back then, or the range was defined in some other manner. What matters is the log function: no matter which range it was that translated into 58 million numbers, she would only need to remember 58 or 59 entries of a log table: we’re talking log 10 here, and it’s only the resolution of the leftmost 2 digits that matter (58).

However she did it, it was quite a feat. She would have had to do all of the above, accurately, in 50 seconds. And note that how she actually went about it might have been even more complicated than what I described; in my reconstruction of her feat, I’ve tapped into the best of (known) modern mental computational techniques. She might not have been familiar with all of them, and in 1977 she most certainly didn’t have easy access to computers with which to try things out.

One comment about the 50 seconds part. We don’t know how long she thought about the problem. If you review carefully the above techniques, you will notice something interesting: the hard part is figuring out what to do with the first five or six digits. The following 191 digits don’t matter – at all! They can literally be anything. So, if you structure your show appropriately, you might for example ask that the number be written on a blackboard. And indeed in this case, judging by pictures that have survived, it was written on a blackboard. And the numbers were grouped in groups of 5 numbers. So while somebody is writing 191 irrelevant numbers, Devi can crunch the hard part of the problem – going from the first 6 numbers of the power to the first 5 numbers of the answer. When she sees the last 4 digits, she has the answer, since this part is simple. If the person writing on the blackboard writes 1 or 2 numbers per second, Devi would have had 2 or 3 minutes to spend on the hard part.

For the record: if a computer had been programmed to use these techniques, the “compute problem” is trivial. So no, she didn’t “beat a computer” that day. What she did was confound her audience, in a manner that rung through the decades.

For a human being it was a formidable demonstration, and for a consummate mathemagician, quite a trick to be remembered for.

Please note that there were a large number of comments on Quora to the above answer that I responded to.