# Help on Mult.asm Classic List Threaded 6 messages Open this post in threaded view
|

## Help on Mult.asm

 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.
Open this post in threaded view
|

## Re: Help on Mult.asm

 Administrator 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?
Open this post in threaded view
|

## Re: Help on Mult.asm

 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.
Open this post in threaded view
|

## Re: Help on Mult.asm

 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.