MTH 495 – Blog Post 3

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 16^th 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