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

11232019, 10:17 PM
(This post was last modified: 12012019 06:17 PM by Jeff O..)
Post: #50




RE: [VA] Short & Sweet Math Challenges #23: "May the 4th Be With You !" ...
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 precompute 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 precomputed value of 5^8 if there is a 5 in the 8digit 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 precomputing 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 onedigit numbers, then all twodigit numbers (including those with one trailing zero), then all threedigit (including those with one or two trailing zeroes), etc., on up to all 11 digit numbers. This would enable me to precompute 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 precomputation 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 { 212Byte 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 non9 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 non9 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 non9 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 N1 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, N1,…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, N1…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. Dave  My mind is going  I can feel it. 

« Next Oldest  Next Newest »

User(s) browsing this thread: 1 Guest(s)