10/22/04

A student writes (reminding me that I forgot something in my answer to the question from the programming newbie): 

     Hi Dr. Patt,
             
     I was testing my program assignment 2 on sorting small numbers and it
     worked. I then used the randomize machine feature of the lc3 to generate
     random numbers to sort, but it did not work. It took me a while to 
     realize that the problem was overflow when comparing numbers by 
     finding their difference.
                     
     I just wanted to make sure that we don't have make the program work for
     numbers that will cause overflow (numbers of large magnitude and 
     opposite signs) in our programs since we are only dealing with ASCII. 
     Specifically, I want to make sure we don't have to check for overflow 
     during the comparison and use the signs (instead of difference) if 
     overflow occurs.
             
     Thank you very much for your time.
     << name withheld to protect the Extra-randomizer >>

The thing I left out of my comment on programs running correctly is that they have to run correctly when there is random garbage in unspecified registers and memory, NOT just when everything is initalized to zero.

That should not present a problem for you IF you remember to never read an unspecified location if you have not previously in the program written a value to that location. That is, locations either contain instructions or data to be processed, or they are unspecified. Unspecified locations (both registers and memory) must be initialized before they are read. For example, 

        ADD, R2,R2,#5

produces unknown garbage in R2 if you have not initialized R2 to something specific BEFORE executing this instruction.

The operative word above is "unspecified." That is, if a program is to access a file of ten locations (x4050 to x4059, for example) and perform some operation on the entries of that file, then it would not be appropriate to randomize those ten locations. That is, your program does not have to work on all possible garbage in those locations, ONLY on data that satisfies the requirements specified by the problem.

So, for example, if you were asked to sort a set of alphabetic letters (ASCII codes) contained in those ten locations, it would not be expected to work after you randomized the contents of x4050 to x4509. For example, randomizing may put the ASCII code for "?" in x4050, and "?" is not an alphabetic charater -- at least not in English!

So, completing this email (which kills two birds with one stone):

1. The problem the Extra-randomizer had was caused by his too agressive randomizing.

2. A problem is considered correct (100%) if it works correctly with all kinds of garbage in all unspecified locations. That is, the problem is not correct (for example) if it depends on R2 containing 0 before the program starts execution.

Good luck.

Yale Patt