# Worthwhile Optimization?

2 messages
Open this post in threaded view
|
Report Content as Inappropriate

## Worthwhile Optimization?

 Hello, In creating the mult.asm program I found my first solution would be incredibly inefficient if the numbers were say: 2500 and 4. The way I solved it, it would add 4 to itself 2500 times. So, I added some branching and value checking, and loops to run differently based on which value R[1] or R[0] was larger. While that solution can save an incredible number of steps, I was wondering if it was worthwhile, considering: • That solution doesn't do anything for the worst case run time, 2500*2500 is still going to take a ton of steps. • Does saving steps in Assembly language have much of an effect on the run time of the program? I am not sure the Hack computer has a timing profile/comparison, and I don't think timing the animated views has a direct correlation with real-world run time. Anyone have any ideas?
 Administrator AleKahpwn wrote Hello, In creating the mult.asm program I found my first solution would be incredibly inefficient if the numbers were say: 2500 and 4. The way I solved it, it would add 4 to itself 2500 times. So, I added some branching and value checking, and loops to run differently based on which value R[1] or R[0] was larger. While that solution can save an incredible number of steps, I was wondering if it was worthwhile, considering: • That solution doesn't do anything for the worst case run time, 2500*2500 is still going to take a ton of steps. Those are both good observations: seeing how you could optimize your program, and realizing that the program still had poor performance when multiplying large values. The Mult program in chapter 4 is primarily intended for learning the Hack assembly language and tools. In chapter 12, Operating System, you will learn how to write a more efficient multiplication routine. Think about pencil-and-paper long multiplication done in binary. You never need to add more than 16 numbers to do 16 bit multiplication ``` 0 0 0 0 1 0 0 1 1 1 0 0 0 1 0 0 2500 0 0 0 0 1 0 0 1 1 1 0 0 0 1 0 0 2500 ------------------------------- 0 0|0 0 1 0 0 1 1 1 0 0 0 1 0 0 0 0 0 0 1 0|0 1 1 1 0 0 0 1 0 0 0 0 0 0 1 0 0|1 1 1 0 0 0 1 0 0 0 0 0 0 1 0 0 1|1 1 0 0 0 1 0 0 0 0 0 0 1 0 0 1 1 1 0|0 0 1 0 0 ---------------------|------------------------------- 0 0 0 0 1 0 1 1 1 1 1|0 1 0 1 1 1 1 0 0 0 0 1 0 0 0 0 6250000 ```Since we're only interested in the low 16 bits of the result, the bits on the left are dropped. --Mark