Arithmetic by Computer and by Human

4 February 2013

Arithmetic by Computer and by Human

Professor Tony Mann

It is a very great honour to have the opportunity to speak at Gresham College and I should like to express my gratitude for the invitation. It is a particular pleasure to be talking about computing mathematics here because it is a subject in whose history Gresham College itself features prominently, through the pioneering work of some of the early Gresham Professors, of whom I will be mentioning in particular today Henry Briggs, the first Gresham Professor of Geometry, and Edmund Gunter, Professor of Astronomy from 1619 until his death in 1626.

In this series of three lectures I am going to discuss the use of mathematics in computing, and of computers in mathematics.  In today’s lecture we shall see how computers help us to carry out arithmetic operations such as multiplication – and in the process we will meet an educated monkey and discover different ways in which we can perform  multiplications ourselves even if we can’t remember our “times tables”!  When computers do most of our arithmetic for us, and when most mobile phones provide a calculating facility which is always at hand, do multiplication tables still matter?  

Next month we will look at errors – how computers sometimes get the wrong answer, and the implications of their, or their programmers’, fallibility.  In my third lecture, in April, we will look at the role of computers in what many mathematicians think is the pinnacle of their subject, the aspect of mathematics which, for its practitioners, makes it the most important area of human intellectual endeavour.  That is proof – establishing the truth of a proposition with absolute certainty.  This is another area in which computers are making us rethink our attitudes to the nature of mathematics.

Mathematics – number, arithmetic, geometry – is something which most human societies have required.  (I would have said “All human societies” until I read Alex Bellos’s fascinating account of Amazonian tribes who don’t share our concepts of number and time, but who perhaps make judgments based instead on an intuitive grasp of ratios.  The anthropologist Pierre Pica has said, “When I come back from Amazonia I lose sense of time and sense of number, and perhaps sense of space.  I have extreme difficulty adjusting to Paris again, with its angles and straight lines.”)  Shepherds need to count sheep; ancient Egyptians needed to redefine boundaries each year after the Nile flood; parents need to divide food amongst children … the applications of mathematics in everyday life have always been numerous.  Indeed clever experiments have shown that many species of animal can count (up to relatively small numbers), and research suggests that babies know that one plus one equals two even before they can begin to speak.

We learn arithmetic in primary school.  With our decimal place-value system, addition and subtraction are relatively simple – we do the sums digit by digit, with the only complication being the occasional need to “carry one” or “borrow one”.  But multiplication is more complicated: in order to be able to multiply, we spend large amounts of time in primary school learning our multiplication tables by rote.  We use these tables to perform long multiplication – an operation which our childhood experience tells us is much more difficult than addition or subtraction.

Suppose we want to multiply 121 by 213.  The way I was taught is like this – your method may be slightly different:

121
213
363

121
242
25773

Using our carefully-memorised tables, we multiply the first number in turn by each digit of the second, then add the results, displacing each successive row one place to the left.  What we are effectively doing, in fact, is multiplying 121 first by 3, then by 10, and finally by 200, and adding these gives us 121 times (3+10+200) which is 121 times 213.

Many people find multiplication tables difficult to remember.  Good though I was at my tables when I was at primary school, today I have to think a little about 6x9 and 7x8.  I’m not alone in that.  Famously in 1998, the minister then responsible for numeracy in schools, Stephen Byers, when he was asked, during a radio interview, to multiply 7 by 8, answered “54”!  So as a helpful aside, here is old method by which we can check that we have these simple sums right.

We write 8 and 7 in a column, and to the right of each number we put its difference from 10 – that is 2 and 3 respectively.

                                    8                   2

                                    7                   3

Now 2 times 3 is 6:  we write that, and to its left we write the difference along one of the diagonals, which is 7-2, giving us 56.  The proof that this works is left to the audience!

There are other ways we can do multiplications like 121 times 213.  Here is a nice one which has been making the rounds on social media recently, possibly from Japan.  We represent 121 and 23 by groups of horizontal and vertical lines respectively:

