Confused with binary operations and multiplication.

[HighSchoolerWhoAsksHowTooMuch]

Hi,

I am a bit (pun intended) confused about how to implement the multiplication function of the OS, and more importantly, why we need to use binary. The book states that adding shiftedX to itself is a primitive hardware operation. This makes sense, but 1001101 (example) is not assembled as binary, but rather as a base 10 number, so I am confused as to why we are converting the base 10 number to a base 2 number, instead of doing the algorithm recursively where all single digit multiplication is done repetitively (adding 9 to itself 7 times for 9*7), and the whole multiplication is broken down into single digit multiplication.

Let me know if any clarification would make this post make more sense.

Thank you!

[WBahn]

All information is stored in a computer in binary, because (nearly all) computers are based on electronic circuits that can only represent one of two possible states.

I'm not quite sure what you mean by 1001101 being assembled as a base 10 number.

If you look at the output of the assembler, you will see that it is encoded in the actual machine instructions in binary, just like everything else. Look at the .hack file and you will see this.

If you wanted to store numerical values in something akin to base ten, one way to do so would be using binary-coded decimal (BCD). Many early electronic adding machines and calculators did just that and there are still some applications where it is beneficial to use this approach. In BCD, memory is organized into 4-bit chunks (generally called "nibbles"). Since four bits can represent sixteen binary patterns, the first ten of these, 0000 through 1010, were used to represent the ten decimal digits. The remaining six patterns were not used (or were used to indicate special conditions).

While this allowed algorithms to be developed based on how we humans do base-10 arithmetic, the big advantage was that it was a very good match to input and output devices such as calculator keyboards and displays. The implementation of the arithmetic itself, while more easily understood by humans, was considerably slower than representing numbers using binary.

Aside from all of that, the approach you mention -- breaking things down into a series of single digit multiplications and then doing those single digit multiplications via repeated additions -- is horrendously inefficient (but there are worse algorithms).

How many clock cycles would it take to multiply 9 x 9 using this approach? You need a loop that repeats nine times and within each loop there would need to be an addition, which might produce a carry, which would have to be tracked using another addition. And this is just to process the multiplication of one digit in one number by one digit in the the other. So to multiply 9999 x 9999 there would be 16 such loops, each of which repeat nine times, so you are making a pass through the loop logic 144 times.

But to multiply two n-bit binary numbers together using the algorithm in the text, you have a single loop that gets executed n times total. The loop logic is also very simple.

[HighSchoolerWhoAsksHowTooMuch]

I get it now. Thank you so much for your time!