Binary Math–Subtracting by Adding

Some of my readers who have been teaching Advanced Placement Computer Science (APCS) will remember the BigInt case study. It was a case study involving mathematics using large (very large) integers. As released by the College Board it supported adding, subtracting, and multiplying large integers. You will notice that division was not included. In fact, asking students to implement division was part of the exam.

BigInt introduced the idea that multiplication was actually multiple addition. By extension, students were to figure out that division is multiple subtraction.

Computer science really requires understanding how mathematics works at a deep level. It becomes obvious (one would hope) when trying to understand how Binary, Octal, and Hexadecimal work. We don’t often spend much if any time trying to understand subtraction though.

Recently, on BlueSky I can across a message by Andrew Virnuls linking to a blog post titled Two's Complement and Negative Binary Numbers that explains subtracting by adding negative numbers.

Let me draw the two previous notes in this post together with some history of mine. Back in my university days I worked on a course connecting some test hardware to a computer. The computer was a Digital Equipment PDP-8. Now the 8 was an interesting machine. It didn’t have a hard drive and it was programmed in assembly language entered in Binary. Where as most computers we use today use hexadecimal representation (base 16) the PDP-8 used Octal (base 8). The word size was 12 bits. Not 64, 32, or even 16 – 12.

This word size places some limits and one of those limits was the number of machine language/ Assembly language instructions. There was no multiply, divide or even subtraction instruction. We had to write code to do those things similar to how code was written in BigInt for those operations. We also had to write code to do subtraction. There was an instruction to create the two’s compliment of a number though. That was handy. So we wrote code to find and use the two’s compliment of a number in order to do subtraction.

We used the subtraction routine to implement division. Though to be honest, we tried to avoid having to do multiplication or division in our project to keep performance reasonable.

I think we’re all glad that today’s computers have a lot more layers of abstraction than the PDP-8 had! Of course, and a lot of students do not realize this, most powerful assembly language instructions are actually the result of what is called microcode that works transparently behind the scenes.

We keep moving up the path of abstraction. Hal Berenson addressed this recently in a post called 98% of Developers can’t program a computer which is actually a bit of a success story including how artificial intelligence is helping with higher levels of abstraction.

A Spoon Full of Computer Science

I was thinking about data science lately. The problem is that I don’t know much about data science. I learned about data bases in school and worked with them some in industry but that was mostly about how they work internally. I used to give talks on how B* Trees worked and I could (back then) give serious talks on how databases do journaling. But I never did much of anything with real work data applications. Not professionally at lease. But I do like playing around with data and Excel is my friend.

So my first thought was to look at Bootstrap’s data Science curriculum. I did find their definition:

data science the science of collecting, organizing, and drawing general conclusions from data, with the help of computers.

Sounds good to me. I guess I have been doing some data science after all.

Looking though the curriculum had me thinking about Mark Guzdial's work with teaspoon languages. It feels like there are some things Bootstrap and Teaspoon languages have in common. The idea of teaspoon languages is to add some computer science to other subjects to broaden participation in CS. Bootstrap is using data sets from other subjects in their curriculum. So both are using CS and programming to help students learn about a lot more than just computer science or the subject they are taking. Note that Bootstrap also has Bootstrap Physics! and Bootstrap Algebra.

While I was doing all this thinking Mike Zamansky posted this post - Teaching CS - How early and how often? Mike askes a lot of practical questions about fitting CS into grades k through 8. It’s easy for us zealots to say that CS should be in every grade and expect K8 teachers to make magic but that is not really fair to anyone. Maybe the answer is to have some teaspoons of CS in existing subjects. It doesn’t make a lot of sense unless adding this CS makes learning the subject it is imbedded into better though.

We’ve seen for years in higher education that computer science and [some other area of study] can be a big win. Can we move some of that down to lower grades? Probably though it is going to take some time and some innovation. It’s worth doing, in my not so humble opinion. We use math in other subjects. We use reading and writing in every subject. Might not CS help teach/lean a lot more subjects than just programming? I think so.

Dice, Simulations, and Math

My friend Andrew Parsons send me this link to an interesting video The unexpected logic behind rolling multiple dice and picking the highest. Now I love simulating dice on the computer. Creating a Die class is one of my favorite projects for teaching objects and classes in programming classes. I’ve long kept example of dice with other than six sides around to help students think outside the six sided dice box. So this video grabbed my interest.

Basically the presenter is looking at what happens if you roll two dice and pick the higher value of the two. What sort of advantage does it provide?.  So this gets into some probability and some related math. One of the first things he does is to look at the problem through a simulation (His Python code is here) OK now I personally would be happy with the simulation but of course that gives one the “what happens” but doesn’t go into why it happens. The math does that. The math is presented in an interesting way if a bit fast for me. I can see it being useful in an algebra or statistics class though. Lots of good math stuff. (Can I say “math stuff?)

For a computer teacher, the things this goes though are ripe for simulation problems though. What is the result for two dice? For three dice? And what about dice with more sides than six? What do you think? Have students watch the video at home and build their own simulations to compare with the mathematical results?

BTW the dice at the top of the post were made with a laser engraver that I have been playing with. Figured dice in binary would be fun.