Worthwhile Optimization?

classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Worthwhile Optimization?

AleKahpwn
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?
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Worthwhile Optimization?

cadet1620
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
Loading...