Modular Arithmetic
Okay, so this intentional, but it seems that I have been on
a modular arithmetic spree! Following my last post, I wrote a brief paper on binary
numbers and their use in computing. This led to the question, “What is
addition, subtraction, multiplication, and division like in a binary world.” I
mentioned this to Professor Golden as we were walking out and he mentioned that
just like in decimal arithmetic, place value it key. Boy, was he right on that!
So I started with a worksheet that I downloaded which
allowed me to practice converting binary to decimal equivalents and decimals to
binary equivalents.
I started with converting binary to decimal equivalents. I
tried several different methods for this but the one I settled on is this:
First, you give each column a number, n, starting at the
first digit on the right starting at zero. For each column with a 1 in it, you
simply add 2^n. The sum will be the decimal equivalent. See Image 1.
Next I worked on converting decimals to binary equivalents.
For this one I only tried one method.
I started by writing down the decimal value of 2^n for n =
0, … , 11, from right to left (See the top of Image 1). I would then look at
the number I was converting and find the column, or place value, that was
closest to this number but less than the number. For example, in problem 2b) I
had the number 19. The column n=5 had a decimal equivalent value of 32, which
was too large but the column n=4 had a decimal equivalent of 16, so I put a one
on the page and then subtracted 16 from 19, which left me with 3. Since columns
n = 3 and n = 2 have a decimal equivalent larger than 3, I put two zeros to the
right of the 1. Column n=1 has a decimal equivalent of 2, so I placed a 1 there
and subtracted 2 from 3, which left me with 1. Column n=0 has a decimal
equivalent of 1, so I placed a 1 there and was left with zero. There for 19 has
a binary equivalent of 10011. To see examples, look at Image 1.
Image 1
I then moved on to binary addition and subtraction. Addition
turned out to be a bit easier than subtraction. With addition, if I was adding
an even number of ones in a column, I would place a zero in that column and
then carry over a 1 to the column to the left for each pair of 1s in the column
I was adding. However, if I had an odd number of ones in the column I was
adding, I would still carry over a 1 for each pair, but I would also put a 1 in
the column I was adding. See Image 2, as I am certain that I am making this far
more confusing than it should be.
As for subtraction, all went smoothly until I was force to
borrow from the number column to the left. The best way for me to make this
work is that I would change the 1 in the column to the left to a zero and put
two ones in the column I was subtracting. This would leave me with a pair of 1s
minus one 1, leaving me with 1. Once again, see Image 2.
Image 2
Next came binary multiplication, see Image 3. This turned
out to be easy and very similar, like the other processes described above, to
the process we use for multiplication with decimal numbers. If there is a one
in the first column of the multiplier, you simply write the multiplicand below
the line. If there is a zero, you just write zero. Below that first row, you
write a zero and then if there one in the 2 column, you write the multiplicand
after that, adding an additional zero to the end of the multiplicand for each
column that has a 1 in it. You then add them all together, using binary addition,
to get your final number.
Image 3
I then worked on binary division, which worked very similar
to decimal division. Essentially, you start at the left most column and move to
the right until you have a number that is higher in value than the divisor. You
put a 1 above that column and write the divisor below those columns and
subtract it. You then start pulling down digits from the column to attach to
the end until you have a number larger than the divisor and repeat until you
have reached the end. Yes, I know that this description is terrible, please see
Images 4 & 4.1.
Image 4
Image 4.1
It was at this point that I thought I was done. However, I
decided to take the time to show all of this to my sons. All of them thought it
was cool but Lance was fascinated. We did several problems together and then I
show him the application I had downloaded to my iPhone to check my work. It is
called Hex Calc and you can find it at: https://itunes.apple.com/us/app/hex-calc-simple-pocket-calculator/id335773208?mt=8
When I showed him the calculator, he noticed that the first
4 buttons at the top are BIN, OCT, DEC, HEX. Below them, in the first three
columns, are the numbers 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, and F. When
you push the BIN button, all of the numbers are grayed out except 0 and 1. When
you press OCT, you get 0 through 7, DEC gives you 0 through 9, and of course,
HEX gives you 0 through F. This blew his mind and we spent several minutes
talking about HEX and how each column would go from 0 to F and then you would
have to carry a 1 to the next column to the left. He then asked me to covert
several numbers in HEX to DEC. At first I thought this would be easy, after
all, wouldn’t it be just like binary? As in, number each column started with
zero at the right and going up as you go to the left. Then use that as the
exponent. As in 16^0, 16^1, … , 16^n. Well, the answer is yes and no. You do
use that method but you then need to multiply that value by the number in the
column in question. For binary, this is down without thinking about it. Either
it is zero, in which that column is ignored (Because you are basically multiplying
2^n by zero.) or you add 2^n (2^n times 1). Except with HEX, you have more than
just 0 and 1 to deal with. Think of it this way, the first column can go from 0
to F which is 0 to 15 in decimal. If you add one to F, you get 10, which is HEX
means 1 – 16 and zero ones or, 16 in decimal. However, if you have 50, the
decimal equivalent is 5 – 16s, or 5 * 16^1. Way cool and way fun.
Later that day Lance wrote the following problem on the board
(See image 5 for my work. It is labeled “Lance’s Problem”.)
DC1+100100
He wanted me to add the HEX number and the BIN number
together and give him the answer in DEC. Keep in mind, Lance loves to give me
problems like this and never knows the answer himself. I think he just loves to
watch me work through then and struggle with the problems. He often gets a
chance to walk through the problem with me. Anyway, I did not get the correct
answer in my head. Trying to do 16^3*13 was a bit much. Eventually, once I
switch to pen and paper, I was able to work it out. The answer, by the way, is
3,557.
Image 5
Now, if you have stuck around this far, you are probably not
going to be surprised by what happened next. A question occurred to me, “I
wonder what multiplication, division, addition, and subtraction would be like
in HEX?!” The examples of that can be found in Image 5 and Image 6.
Image 6
Fascinatingly enough, all of this tied in nicely with our discussion
in class on June 16th as we were discussion Carl Friedrich Gauss.
You see, Gauss’s favorite tool in mathematics was modular arithmetic, and he
used this tool to come up with many proofs that mathematicians had been unable
to solve otherwise.
Modular arithmetic is something that we do on a daily basis,
every time we look at a clock and deal with time, without even a second
thought. Yet, show someone a modular math problem or use a numbering system
with a different base, and it is very difficult for us to use until we have
spent a good amount of time with it. Either way, it was stressing out my brain
cells and so I know it was going me some good, and Lance was fascinated by it,
which is an even better reward.
As for me, one of the most challenging aspects of the GVSU
course, MTH 210, was dealing with modulo. I think this is because up to that
point, I don’t think I had ever dealt with math using anything other than decimal
numbers. Just like working through decimal arithmetic can help you see numbers
a combination of other numbers, which can help you see patterns that would otherwise
miss, working through binary arithmetic and hexadecimal arithmetic, increases
your number sense, stretches your understanding of simple as well as complex relationships,
and helps you see relationships that you likely would have missed otherwise.
Thank you for reading,
Jerry
