TI-BASIC:Algorithmic Optimization
An algorithm refers to your method of solving a problem. Algorithmic optimization, then, relies on choosing the best method to solve a particular problem. Although we could choose a complex problem to illustrate algorithmic optimization, a simpler problem is equally sufficient in demonstrating the process that you go through.
For our example problem, imagine that you want to reverse the characters in a string: if the string is "HELLO", you want it to be "OLLEH". This obviously is a routine that would only really be useful if you are writing a text editor, and are providing different ways for the user to manipulate the text (search, replace, insert, copy, etc.).
Knowing what the routine needs to do, the straightforward approach to writing it is to use another string to store the reversed string, and then concatenating the respective substring to the end of the string while looping over the original string backwards using a For( loop. Here is what the code would look like:
:" " :For(I,length(Str1),1,-1 :Ans+sub(Str1,I,1 :End :sub(Ans,2,length(Ans)-1→Str1
As you can see, we are using the Ans variable to hold our temporary string of reversed characters. You should also note that we initialize it to one space before entering the For( loop. This is because TI-Basic does not allow empty strings -- it will actually return a ERR:DOMAIN if you try to concatenate or manipulate the string.
Although this approach is efficient, there are still other ways to write the routine. One possibility is using Recursion -- the program calling itself. This is basically replicating what the For( loop was doing in the previous routine, except this time we don't have an additional variable to keep track of the string position. Instead we are using the actual length of the string itself, and then subtracting the length of the temporary string from that.
In order for this to work, however, we need to add an additional character to the end of our string. This is because our temporary string is initialized to a space, so we need to offset this character to get the complete reversed string. If we don't add the extra character, our reversed string will be missing the first character from the original string -- we would get "LLEH" instead of "OLLEH".
The actual code for the routine is:
:Ans+sub(Str1,length(Str1)-length(Ans),1 :If length(Ans)<length(Str1 :prgmREVERSTR :sub(Ans,2,length(Ans)-1→Str1
Note that in order to run the routine, you need to initialize Ans on the home screen to a string with one character: a space is the character we like to use, but it can be a question mark, a letter, a number, or whatever you want. Also note that the program name must be the actual name of the program on your calculator; we just called our program REVERSTR because we like names that are descriptive.
When you try out this routine, you should notice that it works just as effectively as the first routine for short or medium length strings. However, if you try using a long string, the routine might not actually complete, but instead the calculator will run out of memory -- giving you a ERR:MEMORY error.
Each time a program call is made, the calculator puts it on a stack and it takes sixteen bytes to keep track of each program call. Because this stack is placed in RAM, whether you are able to completely reverse the string or not depends on how much free RAM you have on your calculator.
The other problem with using this routine is that it has to be its own stand-alone program. This is because the code has to go at the beginning of the program, in order for the recursion to work correctly. Of course, a four line program isn't necessarily bad, but it can be a nuisance having to remember an additional program to use your program.
Using recursion to reverse a string is obviously not going to work for us when you factor in the memory for the program calls and the additional program, so that means we should stick to using a For( loop. Now we need to think about how else we could go about reversing a string.
How about instead of looping over the string backwards and appending the respective substring to the end of the string, we loop forwards and append the substring to the beginning of the string? Does that sound like it would work any better? Well, let's try it.
We are still going to use the temporary string stored in Ans like we did with the other two routines, except this time the original string is stored to Ans instead of just a dummy character. We then loop through each character starting from the beginning to the end, adding it to the beginning of the string as we build up the reversed string.
Here is what the code would look like:
:Str1 :For(I,1,length(Ans)-1 :sub(Ans,2I,1)+Ans :End :sub(Ans,1,I→Str1
Since adding to the beginning of the string alters the index, we must take that into account -- this is where the 2I in the formula comes from. It adds the 2nd character the first time, the 4th character (which was originally the 3rd) next, the 6th character (originally the 4th) after that, and so on.
Comparing the size of the last routine to the size of the first two routines, the code is now smaller, and so coming up with a better algorithm has resulted in a better program. Of course, this required some creative thinking on our part, but it was well worth the effort.