We can now read off each of the digits of the product by counting, in diagonals, the intersections of the horizontal and vertical lines.  The top left group gives us two points of intersection; the middle left plus top middle give us four plus one which is five, the bottom left plus middle middle plus top right have two plus two plus three which is seven; bottom middle plus middle right gives one plus six, so seven intersections, and the bottom right group has three, so our product is 25773, exactly as before.

This method is very nice: it doesn’t require memorising tables!  But essentially it is doing exactly the same as our previous calculation.  We are multiplying each digit of the first number by each digit of the second number, and gathering these products appropriately.  I’ve also carefully chosen an example for which it works particularly well: When the number of intersections in a group exceeds nine, for example if we have digits 3 and 4 giving us twelve points of intersection, we have to start carrying, and things get rather more complicated. 

Here’s another way we can do it.  What we do is write our two numbers at the top of two columns.  I’m now going successively to halve the numbers in the left-hand column (ignoring any remainder), and double those in the right-hand:

 

   121     213     60     426     30     852     15    1704      7    3408      3    6816      1   13632     25773

I then look for rows in which the left-hand number is odd – in this case these are numbers 121, 15, 7, 3 and 1 but not 60 and 30.  I add up the corresponding right-hand entries – and they add up to 25773 which is the product I was looking for!

How does this work?  Well, if you had the good fortune to be present at Gresham Professor Raymond Flood’s first lecture earlier in this academic year, you will remember his discussion of the binary system, which is the basis of computers’ representation of number.   Binary notation represents an integer as the sum of powers of 2; just as 19 in our decimal system represents 1x10 + 9x1, so in binary 100112 represents 1x16 + 0x8 + 0x4 + 1x2 + 1x1 = 1910.  One finds the binary equivalent of a decimal number by repeatedly dividing by 2 and noting the remainders.

Now 121 is 1111001 in binary (which means that it is 64+32+16+8+1).  Reading the first column from the bottom up, taking 1 for an odd number and 0 for an even number, I get exactly this representation.  In the right hand column I have from the top successively 1, 2, 4, 8, 16, 32 and 64 times 213, and the ones I choose to add up to give me my answer, chosen because the left-hand numbers are odd, are exactly the multiples of  1, 8, 16, 32 and 64.  I am calculating 213 times 121 as 213 times 64+32+16+8+1.  So in fact I am doing the operation in binary!

I first came across this as the “Russian Peasant” method, but it is also called the Ethiopian method.  It is in fact the method that was used in ancient Egypt!  It requires addition, doubling (which is equivalent to adding a number to itself), halving, and recognising odd numbers, but it doesn’t require any memorisation of tables.  Arguably, it is easier than the method I was trained to use! 

Of course, the ancient Egyptians didn’t have our place-value number system, but they had a system more like Roman numerals.  And I hope to persuade you that this method of multiplying is particularly suited to such systems.  (Don’t use the recent innovation of writing four as IV rather than IIII: this relatively recent notation, introduced after our present numerals had largely replaced the Roman system for calculation, makes our method much more complicated.)  To double a Roman numeral, you simply write it out twice, and gather the like symbols – twice CXXI is CCXXXXII.  You can then convert five Is into a V, two Vs into an X, and so on.  To halve a Roman number, simply remove half of duplicate symbols, turn X into V, L into XXV and so on: half of XXXII is XVI.  Now, as an example, let’s multiply 13 by 31, or rather XIII by XXXI:

 

XIII     XXXI VI     XXXXXXII = LXII III     LLXXIIII = CXXIIII I     CCXXXXIIIIIIII =      

    CCXXXXVIII

    CCC XXXXXXXXX V IIIIIIII      

= CCC L XXXX X III

= CCCC III

And (noting that a Roman number is odd if it contains an odd number of Vs and Is) we see that the answer is 403.  This may look as it it’s complicated, but it’s actually really easy to do!      

So when you next read that the Roman Empire collapsed because their number system was unsuited for arithmetic and could not support the administration of the trading economy, be sceptical!  By this method, multiplying Roman numbers is, I would argue, considerably easier than our method for multiplying numbers with our decimal place-value system.

