Binary Arithmetic |

Written by Mike James | ||||

Monday, 30 October 2023 | ||||

Page 2 of 3
## The place value systemThe place value system is a remarkably clever invention because using it you can give a name to any number without the need for an infinite number of symbols.
Conventionally we use the digits 0 to 9 for bases up to 10 and the letter of the alphabet for bases greater than ten. The use of letters is something that makes a number system look very strange and it tends to frighten people but the principles are just the same. For example, to count in hexadecimal, i.e. base 16, you need symbols for 0 to 15, i.e. one less than the base, and these are 0 to 9, A, B,C,D,E and F. Counting in base 16 starts out exactly like counting base 10 i.e. 0,1,2,3,4,5,6,7,8 and 9, but you don’t go to ten next because you are counting in base 16 and you only move to the next place value when you have a group of 16 to notch up. Instead you use A for ten, B for eleven and so on until you reach F for 15. Add one more and you have a group of 16 which you write down as 10 - again not “ten” but “one zero in base 16”. The rest is just more of the same but it still looks odd to refer to “FF” as a number - 255 to be exact - because that’s what 15 groups of 16 plus one group of 15 add up to. ## Base ArithmeticYou can count in any base you care to select. You can even use a mixed base if you want to. Just recall the examples listed earlier of money, weights and measures and what about counting the days in a year? In this case we don't even stick to a single base for the first place value as a month as 28, 30 or 31 days. Thinking about these examples and you will quickly understand what mixed base counting is all about. What might surprise you a little more is that it is even possible to include negative numbers in a mixed base and it has some practical applications - but that’s another, and slightly esoteric, story!
You may not be aware that there is anything so difficult about arithmetic that it needs anything as dignified as an “algorithm” but that’s just because you’re not a Roman. As I suggested earlier, doing arithmetic using Roman numerals is a big problem. You can just about manage addition but multiplication and division are next to impossible - try and figure out how to do IX times IIIV as a algorithm that doesn't first convert to decimal or any other place value system. The place value algorithms allow you to work out a sum by processing each pair of digits in turn and handling “carries” to the next place. What is interesting is that the algorithms are the same no matter what base you are working in - as long as you remember to stay in the original base as you work. For example, if you want to add 22 to 21 in base three you would add the first, i.e. lowest order, digits, 2+1 to get the result 10. If you added them and got 3 then you are forgetting to stay within the base that you are working in! So the result of adding the first two digits is 0 carry 1. Adding the next two digits. i.e. the high order, 2+2 gives the result 11 and adding the carry gives 12. The final answer to 22+21 is 120 - in base three.
The general idea is that you add the symbols up in each position and then carry any result that is too big into the next positions addition.
## Why Binary?The same sort of addition algorithm will work in any number base so why choose binary for computers? The answer is that, initially at least, the choice of binary wasn’t at all obvious. When Babbage planned his giant mechanical computer the obvious choice was decimal. Why? Simply because he could build cogs and gears that counted in lots of ten and this was the arithmetic system he was used to. More to the point building a decimal computer allowed the values to be entered without the complication of converting to base 2. After all this is the scheme that was used by all of the mechanical calculators that predated Babbage’s idea and that came after it. You could build a binary mechanical computer and it would have been simpler and perhaps might even have been within the capabilities of Babbage’s day but it wasn’t an obvious thing to do. It wasn’t even an obvious thing to do in the early days of the electronic computer - but it probably should have been. Remember the comment about only needing to know how to add together the symbols used in the base to add any two numbers together. It turns out that this is the clue as to why binary is the best choice. The algorithm for place value addition needs a table of how each pair of symbols adds. For example in decimal you need the table:
where the notation 9/1 means result 9 carry 1. You can see that this table is quite large and it is what small children have to learn when they first start doing arithmetic. The size of the table gives you some idea how complex any circuitry or mechanism that does place value arithmetic has to be. There are obvious symmetries in the table that can be used to make the addition mechanism simpler but it is still quite a complex table. Now compare this to a binary addition table:
This is very simple. In fact it is as simple as an addition table can be and this makes it much easier to implement an addition mechanism in binary than any other base. |
||||

Last Updated ( Saturday, 04 November 2023 ) |