[VA] Short & Sweet Math Challenges #23: "May the 4th Be With You !" Special

[Jeff O.]

One final (hopefully) update: With some encouragement and advice from Valentin, I developed yet another version of my program. Valentin suggested that I eliminate excessive use of Y^X and instead pre-compute the digits to the powers (i.e., 0^N, 1^N, …9^N) and sum them according to the digits in the number. So instead of calculating 5^8, for example, merely sum the pre-computed value of 5^8 if there is a 5 in the 8-digit number under evaluation.

I was initially unsure if I could apply it due to the manner in which prior versions create and check numbers containing zeroes. See above for how I did that, suffice it to say that it would require creating and storing the values of 0 through 9 to the Nth power for each number, because my prior method changes the number of digits at each number checked. So pre-computing 0 through 9 to Nth power for each new number of digits at each number would not be expected to save much if any time.

But I liked the idea, so I decided to see if I could alter my method of generating input numbers to allow it to be used. The goal would of course be to generate all one-digit numbers, then all two-digit numbers (including those with one trailing zero), then all three-digit (including those with one or two trailing zeroes), etc., on up to all 11 digit numbers. This would enable me to pre-compute 0^N, 1^N, …9^N only when the number of digits is increased by one, i.e., only 11 times for the entire run of the program, which is I’m sure what Valentin intended. With a little effort, I was able to do just that. My prior method of generating numbers would go like this:

19999999999
22222222222
22222222223
22222222224
etc.

The new method inserts numbers with zeroes like this:

19999999999
20000000000
22000000000
22200000000
22220000000
22222000000
22222200000
22222220000
22222222000
22222222200
22222222220
22222222222
22222222223
22222222224
etc.

Incorporating the pre-computation method was a bit tricky, as it requires storing those values for later recall. The most natural registers to store them would be 0 through 9, so that the digit value could point to the register containing that digit to the Nth power. But all of my prior versions stored the digits of my input numbers in register 1 through 11, so I chose to store the values of 0^N, 1^N, …9^N in registers 20 through 29. This requires adding 20 to the recalled digit value before indirectly recalling the appropriate d^N value to create the sum. I was able to handle this, and the latest version is indeed the quickest yet. Using Free42 on my laptop PC, this latest version completes the task in approximately 35.6 seconds, compared to 51.7 seconds for the prior version, an approximate 30% decrease in execution time. On my DM42, the timings are 35 minutes and 57 seconds for the latest version vs. 51 minutes and 40 seconds for the prior version, also essentially a 30% reduction.

On a desktop PC that I also use at times, I get anomalous results. Initially, the timings were 12.9 seconds vs. 11.7 seconds. Then that PC received a Windows update, and now Free42 runs much more slowly. And, oddly enough, the new version is actually slower than the prior version, 49.9 seconds vs. 48.5 seconds. I am running the same version of Free42 on both PCs (the decimal version of 2.5.11), so I don't know why the timings are not consistent on one PC vs. the other, nor why the windows update would slow Free42 down by a factor of 4.

For timing results, I guess I put the most faith in the DM42 results, so I believe that the method is demonstrably faster. Below is the program listing, and a zipped raw file is attached. I'd be interested in seeing timings using Free42 in other platforms if anyone has the time or inclination.

