|
Administrator
|
Remember what is important in this project -- writing a program that produces the specified result. Do not worry about getting the result in the most elegant or efficient way -- that's not the goal, the goal is to get an introduction to writing and running an assembly language program for the Hack platform. So don't make the problem harder than it is -- the constraints that the contents in R0 and R1 will not be negative and that their product will be less than 32768, means that even a very brute force approach will run in a reasonable amount of time.
The rest of this post is completely optional -- do not let yourself get sidetracked (unless you want to).
Once you do have a working program, you might choose to see if you can improve it. Not only will this get you more experience with the Hack assembly language and how to bend it to your will, it might help you when you later need to implement the multiplication function for the Math operating system library.
Consider the following: When solving problems in most engineering disciplines (and many non-engineering disciplines), a good approach is to first get ANY solution that correctly solves the problem, even if you know up front that there are things about it that will render it unacceptable as the ultimate solution. That initial correct solution is often a good starting point for figuring out how to improve the solution, perhaps incrementally, until you are left with an acceptable solution that may or may not bear much resemblance to that first one. Even if you end up scrapping the original solution and starting down a different path from scratch, what you learned about how to solve the problem and why the original solution was a dead-end will usually pay valuable dividends as you proceed.
Here are a couple of bookends for you to consider:
One very brute force solution contained 24 assembly language instructions (two of which were needed only to clear a flag used to signal the test script to stop), but took as many as 589814 clock cycles to run.
This program had the advantage that it was very easy to write, being a direct translation of a simple high-level algorithm into assembly.
By leveraging the unusual capabilities of the Hack's C-type instructions, it was possible to shave 6 instructions from the program. This may not sound like much, but because these instructions were located inside a loop, it reduced the worst-case number of clock cycles to 393212, an improvement of 33.3%.
It is tempting to think that the key to making a program run quicker is to make it shorter. But it is quite common that adding instructions to a program can produce a significant improvement in execution speed. In this case, some thought about what determines how many times the program's loop executes led immediately to the addition of 18 instructions (thereby doubling the length of the program) that reduced the worst-case execution time to just 2193 clock cycles, a reduction of over 99%, even though the basic algorithm was untouched and is therefore still the same very brute force approach.
Turning to a fundamentally different approach to the problem, a much more efficient solution contained 28 assembly language instructions and never required more than 334 clock cycles to execute. However, the same observation that was used to reduce the number of passes through the loop in the brute force version was then applied to this solution, resulting in 48 instructions whose worst-case performance only required 188 clock cycles.
So the two extremes are 188 clock cycles versus 589814, a staggering difference of a factor of 3137 times longer.
|
Locked
