Search
Member List
Calendar
Help
HP Forums
/
HP Calculators (and very old HP Computers)
/
General Forum 
/
Tripartite Palindromic Partition of Integer (HP 50g) Challenge
/
Tripartite Palindromic Partition of Integer (HP 50g) Challenge
|
Tripartite Palindromic Partition of Integer (HP 50g) Challenge
|
|
05-25-2023, 11:19 PM
Post: #121
|
|||
|
|||
|
RE: Tripartite Palindromic Partition of Integer (HP 50g) Challenge
For the final one among the subroutines for "short" / "small" numbers I'm using a pair of small helpers. They are principally built for the main algorithms, so you'll see them again there, but as they are generic enough, I was able to use them for AlgS6.
BINTmod is mostly a wrapper around the builtin command #/ for the places where only the remainder of a division by \(g\) is needed. As such, it is roughly equivalent to the \(D(n)\) notation in the proof, except I try optimize it out. As part of the wrapper, \(g\) is recalled from its LAM1, and there's an additional quirk: before dividing, I add \(2\cdot g\) onto the dividend. This seems useless, especially because the quotient is DROPped at the end. But it has a purpose: the parameter can go a bit below \(0\) without unsigned division ruining the day. Placing the remedy into this shared helper may hurt performance a little bit in cases where it's not needed but in the limited memory of all RPL machines code size is generally more important. computeCarryAndRem performs a somewhat more complex operation. It takes two parameters from the stack and adds them together (because it generally operates on a sum, so I'm sharing the #+ by shoving it in here). This sum is the sum of two palindromes' digits which line up under each other, plus (if applicable) any incoming carry. Then it uses a callback to fetch the digit of the input number which they and the third palindrome's corresponding digit have to add up to, and calculates that missing digit. As a highly useful byproduct, the outgoing carry is generated as well. This helper is kind of optimistic: most of its code is built as if determining the missing digit is a matter of simply subtracting the input digit from the remainder of the division that splits off the outgoing carry. However, just before the subtraction happens, it examines if that would result in a negative number; if so, carry and remainder are adjusted accordingly. As mentioned in fromZINT, computeCarryAndRem is stored in LAM2 instead of being available via ROMPTR. This has a notable side effect: 2GETEVAL is implemented in ROM as :: 2GETLAM EVAL ; - note the EVAL where I would like to see a COLA_EVAL. Since computeCarryAndRem takes a callback from the caller's runstream, I need to RDROP the extra return stack level pointing to right behind the EVAL inside 2GETEVAL. Then I can reach the runstream which called 2GETEVAL, and grab the callback from there. If computeCarryAndRem wasn't called via 2GETEVAL everywhere, this RDROP would likely do unwanted things. I felt the need to place one of my rare code comments here so I wouldn't forget about it in case I gave the LAM2 slot to another helper. Code: LABEL BINTmod.sCode: LABEL computeCarryAndRem.sTo those who followed the thread throughout the challenge, the template with the pair of 5-digit palindromes may seem somewhat familiar as Albert Chan's sketches are also based on a pair of odd-length palindromes accompanied by a shorter one. The proof's authors apparently found a number of edge cases which require adjustments or other templates altogether; I can't tell whether that is due to inherent limitations of this template or a consequence of the short length of numbers - because that's clearly what keeps the proof's arbitrary-length algorithms from being used on these. The digits of the 5-digit palindromes are calculated in pairs, each from a sum they need to add up to, and for the pair made up by the outermost digits of both palindromes, an additional requirement that neither may be \(0\) (for obvious reasons). Other than this, the proof gives freedom of choice to the implementation - one of only two places it does so. (The other one is located in pickType.) I previously suggested splitting the sum by integer division by 2 (with the remainder getting added onto one of the halves), but in the end I use that choice only for the third pair (representing the central digit of each 5-digit palindrome). The other pairs have in common (across all cases) that their sums consist of a digit from the input number and a constant, and it turned out to be slightly better to use these components more or less directly as members of the pair. The constants are generally \(0\) or \(g-1\), even - that makes it easy to keep the pairs (and by extension, the palindromes) sorted by magnitude, as they are the extreme values a digit can take. The constants can be simply allocated to one of the slots in the pair with no danger of getting the order wrong. There are three situations where this procedure leads to problems the integer division procedure would dodge without any effort: - In case iv.a the constant for the second pair is \(-1\), i.e. not a valid digit. The way to avoid it is decrementing the variable digit and setting the constant one to \(0\). - In cases i, ii, and iii (other iii.d and the special case in iii.c, which both abandon the template) the first pair is not allowed to contain a \(0\), so if the variable digit is \(0\), it is incremented to \(1\) and the constant decremented to \(g-2\) instead. - In case iv.a, the constant for the first pair is \(g\), i.e. not a valid digit (again). You can likely guess that can be resolved: increment the digit, and decrement the constant to \(g-1\). This would also avoid the previous problem with a \(0\) in the first pair. However, my implementation happens to have access to the values chosen for i, ii, and iii, so it recycles them by incrementing the variable digit and retaining the constant. If the input digit was \(0\), it is therefore double-incremented to \(2\) and the constant will be \(g-2\). Why are these corrections worth passing up the easy path of integer division by 2? For one, cases iii.a, iii.b, and iii.c reduce the freedom of choice and explicitly set the first pair to values that match this procedure's result but don't match the integer division's. (Mathematically, either of them works out but I want to match the proof's results as closely as I can.) The other incentive is that in cases iv and v the input digit used for this pair (\(\delta_4\)) is needed for extra checks - with the integer division, it would need to be reconstructed (by adding the pair back together and subtracting the constant away again) or retained (leading to a superfluous value for other cases that needs to be disposed of). With the procedure I'm using, the decision between iv and v can reuse the pair member already on the stack, because even though the correction obscures the difference between \(\delta_4=0\) and \(\delta_4=1\), it's irrelevant there. Inside v, I bite the bullet and reconstruct \(\delta_4\) from the sum. Regarding the case hierarchy, i is the default case, with a 3-digit palindrome as the third one. Cases ii and iii take care of some minor concerns that come up when the sum of the first pair forces the third palindrome's last digit (and by extension, first digit) to be \(g-1\). (Actually, ii with its extra condition \(\delta_2\ne 0\) distinguishing it from iii essentially says: problems avoided, fall back to i. It's just iii that is deviating, with different sums for the second and third pairs and a 4-digit third palindrome.) iv and v are the cases where the third palindrome's last digit comes out as \(0\) (which obviously isn't allowed there, just like in the first pair). iv.a saves what it can and still manages to apply the same template with some minor adjustments to the pair sums. With all this, it makes sense to share as much as possible of the code constructing this template across all branches. Additionally, since the outermost digit of the third palindrome is so central for the decision which branch to take, I'm optimistically calculating it and the first pair (which it more or less depends on), and only then I use copies of it to find out which case applies. After the dispatching is done via an assortment of nested conditions, the construction of palindromes according to i resumes. ii and even iv.a use the same code, but iii.a, iii.b, and iii.c need to skip part of it (quite literally, with the SKIP command), so that part is wrapped in a secondary. (The comment after that is slightly wrong, it should mention iv.a instead of all of iv. Why do I keep discovering mistakes like that after I'm officially done?) That's most of the code dealing with a pair of 5-digit palindromes explained. The only piece left is inside iii, but there's not much to it. In iii.a, iii.b, and iii.c, the formulae for the palindromes' digits change due to switching to a 4-digit third palindrome, but the procedure is equivalent to what the corresponding piece of cases i, ii, and iv.a does (which is the part that gets SKIPped): it calculates the second pair for the 5-digit palindromes, from there the third palindrome is completed and bundled up into a list, and the sum of the last pair of digits is prepared. The special case \(c_2=2\) in iii.c appears as if it is present for iii.a and iii.b as well, because these three cases share all their code, but with the input digits that lead to those cases, \(c_2\) can't ever be \(2\). That's why I can place that special case there without specifically checking for iii.c. As should be a familiar ritual by now, that special case and iii.d both get rid of the shared code for the pair of 5-digit palindromes waiting in the return stack via RDROP. The special case is for a single digit combination, so it clears almost everything off the stack and constructs the correct palindromes. (A \(g-1\) is recycled, that's all.) iii.d has some superficial similarity to iv.b, v.d, and v.e with palindromes of length 6, 5, and 3, but due to all the differences and iii.d being out of place (on the wrong branch of the overall dispatcher), I found that it's not worth trying to share code. Instead I just roughly followed the proof's order of which values to calculate: \(c_4\) comes first, then \(c_2\) and \(z\) together. In the process, the value \(1-c_4\) is more useful to hold onto than \(c_4\) by itself (and once it's calculated, the whole first palindrome is done and dusted). The \(c_2\) and \(z\) happen to line up with what computeCarryAndRem can calculate. The rest of the case's code is simple enough to not need extra explanation, I think. Now, onward to iv and v. As one of the branches in the top-level ITE, this branch sits in its own secondary, and its two cases are distinguished by another ITE. There's some shared code responsible for a good chunk of the headache-inducing template after it - iv.a avoids it with an RDROP in its branch so it falls back to the pair-of-5-digit-palindromes code again. When that shared code does get run, however, it returns the favor with an RDROP of its own, which tosses the pair-of-5-digit-palindromes code off the return stack. Let's leave that headache for last, though, because in v.a, v.b, and v.c the old template based on subAsZINTthenAlgS reappears. Much like the first attempt in AlgS5 it splits off a palindrome starting with the same two digits as the input number. However, due to the conditions for reaching this template, the "failure" cases get handled (mostly) individually, instead of a second attempt. This leads to a very differently shaped code, consisting of my take on a C-style switch() statement, as seen before in fromZINT: a list of secondaries, accessed by NTHELCOMP. The "default" case is v.d and v.e together, representing the not-yet-discussed template. The secondaries in the list correspond to one each of the cases v.a, v.b, and v.c. As members of one template, these cases share much of their code (most importantly, the subAsZINTThenAlgS call), which I lumped with the EVAL running the secondaries. There's also 2RDROP in there, tossing the return stack entries for shared code of both competing templates in one stroke. These secondaries themselves return the last digit of the input number, as required by the conditions needed to reach this template. This is needed because the digit is used up while checking the conditions, and I can't do much about that without disrupting the code for the pair-of-5-digit-palindromes template. The secondaries also handle all the nameless special cases, with two exceptions: those which are just redundant examples for the shared subAsZINTThenAlgS code (recognizable by their first palindrome; the proof merely lists them explicitly because its authors apparently want to keep the conditions for recursing into lesser AlgS subroutines simple), and the single special case where subAsZINTthenAlgS returns a 3-palindrome result (\((g-1)(g-2)=(g-2)(g-2)+(g-1)+1\)). The latter is from v.a but since it's easier to catch after the subAsZINTthenAlgS call, it's handled in the shared code. The special cases make for bulky but not interesting code. Note that there are some among them which could mathematically be allowed into subAsZINTthenAlgS (namely \(110100\) from v.b as well as \(120101\), \(120111\), and \(120021\) from v.c), but the proof expands them into different palindromes. As usual, I replicated the proof's results exactly instead of going for shorter code - otherwise I could have reduced the special cases in v.b and v.c to two each: \(1100010\) and \(110000\) as well as \(120011\) and \(120001\). Note that even though the number subAsZINTthenAlgS subtracts from the shortened input number consists of two digits again, I can get away with BINTs instead of the ZINT trickery used in AlgS5Callback. This is because this time the higher digit is at most \(2\) (in v.c, to be precise), and \(21=2\cdot g+1\) still fits into a BINT even when \(g\) is 9999. For the headache-inducing template (which, by the way, doesn't even exist in version 1 of the proof; that's one of the big gaps fixed by version 2), I was practically forced to trim down the formulae for the digits and/or replace them entirely with alternatives which yield the same results. The first target is obviously the intermediate value \(y\), which is entirely dependent on \(\delta_1\). The next one is \(c_2\), which is also entirely dependent on \(delta_1\), but it's harder to spot that because part of this dependence is indirect via \(y\). There's also a cluster of typos in this area. You'll see them if you recall that \(c_1\) is an ordinary carry. iv.b gets away without typos, but in v.d the definition of \(c_1\) given below the figure doesn't match the digits in the corresponding column in the figure, which are: \[(1\text{ (incoming carry)}\\+0\text{ (first palindrome's digit)}\\+(y-c_2+1+c_1)\text{ (second palindrome's digit)}\\+(D(\delta_1-1-y)+(c_2-1)-c_1)\text{ (third palindrome's digit)}\\-\delta_1\text{ (remainder of division = input digit)}\\)/g\]That simplifies to \(c_1=(1+y+D(d_1-1-y)-\delta_1)/g\); note the discrepancy in the constant, where I get a \(1\) and the proof's definition has a \(2\). This is fortunately inconsequential if we do the sensible thing and treat the division symbol as integer division, because the difference will just result in a discarded remainder of \(1\) instead of the \(0\) which the proof usually aims for by subtracting the input digit \(\delta_1\) (the expected and desired remainder) beforehand. You'll only run into trouble if you skip this normally superfluous subtraction and receive \(g-1\) as input digit - that would combine with this typo's offset into \(g\), which is just enough to survive the implicit floor() part of integer division. In case v.e the situation is even more serious. This time there is a typo in the equivalent spot but the other way around, another inside the \(D(\text{...})\) part of the definition, and a third in the definition of \(y\). In all three places there is a \(1\) where a \(2\) should be. Since this is the other way around from v.d, the first of these three by itself would be catastrophic (wrapping the remainder around to \(g-1\) and decrementing the quotient), but the second one mostly compensates for that. There's a slight concern left about the values of \(\delta_1\) and \(y\) that cause \(D(\text{...})\) to wrap around to \(g-1\), but that's where the third typo in the definition of \(y\) makes that combination of values trivially impossible. That leaves up for debate what consequences this wrong value for \(y\) has elsewhere, and the answer is: not much. It alters all non-constant digits in the palindromes, but it doesn't break anything: the definition of \(y\) is obviously intended to ensure that \(D(\delta_1-2-y)\) isn't at the lower or upper end of the valid digits range (so that the difference between \(c_2\) and \(c_1\) doesn't cause the third palindrome's middle digit to go out of range), and now it can be \(0\) if \(\delta_1=3\). That input value causes \(y=1\) due to the third typo, but luckily these values cause \(c_1\) to be \(0\) as well, avoiding the possibility of an invalid digit. Crisis averted, but the proof by itself has a gaping hole in its logic. These typos were supposed to be circumvented in my implementation, but I didn't manage that completely - the wrong \(y\) in v.e remains. Between the typos, this implementation quirk, and the general complexity of this template's formulae, the resulting optimized code is pretty much unreadable to anyone except myself as its author, and even I am having trouble understanding it as I'm revisiting it while writing this. Therefore I'll give a stack diagram at a pivotal point in the code, as well as a bunch of alternative formulae for important values - I cooked those up while coding, and they are supposed to line up better for optimized implementation (though they are not suitable for use in the proof's conclusions, so I get why it uses the formulae it does). Both branches of this template - v.d and v.e are handled by mostly the same code in one branch, iv.b is the other branch - start from a clean slate with only the still-relevant input digits on the stack. That is, \(\delta_1\) is in level 3, \(\delta_2\) in level 2, and either \(\delta_3\) (for iv.b) or \(\delta_4\) (for v.d and v.e) in level 1. The iv.b branch needs a 4DROP to make it so, for the other branch this is already the state of the stack on entry. Both branches then proceed to compute the two values dependent on \(\delta_1\) only - that's the first ITE in both. For v.d and v.e it actually computes \(y+c_1\) and \(c_1\), because in the palindrome digit I derive from \(y\), that branch needs \(c_1\) added on top of it. iv.b uses \(y\) by itself in that digit's formula, but it generates \(1+c_1\) in place of just \(c_1\). (iv.b additionally defines a value nearby called \(x\), but my code postpones computing that until it's needed.) The formulae used are: - for iv.b, \(y=\begin{cases}1&\text{if }\delta_1=0\\\delta_1&\text{if }1<\delta_1<4\\1&\text{otherwise}\end{cases}\) and \(c_1=\begin{cases}1&\text{if }\delta_1<4\\0&\text{otherwise}\end{cases}\) - for v.d and v.e, \(y=\begin{cases}\delta_1+1&\text{if }\delta_1<3\\0&\text{otherwise}\end{cases}\) and \(c_1=\begin{cases}1&\text{if }\delta_1<3\\0&\text{otherwise}\end{cases}\) You can see how nicely the conditions for both values computed in one branch line up with each other, making it possible to generate both values in the same ITE. That's not surprising if you know that an intermediate step in the transformation process looks like \(c_1=\begin{cases}1&\text{if }\delta_1<k+y\\0&\text{otherwise}\end{cases}\) (with \(k=3\) for iv.b, \(k=1\) for v.d and v.e), and from there you can try out all the branches of my \(y\) definition and plug input / output pairs into this one to find out that the "otherwise" branches line up. If I had paid enough attention to typo correction, the formulae for v.e would have lined up more with iv.b from the other branch than its partner v.d. (For \(y\) that's obvious from the proof's definitions, for \(c_1\) you'd have to set \(k=2\) in the intermediate equation and conclude that it's indistinguishable from \(k=3\).) That would have resulted in a very different implementation, due to different optimization opportunities. I may fix it in the future, but as the analysis above shows, the resulting palindromes are still valid. I can also claim that it matches the proof's results, as "wrong" as they may be. The next values calculated are a trio of easily calculated final palindrome digits: the one between the first palindrome's outermost and central digits (\(x_2\) in the terminology seen in the proof's description of the pair-of-5-digit-palindromes template and in the long-number algorithms), and the outermost digit of the other palindromes (i.e. \(y_1\) and \(z_1\)). In iv.b the latter two are constants, and the former has one of two values (\(3\) or \(2\)) depending on \(c_3\). That in turn boils down to a simple ITE as it is: \(c_3=\begin{cases}1&\text{if }\delta_3<y\\0&\text{otherwise}\end{cases}\) In the other branch the paths for cases v.d and v.e finally diverge. v.d is essentially implemented as an "error-handler" for when v.e finds that its value for the second palindrome's outermost digit \(\delta_4-3\) is \(0\) (i.e. invalid in that position). In v.e the other two values are constants - and in v.d all of them are constants too, but with different values (I manage to recycle two values, a constant \(2\) and \(\delta_4-3=0\), by shuffling them to other constant slots). I also set a value \(x_2-c_0\) which is in most cases a duplicate of \(x_2\), except in v.d which has constant values that result in a carry \(c_0=1\) from the last column of palindrome digits. v.e's value for that is the \(2\) that gets recycled in v.d. In addition to the constant shuffling and the carry from the palindromes' outermost digits, v.d alters \(y+c_1\) to \(y+c_1+1\). In the digit formulae this \(+1\) is meant to counter the shifted value range of \(c_2\) compared to what that intermediate variable evaluates to in v.e, so I ought to adjust that. However, with the selection of numbers I compute via the proof's formulae or my alternative versions (the rest I hand off to BINTmod or computeCarryAndRem instead), it turned out to be easier to attach the \(+1\) to this intermediate value. As the final steps before dropping into the code shared among all three cases, \(z_1+c_1\) is prepared (iv.b has no need for this as in that case \(z_1\) is always \(1\) and it computed \(1+c_1\) instead of \(c_1\) ahead of time), and \(\delta_3\) is brought to stack level 1. In the branch covering v.d and v.e that's a constant \(0\). On entering the shared code the stack therefore contains: 9: \(\delta_1\) 8: \(\delta_2\) 7: \(z_1+c_1\) 6: \(y\) for iv.b, \(y+c_1+1\) for v.d, or \(y+c_1\) for v.e; in other words, \(y_2+c_2\) 5: \(z_1\) 4: \(x_2+c_0\) 3: \(y_1\) 2: \(x_2\) 1: \(\delta_3\) The order looks jumbled, and it kind of is, but that's the most efficient one I could find. The shared code uses these up to compute the remaining values and eventually bundle up the finished palindromes. It gets started with \(x_3\), and if you account for the \(x\) definition in iv.b and the proof's simplification of \(D(0-\text{...})\) to \(g-\text{...}\) in the \(x_3\) formula, that's straightforward with BINTmod. A copy of \(x_3\) then goes into computing \(y_3\) with computeCarryAndRem. That also drops \(c_2\) into my lap without having to bother with any additional formula. Now is the moment to start caring about the \(\mu\) adjustment for iv.b, which I completely ignored up to this point because it reacts to \(c_2=2\). Since we're in the shared code now, that needs to be sorted out cleanly; \(c_2=2\) can also occur in v.d, so I augment the condition for the IT with a check that is true for iv.b but false for v.d. I settled on \(z_1=1\) which is also true for v.e, but that's irrelevant because that case cannot generate \(c_2=2\). The correction itself decrements \(x_3\) and sets both \(c_2\) (or more correctly, \(c_2-\mu\)) and \(y_3\) to \(0\). From here, everything else goes downhill: \(y_2\) comes out of subtracting now-known \(c_2\) from the \(y\)-based value calculated long in advance, then \(z_2\) combines several numbers with BINTmod. Finally, a bit of stackrobatics mixed with {}N variants package the digits into palindromes. Note that I didn't mention \(x_1\) at all; it's always \(1\) across all three cases, so it can be set while bundling up the first palindrome. If I release an updated version, I'll make sure to include an additional comment or two to note the variables on the stack and their order, because this template is the one section where even I, the author of the whole shebang, couldn't fully reconstruct the data flow from memory and pure brain power. I had to write stuff down, and I hate doing that. Code: LABEL AlgS6.s |
|||
|
|
« Next Oldest | Next Newest »
|
User(s) browsing this thread: 1 Guest(s)