Help on Mult.asm

[cdrh]

I have no idea how to start writing this program at all. You hinted with a loop, but I don't know where to start with that. All I know is that multiplication is a number * a number = a number adding itself a number of times. For example 3*2 = 3+3. 4*8= 4+4+4+4+4+4+4+4. And of course it works the other way around. How am I suppose to implement this into a loop? I saw some solutions on GitHub, and they make absolutely no sense to me. I understand that I need to figure out the actual loop in high level then translate it to low level, but I don't even know where to start in high level.

[WBahn]

While you could implement multiplication as a loop in which one number is added to itself a number of times determined by the other number, that approach has exponential time complexity in which adding one more bit to the number representation results in it taking twice as long, on average, to perform the operation. For 16-bit signed numbers, your loop might have to go through as many as 32,000 times (in round numbers). This might be tolerable. But make that a 32-bit signed number and you are talking a couple of billion times and a 64-bit signed number and you are talking about a large enough number of times through the loop that it would take thousands of years to perform a single multiplication.

Take a step back and ask yourself how you would multiply two moderately large values by hand, say 16,319 multiplied by 21,937. Make careful note of the steps you take. Then see if you can apply those steps to binary numbers. The basic approach is the same, but you will discover that limiting the digits to either 0 or 1 make it substantially easier.

Have you studied (not just read, but actually studied, working though some examples step by step) the algorithm described in the text?

[cdrh]

Ok, so after looking at someone else's solution that was posted on GitHub and with a help of a friend, I was able to understand their methodology/algorithm. They did what I basically described in the first paragraph. Yes, I understand it's the brute force way, but I cannot think of any other method.

Secondly, I think you're assuming that I know multiple kinds of way to multiply large numbers. I don't. I was simply taught in elementary school the vertical method. Multiply the bottom row to the top row, one number at a time from right to left. Then each time you finish one number, you shift over one unit space. And at the end, you add it all together.

Anyways, after understanding this solution, (https://github.com/dnivanthaka/nand2tetris/blob/master/04/mult/Mult.asm) I realized that they decremented because your assembly language doesn't offer the feature to check if it's equal to some value. So they decremented because you can check if it's 0. The reason I couldn't figure this out because I failed to remember the semantics/rules that were offered in this assembly language, and I couldn't piece it together.

Yes, I understood and worked through the examples given in the video/text, but in my case, it didn't transfer over to this problem of multiplication.

I would like to know the optimal solution if this one isn't the one you were trying to tell me about.

[ivant]

The solution with the 4 * 8 to be computed as 8 + 8 + 8 + 8 is good enough for this task. The idea is to understand how the machine and assembly language works. This code won't be used after that.

You will implement a better algorithm (in Jack this time) when you write the Jack OS in chapter 12.

[WBahn]

Ah... I didn't pay close enough attention to the fact that this question was posted in the Chapter 4 forum and not the Chapter 12 forum. So, yes, using repeated addition is fine for this part of the project. Sorry if I send the thread starter down a rabbit hole.

[WBahn]

cdrh wrote

Secondly, I think you're assuming that I know multiple kinds of way to multiply large numbers. I don't. I was simply taught in elementary school the vertical method. Multiply the bottom row to the top row, one number at a time from right to left. Then each time you finish one number, you shift over one unit space. And at the end, you add it all together.

With the caveat that brute force is good enough for this project, the approach you describe above is the method that is generally implemented in computer-based algorithms. It is often the case that very efficient algorithms are done just by mimicking how we do things by hand -- but this is actually not a coincidence. Humans spent hundred and even thousands of years figuring out very efficient ways to do many things, particularly mathematical things, precisely because the computing platforms available -- us -- were so darned slow. So it's really not too surprising that they often form at least the base of many of our most efficient computer-based algorithms to perform the same tasks.

When you get to Project 12, if you don't see the tie back to the vertical method, as you described it, ask in that forum and we can discuss it then.