Andrew Booth and the ARC
Written by Historian   
Wednesday, 02 May 2012
Article Index
Andrew Booth and the ARC
Drum Storage and APE
Booth's Algorithm

To Canada

 

 

BTC had offered to set up a chair in Computer Engineering at Birkbeck for Booth in order to reward him but the then Chancellor and others caused the proposal to come to nothing. In disgust Booth decided to "depart from the hive of socialist mediocrity".

Within a few days he had offers of chairs from the US, Canada and New Zealand. He chose Canada and became Professor at the Western Reserve University. Booth claims to have made the right choice and certainly did a lot for engineering education in Canada - but you can't help think that this was something of a loss to the UK computer industry.

He did continue designing computers - the M3 was built at Saskatchewan University with the help of a graduate student and he worked from 1965 for ten years providing computing resources for the university.

He seems never to have forgotten his own strange route through the education system and saw it as something that should be reproduced. In 1972 he started a "bright kids" program in Ontario which allowed almost anyone to take university level courses and have them credited against a degree when they finally got round to it.

His own children were among the first to benefit. Both of them started studying at 12 and graduated when they were 16 with first class honours. He felt very strongly that people should be allowed to progress at their own rate and regarded the comprehensive education revolution going on in the UK as being an attempt to bring everyone down to the lowest common level.  His only overtly political achievement was to be the only University President to be listed as an Anarchist in Who's Who.

Booth's Algorithm

As well as designing small computers Booth is also responsible for "Booth's Algorithm" which is a sneaky method for multiplying two binary numbers together.

In those early days how to perform arithmetic was a problem and they didn't have the IEEE standard for floating point calculation to consult. Multiplying two binary numbers together is fairly easy in that it can be done using nothing but shifts and adds.

Each shift multiplies  the multiplicand by two and the adds accumulate the final result.  You add the multiplicand to the partial product if the multiplier bit is 1 and do nothing if it is a 0.

However this simple procedure only works for positive numbers. Negative numbers are generally represented by two's complement notation. That is -X is represented in binary as the positive number 2^n-X. This automatically gives you the correct answer when you do additions and subtractions but when you multiple a pair of two's complement numbers one positive and the other negative the answer is wrong and a correction factor has to be added.

The correction factor depends on the pattern of positive and negative values. Booth came up with a simplified and more regular algorithm for working out a signed multiplication. The algorithm is:

  1. If the multiplier bit is a 1 and the next lower order bit is a 0 subtract the multiplicand from the partial product.
  2. If the multiplier bit is 0 and the next lower order bit is a 1 add the multiplicand to the partial product.
  3. If the multiplier bit is the same as the next lower bit then do nothing.

You can see that this is very simple and should be easy to implement in hardware - but can you see how or why it works?

More Information

Andrew D Booth - Britain’s Other “Fourth Man”

Related Articles

From Baby to Mark I

The Manchester Computers

Maurice Wilkes and EDSAC

Alan Turing's ACE

Alan Turing and his contemporaries (Book Review)

Floating point numbers

Binary - negative numbers

Binary

 

blog comments powered by Disqus

 

To be informed about new articles on I Programmer, subscribe to the RSS feed, follow us on Google+, Twitter, Linkedin or Facebook or sign up for our weekly newsletter.

 

Banner


Claude Shannon - Information Theory And More

Claude Shannon is a little-known character in the history of computing. Even those people who do know Shannon's name think of him as nothing but a theoretician - the inventor of something obscure call [ ... ]



Steve Jobs and the Early Apple Years

Steve Jobs, one of the most well-known of the computer pioneers, has died aged 56.

Our history is of the early years, before the era of the iPhone for which Jobs himself became an icon.


Other Articles



Last Updated ( Wednesday, 02 May 2012 )
 
 

   
RSS feed of all content
I Programmer - full contents
Copyright © 2014 i-programmer.info. All Rights Reserved.
Joomla! is Free Software released under the GNU/GPL License.