But whatever method we use, human calculations are fallible.  We all make mistakes and therefore we quickly appreciate the need to check our results.  One way is to repeat the calculation, but that is time-consuming and we may make exactly the same mistake again.  Another is to work with other people, so that we spot each others’ errors.  Let’s try this – I am going to display numbers and ask the audience to shout out the running total.

                                    1000 + 40 + 1000 + 30 + 1000 + 20 + 1000 + 10

Most audiences will shout out 5000 (perhaps the Gresham College audience won’t fall for that one!)  Of course, the answer is 4100, as is clear if we do the sum on paper.  But our human propensity for pattern-recognition takes over.  Part of being human is that we are less good at careful calculation than we are at instinctively detecting patterns and seeking shortcuts, and while these skills are generally an invaluable ability, they can occasionally lead us astray.

So over the centuries mathematicians have devised ingenious ways to check calculations.  Some of them can be used for other purposes.  I’d like now to demonstrate my psychic powers, with a volunteer from the audience (who I will provide with a calculator). I’m going to ask my volunteer to think secretly of a number between 1 and 9, to multiply that by another single digit of their choice, and to continue to multiply the cumulative product by whichever single-digit numbers they choose until they have a six-digit number.  I have no way of knowing any of the numbers my volunteer chose, so I cannot possibly have any idea what this six-digit number is.

I will now ask my volunteer to remove any non-zero digit they wish from the six-digit solution, and tell me the remaining five digits, in any order they wish.  I will then read their mind to reveal what the sixth digit is.

How did I do this?  I used a trick called casting out nines.  If I take any large number, add up its digits, and then subtract nine from this sum as often as I can, what I have left is the remainder when the original number is divided by nine.  For example, the sum of the digits of 4567 is 22, and if I subtract nine twice (or simply repeat the process by adding the digits of the digit-sum itself) I am left with four.  My original number is 9 times 507  plus 4.  This property can be used to check many arithmetical calculations: it will pick up a small error in one digit in a large calculation.

My psychic power was based on my knowledge that the six-digit number my volunteer came up with was (probably) divisible by 9.  In that case the sum of the six digits must be a multiple of 9, and, knowing five of them, I can work out what the sixth must be.  If for example my volunteer chose the digits 3, 7, 6, 9, 7, 6, 8 and 7, their product was 444528.  They might then give me the digits 2, 4, 4, 5 and 8: I add these up to get 23 and I know that the digit I need to add to get a multiple of nine has to be 4, the secret digit.  (How do I know the six-digit number will be a multiple of 9?  Well, I can’t be certain.  But it only needs my volunteer to have included one 9, or two 3s or 6s, amongst their chosen single-digit multipliers, and I believe that happens about 80% of the time.)

Arithmetic is difficult so we have invented a wide range of tools to help us with it, and indeed used tools that were already at hand.  As a child I was strongly discouraged from counting on my fingers. But medieval mathematicians developed powerful means of representing and manipulating numbers using fingers, and many cultures have used finger arithmetic.  My teachers’ and parents’ disapproval, although it strengthened my mental arithmetic, denied me a very powerful mathematical tool.

One of the simplest and oldest arithmetic tools is the abacus. It is powerful, accurate and, when the operator is experienced, can be very fast.  In trials abacus users have been able to perform calculations faster than users of electronic calculators.  And the abacus can be used for more than addition and multiplication – you can find square and cube roots too.

As a teenager, I remember my excitement when I bought a cheap abacus in a gift shop on a family holiday in the Lake District, and found that I could easily calculate square roots with it.  Perhaps I was a slightly unusual teenager to take so much pleasure in that, but I’d like to persuade you how wonderful it is.  So let’s find the square root of 2.

Since multiplying a number by 100 transforms the square root by 10, the square roots of 2 million and of two will have the same decimal digits with only the decimal point moved.  Now in order to find the root to a few decimal places, I’m going to set up 2 on my abacus, leaving six empty rods to the right, which will be used to find the decimal part of the root.  (Balls below the  bar represent, from the right, 1, 10, 100 etc, and balls above the bar represent 5, 50, 500 – 5 times the value of a lower ball on the same rod.) 

