My entry for the HP35S Programming Contest in HHC 2007 (long)



#17

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.


#18

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.


#19

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.


#20

Andrés,

You are quite welcome!

Quote:
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).

In my quest to develop a program that might have been competitive in the contest, I had previously tried something that I believe is similar to what you describe. For multiple occurrences of a digit, it would create all of them at once. For example, if there were three eights, it would create "111", then multiply by eight to create "888", then shift the number being built three spaces to the left and add. It did this nine times in a loop.

The main reason I typed your program into my 35 was to compare it to my program based on the above technique. I was initially quite pleased because it was quite a bit faster, until I realized how scrupulous you had been in clearing the registers that you used, both at the beginning and the end of the program. When I added similar clean-up to my program, yours (and my slightly improved version of yours) retook the lead. So, as a last gasp effort, I unwrapped the rebuild loop in manner similar to your unwrapped loop to count the digits. That improved things enough that this version is now slightly faster than your original and even the slightly improved version of your program. It sorts the first group of numbers in 11.21 seconds* (vs. 11.58 seconds for my modified version of your program), and the second group in 9.55 seconds (versus 10.39 seconds.) It is not faster for each individual number. For numbers with no or maybe only one repeated digit, yours is faster. For numbers where there are more multiples, mine is faster. Luckily for me, the test numbers are biased to my advantage:-)

Again, yours was a terrific effort under the constraints presented at the conference. While I may have been able to do a little better, I'm sure you (and others) could easily do as well or better if you spent a little (or as in my case, a lot) more time on the task.

best regards,

Jeff...


* Timings include my reaction time to start and stop a stopwatch. Your timings may vary.


#21

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!!


#22

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).


#23

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

#24

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

:-)


#25

Hi Andrés,

It is possible to speed up the 35S by 50% by changing the value of the
resistor R1.


#26

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! :-)

#27

It would seem to me that you'd have to change the crystal (next to R1) to significantly change the frequency.

Stefan


#28

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.


#29

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


#30

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.


#31

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]]

#32

Hello Stefan,

I can't add anything to Dave's accurate description.


Possibly Related Threads...
Thread Author Replies Views Last Post
  HP35s Program Four Slings Lift Calculation Jean-Marc Biram (Australia) 2 925 12-16-2013, 07:21 PM
Last Post: Jean-Marc Biram (Australia)
  HP35s Calculator Max Rope Tension Program Jean-Marc Biram (Australia) 10 1,814 12-12-2013, 12:03 AM
Last Post: Jean-Marc Biram (Australia)
  HP Prime: adding an entry to a vector Alberto Candel 12 1,722 12-02-2013, 01:18 PM
Last Post: Alberto Candel
  Complex Number Entry on Prime Jeff O. 19 2,356 11-16-2013, 12:34 PM
Last Post: Jeff O.
  HP Prime: Long integers (continued) Helge Gabert 2 591 11-07-2013, 11:24 AM
Last Post: Helge Gabert
  HP Prime: Pass "Long" Integers to a Program Helge Gabert 6 1,013 11-03-2013, 01:12 PM
Last Post: Helge Gabert
  HP Prime polynomial long division bluesun08 13 1,485 10-30-2013, 03:29 AM
Last Post: parisse
  Program to change entry mode on Prime Michael de Estrada 3 731 10-28-2013, 10:13 AM
Last Post: Han
  Does RPN entry mode cause the Prime keyboard to lock up ? Michael de Estrada 14 1,810 10-22-2013, 06:27 PM
Last Post: John Colvin
  HHC 2013 RPN Programming Challenge - Final Thought Jeff O. 7 1,085 10-17-2013, 11:02 AM
Last Post: Jeff O.

Forum Jump: