The Museum of HP Calculators

HP Forum Archive 18

 My entry for the HP35S Programming Contest in HHC 2007 (long)Message #1 Posted by Andrés C. Rodríguez on 17 Nov 2007, 9:03 p.m. I would like to share this program, which got the second place in the HHC 2007 Programming Contest. The challenge was to create a program to order the digits of an integer in the range between 1 and 9 999 999 999, zero was not permitted as a digit. So, for instance, 1234512345 will result in 1122334455, 827516 will result in 125678, 9876 will result in 6789, and so on. The program which does it faster will win. I had no prior experience with the HP35S, but had quite experience with HP41C and 42S, and some with HP32Sii and HP33S. The first idea was not to resort (no pun intended) to a sort algorythm, but to count how many appeareances of each digit there were, and create the output accordingly. Another idea was to reuse values stored in variables, instead of reentering a number, because recalling was faster than input. A third idea was to use inline code in place of some loops, since the 35S was plenty of free memory. While this is inefficient from a memory usage point of view, and more difficult to edit and debug, it is faster at execution. There are two parts in the program: LBL A analyzes the input, LBL D builds the output from the data gathered in the analysis part. ISG instructions were used to increment the registers which count the number of times a digit appears. The "skip" part of ISG was of no interest, in fact, the next instruction was always skipped. I used DEG as a rather innocuous instruction, a NOP would properly fit. See that the DEG will never be executed, so calculator settings were not changed. Integer division and reminder operations were used to decompose the original value, storage arithmetic (addition and times-10 multiplication) were used to build the output. Since the challenge stated that the calculator should be returned to the original state, care was taken as to free all memory used by the program, some steps at the end of the program took care of that. As the output-building loops were decrementing, the counters end in zero with no effort. Other variables were specifically zeroed at recall time by means of a "STO -" instruction; finally a variable was zeroed by means of a "x<>" instruction. No flags or modes were changed, although the program looks nicer if run in FIX 0 mode. Now, the code... Brackets were used on the right side of instructions as graphical aids to identify loops and loop nesting. Also brackets on the left side of instructions were used to show the destinations of GTO instructions. ``` - PRGM TOP - A001 LBL A A002 1.009 A003 STO B Keep 1.009 for future use as loop counter A004 STO I Initialize loop counter A005 CLx A006 STO D Set output variable to zero A007 [] STO (I) [] Loop here to clear counters (Regs 1 to 9) A008 ISG I [] A009 GTO A007[] A010 R v Roll down to recover the number to be “sorted” A011 ENTER Start analysis A012 ENTER Keep a copy of number in y A013 10 A014 STO C Keep 10 for future use from a register, it is faster A015 RMDR Get rightmost digit by the reminder operation A016 x=0? If zero… A017 GTO D001 … break! A018 STO I Use digit as index and… A019 ISG (I) … increment respective counter A020 DEG Just a placekeeper, will never be executed A021 CLx And now… (number is still in y) A022 LAST x … recover 10 and … A023 INT / … get the remaining leftside digits by integer division A024 ENTER Repeat analysis for next digit… A025 ENTER (this could have been done by a loop, A026 LAST x but was coded inline for speed, the A027 RMDR HP 35S has plenty of RAM for this) A028 x=0? A029 GTO D001 A030 STO I A031 ISG (I) A032 DEG A033 CLx A034 LAST x A035 INT / A036 ENTER Repeat analysis for next digit… A037 ENTER A038 LAST x A039 RMDR A040 x=0? A041 GTO D001 A042 STO I A043 ISG (I) A044 DEG A045 CLx A046 LAST x A047 INT / A048 ENTER Repeat analysis for next digit… A049 ENTER A050 LAST x A051 RMDR A052 x=0? A053 GTO D001 A054 STO I A055 ISG (I) A056 DEG A057 CLx A058 LAST x A059 INT / A060 ENTER Repeat analysis for next digit… A061 ENTER A062 LAST x A063 RMDR A064 x=0? A065 GTO D001 A066 STO I A067 ISG (I) A068 DEG A069 CLx A070 LAST x A071 INT / A072 ENTER Repeat analysis for next digit… A073 ENTER A074 LAST x A075 RMDR A076 x=0? A077 GTO D001 A078 STO I A079 ISG (I) A080 DEG A081 CLx A082 LAST x A083 INT / A084 ENTER Repeat analysis for next digit… A085 ENTER A086 LAST x A087 RMDR A088 x=0? A089 GTO D001 A090 STO I A091 ISG (I) A092 DEG A093 CLx A094 LAST x A095 INT / A096 ENTER Repeat analysis for next digit… A097 ENTER A098 LAST x A099 RMDR A100 x=0? A101 GTO D001 A102 STO I A103 ISG (I) A104 DEG A105 CLx A106 LAST x A107 INT / A108 ENTER Repeat analysis for next digit… A109 ENTER A110 LAST x A111 RMDR A112 x=0? A113 GTO D001 A114 STO I A115 ISG (I) A116 DEG A117 CLx A118 LAST x A119 INT / A120 x=0? For the leftmost digit analysis… A121 GTO D001 … things are simpler A122 STO I A123 ISG (I) End of analysis! D001 [] LBL D Start building the output in variable D D002 RCL B Recover 1.009 to initialize loop counter… D003 STO - B … and release B, we don’t need it anymore D004 STO I For 1 to 9… D005 [] RCL (I) [] … recall the number of times each digit had appeared D006 x=0? [] If zero… D007 GTO D015 [] … break! D008 [] RCL C [] [] Recall 10… D009 STO x D [] [] … use to shift left the contents of D D010 RCL I [] [] Recall the working digit from counter… D011 IP [] [] D012 STO + D [] [] … and add it to D D013 DSE (I) [] [] Repeat for same digit (also cleans the counters) D014 GTO D008[] [] D015 [] ISG I [] Next digit D016 GTO D005 [] D017 CL STK Prepare to finish, Regs 1-9 have been zeroed, B is clean D018 STO C … so clear the stack and clear C… D019 STO I … clear I… D020 x <> D … and get the result, clearing D at the same time!! ``` I enjoyed a lot with this challenge, which made me stay awaken for a couple of hours that night. I found the HP35S manual good enough to clarify things (as the usage of numbered registers and the specifics of indirect addressing in the particular model). While it is not as good reading as the manuals of the golden years (1975-1990), is rather good, and certainly better than most modern examples. Edited: 18 Nov 2007, 8:28 a.m.

 Re: My entry for the HP35S Programming Contest in HHC 2007 (long)Message #2 Posted by Jeff O. on 20 Nov 2007, 4:21 p.m.,in response to message #1 by Andrés C. Rodríguez Andrés, Thanks for posting your program. I entered it and timed it for the test numbers used for the contest. I did several runs for each number and averaged them. Results are as follows: ```Round 1 Test Numbers Times in seconds Number Run 1 Run 2 Run 3 Average 9971992227 - 3.19 3.13 3.19 3.17 7654321 - 2.68 2.62 2.69 2.64 1234567891 - 3.18 3.09 3.16 3.14 1234554321 - 3.16 3.16 3.15 3.16 ------ Total of Averages: 12.11 seconds Round 2 Test Numbers Times in seconds Number Run 1 Run 2 Run 3 Average 9283746591 - 3.12 3.13 3.07 3.11 321 - 2.00 1.97 2.04 2.00 9999999998 - 3.15 3.18 3.16 3.16 666666 - 2.50 2.44 2.47 2.47 ------ Total of Averages: 10.74 seconds ``` Do the above timings look about right? All in all, a very fine job. Upon reviewing your program, I wondered if there were any "tweaks" that might lead to faster times. The first thing I thought might be worth checking was the use of ISG(I) to increment the registers to count the number of occurrences of each digit. It does seem attractive to use one command to increment the register (well, two commands if you count the dummy DEG command) but it could also be done by either entering or recalling a 1 to the stack, then using STO+(I). Since ISG has to increment a register, then do a test, then decide where to go, I thought the latter approach might be a little quicker. Testing one method vs. the other in a little program that simply executed them 100 times seemed to indicate that I was correct, if 1 was recalled from a register. That would of course require that it be stored earlier, then cleared it at the end. It also required some changes to get the stack back in the necessary configuration. I considered putting a Roll Down ahead of your Clear x, then wondered if a REG command might be faster. In this case, a REGZ is needed, which eliminates the need for the Roll Down and the original Clear x. I also noted that you used a double ENTER command quite a few times. A REGX command can replace two ENTER commands and is also slightly faster. So, With the above changes made, I re-ran the timing tests, with the following results: ```Round 1 Test Numbers Times in seconds Number Run 1 Run 2 Run 3 Average 9971992227 - 3.03 3.03 3.00 3.02 7654321 - 2.62 2.56 2.56 2.58 1234567891 - 3.00 2.97 3.00 2.99 1234554321 - 3.00 3.00 2.97 2.99 ------ Total of Averages: 11.58 seconds Round 2 Test Numbers Times in seconds Number Run 1 Run 2 Run 3 Average 9283746591 - 3.03 2.97 3.03 3.01 321 - 1.94 2.00 1.94 1.96 9999999998 - 3.00 3.03 3.00 3.01 666666 - 2.43 2.40 2.40 2.41 ------ Total of Averages: 10.39 seconds ``` Not a tremendous improvement, but noticeable and certainly worthwhile given the competition you were up against. However, I don't think that the above improvement would have put you in the winner's circle, as I believe Gene reported a total sorting time in the 8 second range, which I assume was for the second set of numbers. The above changes to your program are not in any way intended as criticism or critique of your effort. I just wanted to see if I could speed things up a bit, just for fun. Edited: 21 Nov 2007, 8:09 a.m.

 Re: My entry for the HP35S Programming Contest in HHC 2007 (long)Message #3 Posted by Andrés C. Rodríguez on 22 Nov 2007, 4:44 a.m.,in response to message #2 by Jeff O. Jeff, thank you very much for your comments!! As I had not previously used the HP35S, I was not sure about the "REGX", "REGZ" commands. Surely some of the stack operations would have been more compact, faster and easier to track/debug. Actually, I have seen those commands mentioned elsewhere as powerful operations for equation usage, but was no familiar with them. Thinking with a HP41/42 mindset, as I tend to do, I should have thought of them as "RCL ST X", "RCL ST Z". About the usage of ISG: After the contest, when I typed the program for posting, I wondered for a while about the convenience of incrementing via "STO +", instead of the "ISG" variant. I admit I was tempted by the apparent "elegance" of using "ISG" in this particular way, without altering the stack but, as you proved, the other approach would have been faster. Your suggestions made for an improvement in the range of 4%, hardly irrelevant! Congratulations and, again, thanks. I think that something more clever and effective can be done at the output building stage. I vaguely recalled something I did with the HP42S quite a time ago, it may have helped building some strings faster (i.e.: multiplying and truncating "1111111111" to obtain "nnnnnnn" strings without nested loops). A table-driven approach would also be faster, but the setup time will be very costly for this challenge. I suppose that the winning program did something more efficient on the output building routine. Thank you again very much!! Edited: 22 Nov 2007, 4:47 a.m.

 Re: My entry for the HP35S Programming Contest in HHC 2007 (long)Message #5 Posted by Andrés C. Rodríguez on 1 Dec 2007, 7:35 a.m.,in response to message #4 by Jeff O. Jeff, thank you again, I enjoy this discussion and friendly exchange of ideas as much as the original contest. Quote: Again, yours was a terrific effort under the constraints presented at the conference. As per the "constraints", I can just say that I had no prior 35S specific experience. Also, I was under the effects of a 15-hours trip (Buenos Aires - Dallas - San Diego) in economy seats of fully populated planes. However, despite some urge to sleep, the challenge gave the excuse to stay awaken past dinner, learning a new calculator; something I have not repeated since the HP41C days!!

 Re: My entry for the HP35S Programming Contest in HHC 2007 (long)Message #6 Posted by Don Shepherd on 1 Dec 2007, 8:13 a.m.,in response to message #5 by Andrés C. Rodríguez Andres, I agree with you, that was a great challenge, and I was up until about 3:00 AM Saturday night in my hotel room in San Bernardo trying to make my program work. I did get it to work, but nowhere near fast enough to be in contention. But I loved it. Gene really selected a great problem; so easy to state but so challenging to implement. Since the contest, I have implemented it on the 17bii+ and the 33s. Interestingly, the 33s can process a 10 digit number in about 1 second! I also implemented it on the venerable HP65, and that presented a real challenge given the limited resources of that machine (8 usable registers and 100 lines of program).

 Re: My entry for the HP35S Programming Contest in HHC 2007 (long)Message #7 Posted by Andrés C. Rodríguez on 1 Dec 2007, 2:18 p.m.,in response to message #6 by Don Shepherd Don, thank you for your comments!! Your solution for 17bii is very interesting. As I was no familiar with such solver-based paradigm, I think I would not be able to even think of such a manner to look at this problem. I am also surprised by the fast 33S time, although it was previously reported that the 35S is slower than the 33S. Frankly, I don't like the 33S because of ergonomic reasons (display and chevron keyboard). I have one at work just to have something RPN-capable, but also something I don't care too much about (it can be loaned, drop to the floor, etc. without any suffering on my side). I prefer the 35S, even slower and buggy as it is. However, I hope someday there will be a 35Sii, with no bugs and a better display. Best regards

 Re: HP35S Programming Contest in HHC 2007 , a "hard" solutionMessage #8 Posted by Andrés C. Rodríguez (Argentina) on 22 Nov 2007, 7:04 a.m.,in response to message #2 by Jeff O. Not seriously, but... I was just wondering... Gene hadn't enough time to manually enter the code of each submission (manually, since there is no I/O in the 35S, a real pity) in a single test machine. So, a manner to "win" would be based on tweaking the calculator hardware... (turbo switches were commonplace two decades ago, as some of us may recall). A die-hard aficionado may have opened his HP35S during the night, added some capacitor, crystal, or whatsoever and, the next day, submit his solution in a "modded" machine, perhaps 25% faster than the garden-variety HP35S... :-)

 Re: HP35S Programming Contest in HHC 2007 , a "hard" solutionMessage #9 Posted by Xerxes on 30 Nov 2007, 8:53 a.m.,in response to message #8 by Andrés C. Rodríguez (Argentina) Hi Andrés, It is possible to speed up the 35S by 50% by changing the value of the resistor R1.

 "Beware of programmers who carry screwdrivers"Message #10 Posted by Andrés C. Rodríguez on 1 Dec 2007, 7:43 a.m.,in response to message #9 by Xerxes This phrase appeared on the opening screen of the Crosstalk XVI communications package for DOS (circa 1985), So, in the unlikely event that I manage to assist to HHC again (because of distance and airline fares), I will bring my soldering iron with me! :-)

 Re: HP35S Programming Contest in HHC 2007 , a "hard" solutionMessage #11 Posted by Stefan Vorkoetter on 1 Dec 2007, 1:44 p.m.,in response to message #9 by Xerxes It would seem to me that you'd have to change the crystal (next to R1) to significantly change the frequency. Stefan

 Re: HP35S Programming Contest in HHC 2007 , a "hard" solutionMessage #12 Posted by DaveJ on 1 Dec 2007, 5:03 p.m.,in response to message #11 by Stefan Vorkoetter Quote: It would seem to me that you'd have to change the crystal (next to R1) to significantly change the frequency. Stefan That crystal is the 32.768KHz watch crystal, and is not be used as the main processor clock, it is only for the RTC. The sunplus SPLB31A processor used has an external RC oscillator pin (internal cap), so you do only need to change the resistor value to change the main clock frequency. All HP35S's will therefore have a natural variation in clock frequency, but probably around several percent, and that will change with temperature too. Dave. Edited: 1 Dec 2007, 5:04 p.m.

 Re: HP35S Programming Contest in HHC 2007 , a "hard" solutionMessage #13 Posted by Stefan Vorkoetter on 1 Dec 2007, 7:34 p.m.,in response to message #12 by DaveJ Thanks. I didn't realize the crystal wasn't used for the processor. I also didn't realize the 35s has a real time clock. What is it used for, since there's apparently no way to access it at the user level? Stefan

 Re: HP35S Programming Contest in HHC 2007 , a "hard" solutionMessage #14 Posted by DaveJ on 2 Dec 2007, 5:26 a.m.,in response to message #13 by Stefan Vorkoetter Quote: Thanks. I didn't realize the crystal wasn't used for the processor. I also didn't realize the 35s has a real time clock. What is it used for, since there's apparently no way to access it at the user level? Stefan I have no real idea in that case. The crystal is apparently dedicated to the (hardware?) RTCC module, although I have not checked the full datasheet to make certain. The processor clock is software selectable to be /1, /2, /4, /8, /16, /32, /64 of the main RC clock frequency. So if you could access the right register location you could change the processor speed in software. I'd be surprised if there isn't code already in the firmware somewhere to change the processor speed, the programmers would likely have put it in somewhere for development purposes. Perhaps there is a secret hot-key or instruction that someone will find someday... Dave.

 Re: HP35S Programming Contest in HHC 2007 , a "hard" solutionMessage #15 Posted by Andrés C. Rodríguez on 2 Dec 2007, 9:46 a.m.,in response to message #14 by DaveJ Quote: ... I'd be surprised if there isn't code already in the firmware somewhere to change the processor speed, the programmers would likely have put it in somewhere for development purposes... Well, Gene Wright mentioned that one of the programs submitted for the contest was from no other than Cyrille. If there is someone who may know about such programmers backdoors, he is the one to be asked! Fortunately enough, Cyrille was not the winner; otherwise we could exhaust our lives wondering for such undocumented shortcuts and tricks! So, for the next time, better than a soldering iron and a resistor, please have your "HP 35S byte jumper" ready. It may be hidden in what Cyrille mentioned as the "MMU". [[all of this post should be taken as "light" (I mean: not serious) writing]]

 Re: HP35S Programming Contest in HHC 2007 , a "hard" solutionMessage #16 Posted by Xerxes on 1 Dec 2007, 5:30 p.m.,in response to message #11 by Stefan Vorkoetter Hello Stefan, I can't add anything to Dave's accurate description.

Go back to the main exhibit hall