HHC 2016 RPN contest is now live

[Jeff O.]

(10-06-2016 04:26 PM)Jeff O. Wrote:  Also, any idea why I cannot create more than 127 local registers?

Just to close the loop on this, I consulted with Marcus and found that creation of more than 127 local registers must be done via indirection. So, to set 144 local registers one must do as follows:

...
#144
LocR->X
...

I do not believe that the above is specifically stated anywhere in the manual, if so, I was unable to find it. It does follow from footnote no. 112 on page 271 of the manual: "Only arguments up to 127 are storable in an op-code, hence the limit." This was in reference to accessing local registers, but of course would logically apply to keying in something like "LocR 142".

With that mystery (to me) solved, I modified my program to calculate the number of sums n in a k-digit number for k equal up to 13, presented below. It does run a little more slowly than the version limited to 9 digits; there appears to be about a 1.5 second penalty for large sums in 9-digit numbers. It calculates f(13, 117) in about 7.5 seconds. As warned in the manual (p.270), creating so many local registers requires you to be aware of how many steps are in use in program memory. If you have too many program steps used, you'll get a "RAM is FuLL" message when you try to run the program. I had to move some programs to the library so that there were no more than 351 program steps in RAM before it would run. I also added a couple of steps to release the local registers and reset the number of regular numbered registers to 100. Otherwise it stops with no such registers allocated, which would likely affect running other programs.

Code:

001    LBL"HHC"       
002    DEC X          subtract 1
003    #014           constant 14 (10 for k=9, 11 for k=10, 12 for k=11, 13 for k=12, 14 for k=13)
004    x              14 times (target sum -1)
005    +              add number of digits to form count of iterations
006    STO J          store count of iterations in J
007    REGS 000       set number of numbered registers to low value to free space for local regs. 
                      Can be set to 0 since only lettered regs are used
008    #112           constant 112
009    STO A          store initial R000 pointer value
010    #113           constant 113
011    STO B          store initial R001 pointer value
012    #126           constant 126 (122 for k=9, 123 for k=10, 124 for k=11, 125 for k=12, 126 for k=13)
013    STO C          store initial pointer to R014
014    #253           constant 253 (213 for k=9, 223 for k=10, 233 for k=11, 243 for k=12, 253 for k=13)
015    STO D          store initial R141 pointer value
016    #002           constant 002
017    STO K          store initial forced zero sum loop counter in K
018    #142           constant 142 to indirectly set 142 local registers (indirection not required for less than 127)
019    LocR ->X       create 142 local registers (102 for k=9, 112 for k=10, 
                      122 for k=11, 132 for k=12, 142 for k=13)
020    #001           constant 001
021    STO-> A        store initial 1 in LocR001
022    STO .15        store initial 1 in LocR015 (.11 for k=9, .12 for k=10, 
                      .13 for k=11, .14 for k=12, .15 for k=13)
023    LBL 01         Label for overall count loop iteration, easier to keep track of than BACK
024    DSE J          decrement iteration count, skip when zero
025    SKIP 004       skip to update pointers and calculate next sum if not done
026    RCL-> A        done, Recall final sum
027    LocR 000       release local registers (optional)
028    REGS 100       restore 100 standard registers (optional)
029    RTN            finished
030    DEC A          decrement R000 pointer
031    DEC B          decrement R001 pointer
032    DEC C          decrement R014 pointer
033    DEC D          decrement R141 pointer
034    #111           constant 111
035    x=/=A?         is R000 pointer not equal to 111?
036    SKIP 003       if not, skip to check r001 pointer
037    #253           if R000 pointer is equal to 111, set pointer to max local reg
038    STO A          store new R000 pointer
039    SKIP 014       done updating pointers, go calculate next sum
040    x=/=B?         is R001 pointer not equal to 111?
041    SKIP 003       if not, skip to check R011 pointer
042    #253           if R001 pointer is equal to 111, set pointer to max local reg
043    STO B          store new R001 pointer
044    SKIP 009       done updating pointers, go calculate next sum
045    x=/=C?         is R014 pointer not equal to 111?
046    SKIP 003       if not, skip to check R141 pointer
047    #253           if R014 pointer is equal to 111, set pointer to max local reg
048    STO C          store new R014 pointer
049    SKIP 004       done updating pointers, go calculate next sum
050    x=/=D?         is R141 pointer not equal to 111?
051    SKIP 002       if not, done checking/updating pointers, go calculate next sum
052    #253           if R141 pointer is equal to 111, set pointer to max local reg
053    STO D          store new R141 pointer
054    #014           constant 014 (10 for k=9, 11 for k=10, 12 for k=11, 13 for k=12, 14 for k=13)
055    x=/=? K        check if forced zero sum loop count equal 14 
                      (10 for k=9, 11 for k=10, 12 for k=11, 13 for k=12, 14 for k=13)
