The decimal numeral system, the numbers that start from 0 and end at 9, are of everyday use in our lives. Sometimes we tend to think that all other systems play a little roles because we do not use them or see them in action.
Well, the binary numeral system might appear to be of more importance than the decimal system; especially if you are talking to someone who is conversant with electronics, computer languages and logic. They can also be of importance to you. Unknown to me, until I read a wikipedia article on
binary numbers , the Ifa priest makes use of this system in divination. I do not recommend though that you learn geomancy or divination because you want to understand the usefulness of maths.
I took the above picture because the positions of the birds is a good example I can use for the positions of the 0s and 1s in a binary system. If you represent a bird sitting on the power line with a 1 and an empty space a 0, the picture will produce the binary number: 10110000100110100110 base 2. Alternatively, if I represent each bird to be a ten in the decimal system, I will oblige your indulgence and make it number 90 base 10. So, for the exercises, we'll try converting the 90 base 10 to base 2 and then 10110000100110100110 base 2 to base 10.
From base 10 to base 2 (or from decimal to binary numeral systems):
A simple system of converting from decimals to binary is to divide the decimal number by 2 and if there is a remainder, place the remainder, which will be a 1, at the rightmost bit position but if there is no remainder, insert a zero. Then divide the resulting decimal number again and continue placing bit positions based on whether or not there are remainders until we arrive at decimal number 0. Then write down the 1 and 0s on the remainder column, starting from the bottom of the column such that the bottom is the leftmost bit position in binary numeral system. Your work is finished.
Let's show this with a table using the birds sitting on the powerline, or decimal number 90.
| Result : Decimal number % 2 | Remainder (leftmost bit position) |
| 90 / 2 = 45 | 0 |
| 45 / 2 = 22 | 1 |
Note our technique. Taking 90 and divide it by 2, we get 45 with a remainder of 0. So we insert 0 in the remainder position. Because the result is not zero, we continue the division. The second division, i.e 45 divided by 2 gives 22 remainder 1.
| 22 / 2 = 11 | 0 |
| 11 / 2 = 5 | 1 |
| 5 / 2 = 2 | 1 |
| 2 / 2 = 1 | 0 |
| 1 / 2 = 0 | 1 |
| 1011010 base 2 |
This dividing and inserting remainders continues to the seventh row when the result becomes 0. When you write down the converted number in binary, from the bottom, taking 1 as the left most bit, then the next is 0 and then 1 and until we get to the last remainder, 0, we get 90 base 10 converted to 1011010 base 2.
From base 2 to base 10 (or from binary to decimal numeral system):
This time, we'll convert the bird positions in binary,10110000100110100110 base 2 to base 10. How many positions are there? Let us count: the leftmost is a 1, then a 0 and counting from there we have 20 bit positions.
There is a system of binary to decimal conversions that uses bit positions and successive additions of their face values and place values to get to the result. The face value is the literal value for a bit position and the place value indicates the bit position, counting from the right starting from 0, to which we raise the number 2. 101 base 2, for simplicity has three (3) bit positions, with the rightmost bit 1, having a face value of 1 and a place value of 20. The next bit position has a face value of 0 and a place value of 21 and the last a face value of 1 with place value of 22. This simple system of conversions adds up the face and place values thus: 1 x 22 + 0 x 21 + 1 x 20 = 4 + 0 + 1 = 5 base 10.
If we apply this technique to a binary number with twenty (20) bit positions, how enormous the multiplications and additions that have to be done, and furthermore, mistakes will surely creep in.
There is a simpler technique, and it is very elegant. In fact, this technique, which I found while reading the wikipedia article on
binary numeral system was what prompted this blog. I just was impelled to share it. It is called the Horner scheme.
These are the steps to apply the scheme:
- Create a prior value and give it a value of 0.
- Multiply the prior value by 2.
- Take the leftmost bit in the binary number and make it the Next Available Bit. Add the result of (2) to the Nest Available Bit.
- Let the result of (3) be the value of a box you will call, the Next Value.
- Now, assign the Next Value to the prior value, or make the Next Value be the value of the prior value.
- Provided there are still some bits that have not been manipulated in the binary number, or the next bit still have some candidates from the binary number, go back to (2).
- If the binary number bit positions is exhausted, then the result of the conversion is the value of the Next Value box.
We can illustrate the Horner scheme with a little table using the 20 bit positions of the birds sitting on the powerline representation.
| Prior Value | x 2 | + Next Bit | Next Value |
| 0 | 0 x 2 = 0 | 0 + 1 (the leftmost bit) = 1 | 1 |
| 1 (the previous Next Value) | 1 x 2 = 2 | 2 + 0 = 2 | 2 |
| 2 | 2 x 2 = 4 | 4 + 1 = 5 | 5 |
We started with a prior value of 0, multiplied it by 2, got 0, then took the leftmost bit as the Next Available Bit, which is a 1 and added it to the earlier result to get a 1 which was placed as the Next Value and then transferred to the prior value. Since there were still bit positions remaining, we continued by multiplying the prior value by 2, adding it to the next bit which is a 0 to get a 2 that was placed into the Next Value box. Continuing this algorithm for the third row resulted in a next value of 5.
| 5 | 5 x 2 = 10 | 10 + 1 = 11 | 11 |
| 11 | 11 x 2 = 22 | 22 + 0 = 22 | 22 |
| 22 | 22 x 2 = 44 | 44 + 0 = 44 | 44 |
| 44 | 44 x 2 = 88 | 88 + 0 = 88 | 88 |
| 88 | 88 x 2 = 176 | 176 + 0 = 176 | 176 |
| 176 | 176 x 2 = 352 | 352 + 1 = 353 | 353 |
| 353 | 353 x 2 = 706 | 706 + 0 = 706 | 706 |
| 706 | 706 x 2 = 1412 | 1412 + 0 = 1412 | 1412 |
| 1412 | 1412 x 2 = 2824 | 2824 + 1 = 2825 | 2825 |
| 2825 | 2825 x 2 = 5650 | 5650 + 1 = 5651 | 5651 |
| 5651 | 5651 x 2 = 11302 | 11302 + 0 = 11302 | 11302 |
So far, we have calculated for fourteen (14) bit positions starting from the leftmost bit. I am sure you have realized how elegant Horner's scheme is compared to the earlier one that depends on face and place values? Especially if your bit positions are in the high numbers. Man, am I breaking out in sweat? Yet, the job has to be completed.
| 11302 | 11302 x 2 = 22604 | 22604 + 1 = 22605 | 22605 |
| 22605 | 22605 x 2 = 45210 | 45210 + 0 = 45210 | 45210 |
| 45210 | 45210 x 2 = 90420 | 90420 + 0 = 90420 | 90420 |
| 90420 | 90420 x 2 = 180840 | 180840 + 1 = 180841 | 180841 |
| 180841 | 180841 x 2 = 361682 | 361682 + 1 = 361683 | 361683 |
| 361683 | 361683 x 2 = 723366 | 723366 + 0 = 723366 | 723366 |
So, finally, when there are no bit positions remaining, we arrive at the value of 723366 base 10.
Try out some exercises at home. You'll soon using this scheme yourself.
I will like to end this blog by noting that the Horner scheme is the conversion from base 10 to base 2 using division by 2 and noting remainders in reverse.
I leave this as an exercise for you to compare both methods. This underscores a trait in mathematicians that I admire very much: they have an open eye for patterns, even the queer variety. They have a knack for knowing what works most of the time if it has worked once in their life. They have an amazing memory recall system. I know it because I have experienced it myself.
Surprisingly, ancient India used binary numbers and applied binary to decimal conversions prior to 2nd century A.D, more than 1500 years before their discovery in the west.
My next post will cover fractional conversions, conversion exercise in decimal and binary systems, part 2 : fractions.
follow me on twitter, @emeka_david or be a friend on facebook, nnaemeka david
No comments:
Post a Comment
Your comments here!