000 { 212-Byte Prgm }
001 LBL "Σd↑n"_____
002 FIX 00_________ Fix 0 to eliminate zeroes after decimal for integers
003 CF 29__________ clear flag 29 to eliminate radix symbol display for integers, else it would get copied to alpha register
004 20_____________ Steps 4 through 9 clear registers 1 through 20 (need to clear 20 for 0^N for all N's, not done in subroutine)
005 0______________
006 LBL 01_________
007 STO IND ST Y___
008 DSE ST Y_______
009 GTO 01_________
010 1______________
011 STO 01_________ initialize register 1 to 1
012 XEQ 12_________ execute subroutine to calculate 1^N….9^N for N=1
013 GTO 98_________ go to label to calculate sum d^N for 1
014 LBL 02_________ Label 02, begin main routine
015 RCL 01_________ recall rightmost digit
016 X=0?___________ is it zero?
017 GTO 99_________ if so, prior number had trailing zero(es), go to routine to copy latest incremented number down to next lower register
018 1.011__________ Store 1.011...
019 STO 00_________ ...for ISG to check digits
020 LBL 03_________ Label 3, check digits to see if they equal 9
021 9______________ Enter 9
022 RCL IND 00_____ recall digit
023 X≠Y?___________ is it not equal 9?
024 GTO 04_________ if not, go to routine to increment
025 ISG 00_________ if equal to 9, increment counter to…
026 GTO 03_________ ...loop back to check next digit
027 STOP___________ if register 11 equal 9, all unique combinations up to 99,999,999,999 have been checked
028 LBL 04_________ routine to increment registers
029 RCL 12_________ recall number of digits
030 RCL 00_________ recall loop counter, which has counted up to register number containing first non-9 digit
031 IP_____________ take integer part
032 STO 19_________ store for use in storing new incremented values in lower registers
033 STO 19_________ store back in register zero without .011 rarget for use as DSE later
034 X>Y?___________ is register in which first non-9 found greater than current number of digits?
035 XEQ 12_________ if so, new number of digits established, go to subroutine to calculate 1^N, 2^N,…9^N
036 1______________ enter 1
037 STO+ IND 00____ add one to register in which first non-9 found
038 DSE 00_________ decrement register 0
039 DEG____________ no operation
040 0______________ enter 0
041 LBL 05_________ label for loop to store zeroes in registers N-1 to 1
042 STO IND 00_____ store zero
043 DSE 00_________ decrement register zero
044 GTO 05_________ loop back to store next zero
045 GTO 98_________ go to label to calculate sum d^N
046 LBL 99_________ label to store incremented value in lower registers after storing zeroes
047 RCL IND 19_____ recall new incremented value
048 DSE 19_________ decrement loop counter
049 STO IND 19_____ store new incremented value in next lower register
050 LBL 98_________ label to calculate sum d^N
051 RCL 12_________ recall current number of digits
052 0______________ enter zero
053 LBL 09_________ loop label for summing d^N
054 20_____________ enter 20
055 RCL+ IND ST Z__ add to value of digit in register N, N-1,…1
056 RCL IND ST X___ recall value in register 20 + the value of the digit
057 RCL+ ST Z______ add to running sum
058 R↑_____________ roll up…
059 X<>Y___________ … and swap to get stack in proper order
060 DSE ST Y_______ decrement register containing N, N-1…1
061 GTO 09_________ loop back to recall and sum next d^N
062 STO 14_________ store sum d^N in register 14
063 CLA____________ clear the alpha register
064 ARCL 14________ copy sum d^N into alpha register
065 ALENG__________ length of alpha register equals how many digits in number
066 RCL 12_________ recall current number of digits
067 X≠Y?___________ digits in original not equal digits in sum d^N?
068 GTO 02_________ if not equal, cannot be selfie, skip all checks
069 RCL 14_________ if equal, recall sum d^N
070 +/-____________ negate
071 LBL 08_________ Label for loop to sum d^N of sum d^N of input number
072 ATOX___________ move char# of leftmost digit of sum d^N into X
073 X=0?___________ is it zero?
074 GTO 11_________ if zero, all digits shifted out, go to label to see if sum d^N of sum d^N equals original sum d^N
075 28_____________ if not zero…
076 -______________ ...subtract 28 to convert char# to actual digit plus 20
077 RCL IND ST X___ recall d^N of value of digit
078 RCL+ ST Z______ add to negated sum d^N
079 GTO 08_________ loop back to recall next digit
080 LBL 11_________ Label to see if sum d^N of sum d^N equals original sum d^N
081 X≠Y?___________ zero will be in x, if sum d^N of sum d^N equals original sum d^N, zero will be in y
082 GTO 02_________ if not equal, cannot be selfie, go back to create and check next number
083 RCL 14_________ recall sum d^N
084 10_____________ enter 10
085 MOD____________ determine rightmost digit
086 X=0?___________ is FP zero, i.e., was rightmost digit zero?
087 GTO 02_________ if so, cannot be selfie since reverse will be fewer digits, skip all checks
088 RCL 14_________ if not, recall sum d^N, steps 88 through 99 reverse the digits in the number to produce selfie
089 STO- 14________ store in reg 14 to clear it.
090 LBL 16_________ label for loop to reverse digits
091 FP_____________ take fractional part
092 STO+ 14________ add to register holding reversed sum d^N
093 LASTX__________ recall input number
094 IP_____________ take integer part
095 0.1____________ enter 0.1
096 STO÷ 14________ divide current reversed number by 0.1 to shift left one digit
097 ×______________ multiply input number by 0.1 to shift one digit right
098 X≠0?___________ is input number not zero, indicating more digits to shift?
099 GTO 16_________ if not zero, loop back to shift and add again
100 RCL 14_________ if zero, number has been reversed, recall reversed sum d^N
101 PRX____________ print number for which d…d=reverse of sum d^N
102 GTO 02_________
103 LBL 12_________ Subroutine to calculate 1^N, 2^N,...9^N and store in registers 21 through 29
104 STO 12_________ store new N
105 9______________ enter 9 for DSE loop
106 LBL 13_________
107 RCL ST X_______ duplicate X register
108 RCL 12_________ recall number of digits
109 Y↑X____________ raise 0…9 to Nth power
110 20_____________ enter 20
111 RCL+ ST Z______ add to 0…9
112 X<>Y___________ swap
113 STO IND ST Y___ store d^N in register 20+d
114 RCL ST Z_______ recall current digit
115 DSE ST X_______ decrement
116 GTO 13_________ loop back to calculate next
117 RTN____________ subroutine return
118 END____________


edits - revised program now three steps shorter, added commented program listing, fixed a mistake, clarified some things.