056    SKIP 004       if no, proceed to calculate sum
057    CLx            if count is multiple of 14…
058    STO->A         ...force current sum to be zero
059    STO K          reset forced zero sum loop counter to zero
060    SKIP 004       skip sum calculation if sum forced to zero
061    RCL->B         recall previous sum
062    RCL+->C        add sum from 14 sums ago (10 for k=9, 11 for k=10, 12 for k=11, 13 for k=12, 14 for k=13)
063    RCL- ->D       subtract sum from 141 sums ago (101 for k=9, 111 for k=10, 121 for k=11, 131 for k=12, 141 for k=13)
064    STO->A         store new sum in current register pointed to by A
065    INC K          increment forced zero sum loop counter
066    GTO 01         loop back to decrement count, update pointers, calculate next sum
067    END

New version 8 steps shorter:

Code:

001    LBL"HHC"      
002    DEC X         subtract 1
003    #014          constant (10 for k=9, 11 for k=10, 12 for k=11, 13 for k=12, 14 for k=13)
004    x             constant times (target sum -1)
005    +             add number of digits to form count of iterations + 1
006    DEC X         decrement to get the number of iterations required to calculate the target sum
007    STO J         store count of iterations in J
008    REGS 000      set number of regs to low value to free space for 102 to 142 local regs
009    #111          constant 111
010    SDR 003       shift digits right 3 places to create .111
011    #112          constant 112, points to lowest local register
012    +             add .111 to set DSE skip index
013    STO A         Set pointer A to initial value of 112
014    INC X         increment by 1 for initial B value
015    STO B         Set pointer B to initial value of 113
016    #13           constant 13
017    +             add to initial B pointer to obtain initial C pointer value of 126
018    STO C         Set pointer C to initial value of 126 (122 for k=9, 123 for k=10, 124 for k=11, 125 for k=12, 126 for k=13)
019    #127          constant 127
020    +             add to initial C pointer to obtain initial D pointer value of 253
021    STO D         Set initial D pointer D value to 253 (213 for k=9, 223 for k=10, 233 for k=11, 243 for k=12, 253 for k=13)
022    #013          constant 13
023    STO K         store initial loop counter to set every (k+1)th sum to zero in K
024    #142          constant 142 to indirectly set 142 local registers (indirection not required for less than 127)
025    LocR ->X      create 142 local registers (102 for k=9, 112 for k=10, 122 for k=11, 132 for k=12, 142 for k=13)
026    #001          constant 001
027    STO-> A       store initlal 1 in registere 112
028    STO .15       store initial 1 in register 127 (.11 for k=9, .12 for k=10, .13 for k=11, .14 for k=12, .15 for k=13)
029    DSE A         Begin loop to calculate sums, decrement A pointer…
030    SKIP 002      skip when equal to 111
031    #142          constant 142
032    STO+ A        if A pointer is equal to 111, set pointer to max local reg by adding 142
033    DSE B         decrement B pointer…
034    SKIP 002      skip when equal to 111
035    #142          constant 142
036    STO+ B        if B pointer is equal to 111, set pointer to max local reg by adding 142
037    DSE C         decrement C pointer…
038    SKIP 002      skip when equal to 111
039    #142          constant 142
040    STO+ C        if C pointer is equal to 111, set pointer to max local reg by adding 142
041    DSE D         decrement D pointer…
042    SKIP 002      skip when equal to 111
043    #142          constant 142
044    STO+ D        if D pointer is equal to 111, set pointer to max local reg by adding 142
045    DSE K         decrement loop counter setting every (k+1)th sum to zero
046    SKIP 004      skip when equal zero
047    #014          constant 14
048    STO K         reset loop counter to 14
049    CLx           clear x for zero,
050    SKIP 003      if count is multiple of 14, skip to force current sum to be zero
051    RCL->B        recall register pointed to by B, sum(k-1,n) 
052    RCL+->C       recall and add register pointed to by C, sum(k,n-1) 
053    RCL- ->D      recall and subtract register pointed to by D, sum(k-1,n-10), forms sum(k,n)
054    STO->A        store new sum(k,n) in register pointed to by A
055    DSE J         decrement loop counting iterations required for input k,n
056    BACK 027      if not zero, loop back to update pointers, calculate next sum
057    LocR 000      if zero, final sum complete, release local registers…
058    REGS 100      restore 100 standard registers (optional)
059    END           stop, final sum displayed

Over 7 years after writing the above code, for some reason I felt like entering it into the WP 34S emulator app on my phone. When it did not work, I had to remember how to program the WP 34S, then troubleshoot the program, and found a typo in the above original listing which I have corrected for posterity. Then of course I had to see if I could improve it, and developed the new version above, which is 8 steps shorter (really only 7 since I saved a step by eliminating the single label) and just better overall, I think. A real WP 34S returns results in about 9 seconds for the worst case input of 13, 117. By way of comparison, the same algorithm on a 35s takes about 9 minutes for that input.