I now count off pairs of rods from the right of the abacus and start with the leftmost non-zero pair – I have 02 00 00 00.  Ignoring those rods to the right, I subtract 1, then 3, 5 and further successive odd numbers till I can no longer do so.  In this case I can only subtract 1.  I now bring in the next pair of rods – I have 01 00 00 00 – and I  multiply the last number I subtracted (1) by 10 and add 11, giving 21.  I continue the operation, subtracting 21, 23, 25 and 27 from 100 (leaving 4): I can’t subtract 29.

I bring in two more digits, and multiply the last number subtracted (27) by 10 and add 11, so I am now subtracting 281 from 400.  That leaves 119; I bring in the last two digits and subtract odd numbers beginning with 2821 from 11900.  I take off 2821, 2823 and 2825, and 2827.  At this point only 604 remains so I can’t take away any more.  I add one to the last number I subtracted, 2827, and halve that to get 1414: I have found that the first four digits of the square root of two are is 1.414.  (The true value is approximately 1.414214.)

You may not believe me until you try it on an abacus, but this is much easier to do than to describe!  With a little practice, one finds one’s fingers do the calculations without conscious direction: it’s like playing the piano or driving a car.  But what I think is rather astonishing is that we have been able to find the square root of 2 (and we could have continued to find more decimal places) by using only subtraction – no more complex arithmetic was needed!

How does it work?  Again, that’s an exercise for the audience (my abacus instruction book gave the method without explanation), but you might remember the identity 1 + 3 + 5 + …+ 2n-1 = n2.

The abacus and counters were the tools used by merchants in the middle ages.  Then at the end of the sixteenth century the Scottish mathematician John Napier made two contributions to help calculation.  One was “Napier’s Bones” – a device which allows one to read off the results of multiplication.  Here, having set up 372 in my frame, I can read off the digits of 8 times 372 as 2, 4+5, 6+1 and 6 to give me 2976.

The more significant of Napier’s ideas, because it revolutionised computation and provided the means by which scientific calculations for purposes such as astronomy and navigation were carried out for over three centuries, was Napier’s invention of logarithms.  If you are my age, you were probably taught to use logarithms at school.  Perhaps it was tedious (the heroes of the school stories I read as a boy certainly found it so), but it was effective.  Of course, the cheap pocket calculator has now made the use of logarithms for calculation obsolete for school children, just as mechanical calculators had superseded logarithms for serious computation by the middle of the last century.

Logarithms were a brilliant idea.  We use the fact that

10a x 10b = 10a+b

The clever part is that on the left we have a multiplication and on the right we have an addition.  As we’ve already commented, addition is a much simpler operation than multiplication.  So if we want to multiply A by B, what we do is to find a and b such that 10a = A and 10b = B.  Then A times B is 10a+b.  It might appear that finding a and b from A and B is much harder than the original multiplication, and if we were to do so ourselves that would be the case, but the beauty of it is that we can use pre-prepared tables to look these up.  So for example, to find 2 times 3, I look up my table of logarithms.  I find that the logarithm of 2 is approximately 0.301, and log(3) is about 0.477.  Adding them gives 0.778, and from my table of antilogarithms I find that 100.778 is 5.998, so I have found 2 times 3, solely by addition and by looking up tables, without needing to memorise any multiplication tables!  Essentially logarithms transform the difficult operations of multiplication and division in to the much simpler addition and subtraction.

Of course, this example doesn’t show logarithms to full advantage.  The point is that if we are using logarithms, multiplying, say, 2.3762 by 3.4812 is no more difficult than my calculation of 2 times 3.  In George Bernard Shaw’s play In Good King Charles’s Golden Days, Isaac Newton is asked by his housekeeper “What is three times seven?”  He does the calculation in his head, using logarithms, and is able to tell her almost instantly that the answer lies between 20 and 22.

Great accuracy can be achieved by using suitable tables.  Arguably, it was the invention of logarithms that enabled the developments in mathematical astronomy that changed the modern world.  Interestingly, and rather sadly for those who want their scientific heroes to be pillars of modern rationality), John Napier himself did not consider this invention to be his greatest gift to posterity: he was prouder of a little book in which he analysed the Book of Revelations to prove that the Pope is the Antichrist and to calculate the date of the end of the world.  (His prediction was between 1688 or 1700.)

