Short & Sweet Math Challenges for HP fans #2 - Printable Version +- HP Forums (https://archived.hpcalc.org/museumforum) +-- Forum: HP Museum Forums (https://archived.hpcalc.org/museumforum/forum-1.html) +--- Forum: Old HP Forum Archives (https://archived.hpcalc.org/museumforum/forum-2.html) +--- Thread: Short & Sweet Math Challenges for HP fans #2 (/thread-18067.html) |
Short & Sweet Math Challenges for HP fans #2 - Ex-PPC member - 06-01-2002 Thanks to all of you who were interested in the very first S&SMC, posted
Last week's challenge (the one about the tangents), was mostly theoretical
All in all, it was a rather theoretical (if interesting) challenge, so in order
Give it a chance, refrain from the temptation to use a pc, and let us all see how you and your HP cope with this challenge ! Re: Short & Sweet Math Challenges for HP fans #2 - John Ioannidis - 06-02-2002 Several observations:
Now for some solutions:
Re: Short & Sweet Math Challenges for HP fans #2 - Ex-PPC member - 06-05-2002 Hi Mr. Ioannidis,
It seems that this week's challenge hasn't catch the Mr. Ioannidis: "The maximum and the mimimum solutions have the same absolute value (you get one by exchanging two rows or two columns of the other). Hence, we are only going to consider as solution the absolute value of the determinant."
That's exactly what I said in my description of the
Mr. Ioannidis: "The lowest solution is obviously 0"
Wrong. In my description of the challenge you can read:
Mr. Ioannidis: "The really hard part is generating the permutations; it gets harder on HP calculators because you can't use a recursive algorithm and have to unwind the
Wrong again. At least one model does allow recursion:
While this is of course correct, remember I pleaded:
While I'm grateful to you for your interest in the challenge Let's hope that, before the week elapses, some other kind contributors of this forum will shed some light on the solutions for the minimum 3x3 determinant, and the maximum and minimum 4x4 determinant. Seeing some code for any HP calculator would be great ! And finding a theoretical expression for arbitrary NxN determinants would be eidetic.
So I repeat: put aside you fancy PC at 2 Ghz and let your 71B, your 42S or your 49 do the job, Ok ? :-)
Re: Short & Sweet Math Challenges for HP fans #2 - Thibaut.be - 06-06-2002 Well, I have to admit that in order to apply to this challenge I had to go back to my old maths books.
I love those quizzes, but I propose that you lower a bit the level of the questions, I guess you'd get more answers...
Re: Short & Sweet Math Challenges for HP fans #2 - Chris Randle (UK) - 06-06-2002 At least one model does allow recursion: HP-71B BASIC language allows subprograms and user-defined functions (single-line and multi-line) to call themselves, so permitting recursion naturally All RPL machines can have programs that call themselves too. If you have a program called FAC to calculate a factorial, then:
<< -> n << IF n 1 == THEN 1 ELSE n 1 - FAC n * END >> >> works quite nicely with FAC(n) calling FAC(n-1) * n, etc. Tried it on a 28S. I know the "IF n 1 ==" can be replaced by "IF n", but I thought the intent was clearer.
I'm going to have a go at your puzzle now, instead of doing the work I'm paid for ;-) I love puzzles like these for little machines. Thanks for posting them.
Recursion in HP calcs - Andrés C. Rodríguez (Argentina) - 06-06-2002 I would just say that the HP 41 programming model (hence including the HP 41C/CV/CX and HP 42S calculators) allow for recursion at the user programs level.
Re: Recursion in HP calcs - John K. (US) - 06-06-2002 [T]the HP 41 programming model [...] allow for recursion at the user programs level.
Unfortunately, due to the limitations one calling chain depth, this ability is somewhat limited. One of the programming projects I was working on many, many moons ago was a routine to copy out the return address registers in the 41 to the main storage registers and back again to seemlessly allow for longer calling chains. I don't think I ever got it working quite right and, since it was (obviously) filled with synthetic commands, it won't work on a 42S. Still, it might be interesting to see if I still have a copy of it somewhere...
Re: Recursion in HP calcs - Andrés C. Rodríguez (Argentina) - 06-07-2002 You are right, I should have said that "...the 41 programming model allow for limited recursion"
Re: Recursion in HP calcs - Paul Brogger - 06-07-2002 If one kept one's own "call/return stack" in user memory in the form of codes indicating what was called and where to return, couldn't one simply use GTO rather than XEQ/RTN (or equivalents)? That should extend the depth of the call/return stack greatly. (Especially in, say, a 32K 42s or a 48/49.)
Re: Recursion in HP calcs - Thibaut.be - 06-07-2002 XEQ <lbl> or GTO <lbl> are exactly the same, aren't they ?
Re: Recursion in HP Calcs - Paul Brogger - 06-07-2002 Details, details! Actually, that may betray how little I actually am engaged now in programming the things. On my -32s (and presumably the -32sii) I believe that XEQ means "GOSUB" (call with return) and GTO means "GOTO" (go there without expectation of return). If I've got it right, the first enters a return address on the internal return stack, while the latter doesn't. My HP-48G doesn't seem to have a GOTO, but perhaps I haven't looked closely enough. Regardless, one or more recursive routines could be broken into segments and sequenced through codes passed to special "Call" and "Return" subroutines. (Without a GOTO, it would just be a little more work.) Of course, any variables whose values need to be maintained across such a recursive call would need to be maintained by the programmer on a stack as well. As with any actual implementation, there would be an real (if not a practical) limitation on just how far the process could recursively descend before the end of memory is reached. I imagine that general-purpose "Recursive Call" and "Recursive Return" subroutines could be written for each calculator, with some documentation detailing how to use them, and what other requirements there may be of the programming and storage for the actual routines being called. (I wouldn't bother with the -32s -- not enough memory. But the -41, -42S & beyond should be capable of supporting such.)
In fact, I don't know what the limit on subroutine descent is in the 49/49 models. I doubt it's anywhere near as limited as it is on the earlier machines. But I don't have my manual handy . . .
Re: Recursion in HP Calcs - Thibaut.be - 06-07-2002 Well, on the 41C the GSB function is well present. Now I have a doubt. The difference between GTO and GSB is, as most of us know I guess, that the RTN function steps to the next instruction after GSB.
I will check that on my 41, but I think the XEQ function works like the GSB in that sense...
Re: Recursion in HP Calcs - Andrés C. Rodríguez (Argentina) - 06-07-2002 In fact, XEQ as used in the HP41/42 replaced the GSB mnemonic used in previous models. The discussion about recursion has to do with the "pending returns" depth of an internal "return addresses" stack (nothing to do with the RPN stack, of course). The HP41 had 6 levels of pending returns, the HP42 increased it to 8; in any case this limits the "recursionability" of these models.
So your statement can be enhanced as "the RTN function steps to the next instruction after GSB" [as long as there are no more than "n" pending returns].
Re: GSB Considered Harmful - Paul Brogger - 06-07-2002 Right. We're not talking about the RPN stack at all. But, my point is, if you AVOID using GSB/RTN (or whatever) to call subroutines, you aren't bound by the limited subroutine call depth supported by the calculator's firmware. To avoid GSB/RTN, one would have to simulate GSB/RTN functionality using application logic that is based on GTO (and probably utilizing arrays). This logic would have to save return "addresses" and local variable values on a stack, pushing the values at the time of pseudo-GSB, and popping those values as part of a pseudo-RTN.
So, given some clever programming and enough memory, you needn't be limited by the depth calculator's internal return stack.
Return addresses - Andrés C. Rodríguez (Argentina) - 06-07-2002 While we may think about keeping our own management of return addresses, it should be noted that you cannot return to an arbitrary program line. You can simulate a return by means of a GTO to an existent label (somehow identified by your "return handling" extensions), or go to a PHYSICAL address (which is most harmful, indeed!) using synthetic programming and a lot of discipline.
While I was the one who stated that HP41/42 could operate recursively, I am also among the first to admit such feature is very limited for general recursion.
Re: Recursion in HP calcs -- Pseudocode - Paul Brogger - 06-07-2002 Here's how I think it would work. . . Scenario: . Main process named “MP” . . calls recursive subprocess to figure something. , Recursive subprocess named “RSP” . Figures something in two blocks of code (“RSP_a” & “RSP_b”), . . with possible recursive self-call in between them. . Needs to maintain two local variables, “x” & “y” across recursive calls. , Logic: . process MP . . allocate recursive call/return stack . . initialize stack pointer to 0 . . [ do some work ] . . initialize x = 0 . . initialize y = 0 . . set caller = “MP” [could be a numeric code, whatever] . . GSB RSP_a . . [ do some more work ] . . clean up & exit. . . endprocess MP . process RSP_a . [use x & y] . push x . push y . push caller . IF recursive descent indicated THEN . . set caller = “RSP_a” . . GTO RSP_a . ELSE . . GTO RSP_b . endprocess RSP_a . process RSP_b . pop caller . pop y . pop x . [ use x & y ] . IF caller = “RSP_a” THEN . . GTO RSP_b . ELSE . . RTN . endprocess RSP_b . "push" & "pop", of course, would utilize an array as a stack to save values and caller codes.
I'll have to try to implement a general solution to, say, the "Tower of Hanoi problem" on my 42s this weekend . . .
Re: Return addresses - John K. (US) - 06-07-2002 The method I used was actually a little simpler (in theory, anyway) than that mentioned by Mr. Brogger. It involved copying the two status registers ("a" & "b" as I recall), which contain all six return pointers and the program counter, to main memory, starting at an address that the user specified in an initialization routine. Two other registers were also used to keep track of the number of return frames (set of six return pointers) that had been used and the current reference count within each frame (so that the routine knew when it was time to copy the current frame and start a new one), and a third register to keep track of the starting point. I tried using one of the alpha registers for the last, but every once in a while something would happen and a program would munge the value. Lossage would then ensue. It worked -- to a point. One of the problems I ran into involved the program counter, and another problem was (as is often the case with reference-counting systems) with calls to routines that didn't play along. The details are a little fuzzy in my head since I haven't really thought about this for 15 years or so.
(Wow. High weirdness in the forums.)
Final Remarks - Ex-PPC member - 06-08-2002 Thanks to all those people that posted and/or were interested in this thread. This time there
Re: Final Remarks - Chris Randle (UK) - 06-09-2002 I'm still thinking about this puzzle! My brain is slower than most!!
I hope to have some code soon, so could you give me another 24 hours to come up with something (like code that can find the answers) before posting any solution? I mean algorithmic solution - not numeric (which has already been found).
Re: Final Remarks - Ex-PPC member - 06-09-2002 Chris Randle wrote:
"I'm still thinking about this puzzle! [ ... ] could you give me another 24 hours to come up with something (like code that can find the answers) before posting any
Thanks for your interest, and don't worry for any deadline
Normally I'll post a "Final Remarks" message, |