Puzzle  RPL and others

05032021, 03:43 PM
Post: #24




RE: Puzzle  RPL and others
After I theorycrafted this scheme of sorting baseN digits into buckets based on their GCD with the base (this is what the divisibility stuff boils down to, I just failed to realize that earlier)... I couldn't resist the temptation to try and implement it. Yes, I'm jumping past the odd/even and ==base/2 checking stages, but the way I baked it into my program should make the recursive subroutine faster in all situations than with those two simple tests, even in situations like bases 6 and 8 where my buckets match up perfectly with those tests, thanks to bitset juggling and the fact I already have a bitset check in there.
Code: :: The goal was to make the check for whether a digit is in the right bucket for the currently processed place as quick as I could: another bitset, which gets ANDed into the bitset of notyettaken digits before the digittesting loop in the recursive subroutine starts. (My previous programs used a bitset of alreadytaken digits, but that's just an inversion away.) The preprocessing that goes into constructing the bucket bitsets is pretty quick too, since it doesn't use many loops or particularly slow commands, and especially not recursively nested loops. This new part is just a loop over all valid digits taking the GCD between it and the base, using an indefinite loop for a custom BINT version of the Euclidean Algorithm (since I didn't want slow backandforth conversion to a slower type which would likely also use that algoithm in ROM). With this GCD a list is recalled, the digit appended to it, a bitset at the end of the list updated by ORing the digit's singlebit bitset into it, and the resulting list stored back. A separate loop over the GCDs (actually over all digits, but everything that doesn't have a list gets ignored) and distributes the finished bitset to the digits in the list. This reuses the same local variables for lists and extracted bitsets, but I made sure that's safe. If I comment out the part that sets up the three parameters for the outermost recursive subroutine call along with the call itself (i.e. leaving only this new setup part and the small setup which existed before), the time spent is around 0.16_s for bases 22 and 24 (the highest bases I tried so far). Compare that to how long the recursive part took: 150_s for base 24, which benefits greatly from all that bucketsorting, and a staggering 1304_s (over 21 minutes!) for base 22, which does not benefit from it at all beyond the simple odd/even and ==base/2 checks. Good ol' base 10 takes just under 2.5 seconds. Other changes include switching the types employed for the underconstruction number and bitsets from reals and BINTs to ZINTs and HXSs, respectively. ZINTs slow things down, but reals broke down partially in base 13 and fully in base 14 and beyond (because they only hold 12 decimal digits), and extended reals push this limit up by only 3. So infiniteprecision integers are the way to go; I don't need a fractional part anyway. Similarly, BINTs have only 20 bits, so they only work as bitsets up to base 21; HXSs are theoretically infinite (though the ROM math routines only support up to 64 bits), but also slower. Still, slow results is better than wrong results  base 65 is the upper limit now. Without these type changes base 10 was in the neighborhood of 1 second. Oh, and I added an early exit in basically constant time for odd bases. No point checking those anymore, just return no results immediately.  While climbing the ladder up to base 24, I also noticed that quite a few of the bigger even bases don't have solutions either. Assuming my code is correct, these are the solutions by base:  2: \(1_2 = 1_{10}\)  4: \(123_2 = 27_{10}, 321_2 = 57_{10}\)  6: \(14325_6 = 2285_{10}, 54321_6 = 7465_{10}\)  8: \(3254167_8 = 874615_{10}, 5234761_8 = 1391089_{10}, 5674321_8 = 1538257_{10}\)  10: \(381654729_{10}\), the original puzzle target  12: nothing  14: \(9C3A5476B812D_{14} = 559922224824157_{10}\)  16 to 24: nothing I would have liked to dump some Babylonian numerals on you eventually (base 60), but I don't think that's going to happen if I look at the TEVAL reports for 22 and 24. The preprocessing isn't too bad (without the recursive subroutine I measured it to take 0.44 seconds for base 60), but 60 levels of recursion with a loop in each surely is just asking too much from a tortured little pocket calculator. We'd need more shortcuts to make that even remotely feasible. 

« Next Oldest  Next Newest »

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