It was the very first Gresham Professor of Geometry, Henry Briggs, who at the beginning of the seventeenth century worked to make the use of logarithms practical, simplifying Napier’s theory and producing the necessary tables.  Another Gresham Professor, Edmund Gunter, is remembered for a number of mechanical inventions (when he applied to be Savilian Professor of Geometry at Oxford, Henry Savile was not impressed by his use of mechanical devices – “This is mere showing of tricks, man!" – and “dismissed him with scorne”!)   Gunter created a calculating aid with a logarithmic scale, and when in 1632 William Oughtred put two of these together, we had the slide rule – the device universally used by engineers until about thirty years ago.  (The photo shows the one I was trained to use at school.)

Logarithms and slide rules transformed computation, but it was still a highly skilled activity.  Another idea was to do calculation by machine. Such great mathematicians as Pascal and Leibniz designed mechanical calculators, and Charles Babbage took this further: I’ll say more about him in my next lecture.

By the twentieth century mechanical calculators were widely used.  Leslie Comrie, who in the 1930s headed the Nautical Almanac Office at Greenwich (on the campus at which I now work), before he was sacked in 1936 for using the NAO’s facilities to perform calculations for the War Office, pioneered the extensive use of such calculators for scientific computation.  He said in 1924 that his ambition was to abolish the use of logarithms for serious calculation, and in a speech in 1948 he claimed to have succeeded.  (As I have noted, the message didn’t get to schools for another 30 years!)

Some imaginative mechanical devices have perhaps entertainment rather than practical value.  Let me introduce Consul the Educated Monkey, who has certainly mastered his multiplication tables.  Consul was a real performing monkey, a film star, who could eat with a knife and fork and ride a bicycle. The toy was patented in 1916 and made by the Educational Novelty Company of Dayton, Ohio.  If I position his feet at the numbers I want to multiply, Consul will tell me their product.

And now of course we have the electronic computer.  I’ll be saying a lot more about our relationship with computers in my next two talks but I want to finish today with a comment on computer arithmetic.    As we have seen, for a computer, an integer like 19 (which in our decimal notation represents 1x10 + 9x1) is written in binary as 10011 which means 1x16 + 0x8 + 0x4 + 1x2 + 1x1.  Any integer can be represented by a binary number made up of 1s and 0s.  (We can also represent fractions and numbers in “scientific” or “floating point” notation.)

Just as addition for us is simpler than multiplication, so addition for computers is a faster process than multiplication.  But binary multiplication can be accomplished by a combination of shifts and additions.  In decimal notation, we multiply a number by 10 by simply adding a zero at the end (or shifting the whole number one place to the left).  In binary – base 2 – the effect of putting a zero at the end of a number is to double it.  111 (7) doubled is 1110 (14).   So to multiply, say, 19 by 10 – 10011 by 1010 – we can multiply 10011 by 4 – add two zeroes to the end to get 1001100, then add our original number to get 5 times it

1001100
  10011
1011111

We now double the result by adding another 0 – giving 10111110 – or 1x28+1x26 +1x25 +1x24 +1x23 +1x22+1x21  = 128+32+16+8+4+2 = 190, as we hoped.  So in binary multiplication can be accomplished by a suitable combination of shifts – doubling – and additions.  You don’t even need the binary multiplication table!

Does this remind you of anything?  It is exactly the ancient Egyptian method of multiplication!  The method used by our supercomputers and iPhones to do multiplication is not the method we – or at least those of us of my age – learned in primary school: it’s the method used 3000 years ago in a completely different mathematical culture.

So I would suggest that the multiplication tables which we learned with so much time and effort have turned out to be an evolutionary dead end!  It’s the ancient Egyptian method which dominates in the digital age.

However, wonderful though our computers are, just like us, they have been known to give wrong answers on occasion. My next lecture, a month from today, will examine how computers sometimes get it wrong.

Thank you for listening. I am happy to take questions now, or if you would like to comment on this lecture afterwards, please do so on my blog www.tonysmaths.blogspot.com

 

© Professor Tony Mann 2013