Mini challenge. CEIL / FLOOR in RPN « Next Oldest | Next Newest »

 ▼ M. Joury Posting Freak Posts: 756 Threads: 31 Joined: Aug 2010 10-29-2011, 07:42 PM Hi All, Recently I needed a FLOOR function on my HP41. Easy enough, but I decided to generalize the solution. I wanted FLOOR and CEILING functions that did not effect the stack (Y, Z, and T are preserved) and that did not use any registers. LASTX does not have to be correct. My solution uses 44 bytes on an HP41 including 19 bytes for the LBL FLOOR, LBL CEIL and the END instructions. My solution does not update LASTX correctly but it could if I were willing to use more memory. I use no SP tricks but they are not disallowed. Off the top of my head I can't see how SP would help but I am going to look into it in more detail to see if I am missing something. I worked on this for longer than I expected when I started the exercise and would love to see other solutions. I just can't shake the feeling that I am missing something obvious--some trick that will shave the code to half the size and twice the speed. At one point I thought that I had a very elegant truly tiny solution but it did not work for certain cases. I'll share later. Cheers, -Marwan ▼ Allen Senior Member Posts: 562 Threads: 27 Joined: Oct 2006 10-29-2011, 07:45 PM How do you define FLOOR and CEIL for negative numbers? ▼ M. Joury Posting Freak Posts: 756 Threads: 31 Joined: Aug 2010 10-29-2011, 08:05 PM ```FLOOR(-2.3) = -3.0 CEIL(-2.3) = -2.0 ``` Therein lies the trick because otherwise (for a positive number) FLOOR is just INT or IP. INTG on the 33S or 35S is a FLOOR function but as far as I can tell there is no CEILING on those machines. Cheers, -Marwan Edited: 29 Oct 2011, 8:10 p.m. ▼ Marcus von Cube, Germany Posting Freak Posts: 3,283 Threads: 104 Joined: Jul 2005 10-30-2011, 04:51 AM FLOOR(x) = -CEIL(-x) and vice versa. This should help on the 33/35S. PeterP Senior Member Posts: 564 Threads: 72 Joined: Sep 2005 10-29-2011, 08:44 PM can we use alpha? ▼ M. Joury Posting Freak Posts: 756 Threads: 31 Joined: Aug 2010 10-29-2011, 10:19 PM No. Egan Ford Posting Freak Posts: 1,619 Threads: 147 Joined: May 2006 10-29-2011, 08:48 PM 41 RPN: ``` 1 LBL FLOOR 2 INT 3 x<0? 4 x<>0? 5 RTN 6 X<>L 7 FRC 8 x<>0? 9 ST- L 10 X<>L 11 INT 12 RTN ``` Q&D. CEIL shouldn't be much different. Correct me if wrong, but LastX preserved. Edited: 29 Oct 2011, 9:05 p.m. after one or more responses were posted ▼ Paul Dale Posting Freak Posts: 3,229 Threads: 42 Joined: Jul 2006 10-29-2011, 09:04 PM Extending Egan's code using CEIL(x) = -FLOOR(-x): ``` 1 LBL CEIL 2 CHS 3 XEQ 00 4 CHS 5 RTN 6 LBL 00 7 LBL FLOOR 8 INT 9 x<0? 10 x<>0? 11 RTN 12 X<> L 13 FRC 14 x<>0? 15 ST- L 16 X<> L 17 INT 18 END ``` Is this 38 bytes all up? - Pauli Edit: merged in Egan's improvements Edited: 29 Oct 2011, 9:12 p.m. after one or more responses were posted ▼ Egan Ford Posting Freak Posts: 1,619 Threads: 147 Joined: May 2006 10-29-2011, 09:06 PM Doh! Concurrent updates. I changed it, shorter now. ▼ Paul Dale Posting Freak Posts: 3,229 Threads: 42 Joined: Jul 2006 10-29-2011, 09:12 PM Easily fixed :-) - Pauli M. Joury Posting Freak Posts: 756 Threads: 31 Joined: Aug 2010 10-29-2011, 10:32 PM -2.3 return -2.0 not -3.0. INT would give you the same results. Solution not working correctly for negatives. Also, your solution to CEIL is exactly what I used in my solution. That is why LASTX does not work for CEIL in my solution. Cheers, -Marwan Edited: 29 Oct 2011, 10:35 p.m. after one or more responses were posted ▼ Paul Dale Posting Freak Posts: 3,229 Threads: 42 Joined: Jul 2006 10-29-2011, 10:34 PM Blame Egan for the floor -- I just copied his code :-) I checked the one byte longer version and I'm pretty sure floor(-2.3) was correct then. - Pauli ▼ M. Joury Posting Freak Posts: 756 Threads: 31 Joined: Aug 2010 10-29-2011, 10:41 PM I never got to see the 1 byte longer version. I count 39 bytes in the current version (?). If the original version was 1 byte longer and works it is 4 bytes shorter than mine (I think). Cheers, -Marwan Edited: 29 Oct 2011, 10:41 p.m. M. Joury Posting Freak Posts: 756 Threads: 31 Joined: Aug 2010 10-29-2011, 10:27 PM Don't think that this is right. For FLOOR(-2.3) it returns -2. FLOOR(-2.3) should be -3.00. Dieter Senior Member Posts: 653 Threads: 26 Joined: Aug 2010 10-30-2011, 10:08 AM This will not work. First, the inital test makes no sense. It uses a well-known technique from the good old days: use two consecutive tests, and you will get a "composite test" for (NOT condition1) OR condition2. So x<0? followed by x<>0? logically equals "X>=0 OR X<>0?", or in other words: "is x greater than zero, or equal to zero, or not equal to zero". Which is the case for any number. So the program will always stop after this test, simply returning INT(x). #-) There also is not much sense in the sequence "X<>0? ST-L" as the test for non-zero X is obsolete: if X actually is zero subtracting it from L will not change anything. Here's my (also Q&D) first idea for the '41: ```01 LBL"FLOOR" 02 INT 03 X<> L 04 X<0? 05 DSE L 06 LBL 00 07 X<> L 08 END ``` It even sets LastX correctly. But it will not work for negative integers, so I'll keep trying. ;-) Dieter Edited: 30 Oct 2011, 10:12 a.m. Werner Member Posts: 163 Threads: 7 Joined: Jul 2007 10-30-2011, 05:26 AM 43 bytes, perfect function (YZT preserved, LASTX contains last X): ```01*LBL"CEIL" 02 INT 03 X<>Y 04 X<> L 05 X>Y? 06 ISG Y 07 LBL 00 (NOP) 08 X<> L 09 X<>Y 10 RTN 11*LBL"FLOOR" 12 INT 13 X<>Y 14 X<> L 15 X L 19 X<>Y 20 END ``` it won't win the elegance prize, though ;-) Cheers, Werner ▼ M. Joury Posting Freak Posts: 756 Threads: 31 Joined: Aug 2010 10-30-2011, 08:38 AM Nice. Actually I think it is pretty elegant--a single test, a single exit point (RTN), shorter, and you don't use a flag. Better than mine. But see Pauli's and Marcus's solution and comments above. If you are willing to give up LASTX (as I was) you can use: ```LBL CEIL CHS XEQ 00 CHS RTN LBL FLOOR LBL 00 ... ``` This is what I did in my original solution and why I said that LAST X is correct for FLOOR but not for CEIL. It shortens the code considerably. Cheers, -Marwan Edited: 30 Oct 2011, 8:47 a.m. Dieter Senior Member Posts: 653 Threads: 26 Joined: Aug 2010 10-30-2011, 10:19 AM *clap* *clap* I see the idea with DSE/ISG is quite obvious. And it's sufficiently elegant as well. ;-) Dieter Namir Posting Freak Posts: 2,247 Threads: 200 Joined: Jun 2005 10-30-2011, 10:53 AM I regard the STO X command is the best NOP for the HP-41C and HP-42s. Namir ▼ Dieter Senior Member Posts: 653 Threads: 26 Joined: Aug 2010 10-30-2011, 10:57 AM But STO X requires two bytes, while LBL 00 only takes one. ;-) Dieter M. Joury Posting Freak Posts: 756 Threads: 31 Joined: Aug 2010 10-30-2011, 11:00 AM The Zenrom module offers a NOP instruction that is basically a text byte (I think) but I am not sure of the length. Also X <> X works well but is also two bytes as is STO X. Cheers, -Marwan M. Joury Posting Freak Posts: 756 Threads: 31 Joined: Aug 2010 10-30-2011, 11:56 PM Hi Werner, Did you see Alan's solution below? It does not work for integer values but he uses a trick that can shorten your version by 3 bytes. Instead of: ```ISG Y LBL 00 X<> L X<>Y RTN ``` You can use: ```ISG Y LBL 00 GTO 00 ``` A savings of 3 bytes. Cheers, -Marwan ▼ Werner Member Posts: 163 Threads: 7 Joined: Jul 2007 10-31-2011, 03:40 AM Only two bytes ;-) Werner ▼ M. Joury Posting Freak Posts: 756 Threads: 31 Joined: Aug 2010 10-31-2011, 06:58 AM Right, sorry, GTO 00 is 2 bytes not 1 byte. Cheers, -Marwan M. Joury Posting Freak Posts: 756 Threads: 31 Joined: Aug 2010 10-30-2011, 11:05 AM Here is my original solution. But as noted elsewhere Werner's is better (which was partially what drove the challenge--find a better solution). ```LBL CEIL CHS XEQ 00 CHS RTN LBL FLOOR LBL 00 CF 20 FRC X=0? SF 20 CLX These two instruction could also be X <> L LAST X which is the same number of bytes INT FS?C 20 RTN X>0? RTN DSE X RTN END ``` 44 bytes total preserves Y, Z, and T. Preserves LASTX for FLOOR but not for CEIL. I don't see any way to do this without using a DSE instruction so I would love to see Egan's original solution it works. The later solution does not. Cheers, -Marwan Edited: 30 Oct 2011, 11:06 a.m. ▼ Gerson W. Barbosa Posting Freak Posts: 2,761 Threads: 100 Joined: Jul 2005 10-30-2011, 12:06 PM Quote:```LBL CEIL CHS XEQ 00 CHS RTN ``` I found this relationship yesterday, at Wikipedia: FLOOR(x) can be defined in terms of INT(x) and FRC(x), but I don't see this being mentioned there: `FLOOR(x) = INT(x) + INT(FRC(x) + 1) - 1` On the HP-15C, the following avoids any test, but preserves Y only. Perhaps it can be optimized on the HP-41. ```001- f LBL C ; CEIL 002- CHS 003- GSB A 004- CHS 005- g RTN 006- f LBL A ; FLOOR 007- g INT 008- g LSTx 009- f FRAC 010- 1 011- + 012- g INT 013- 1 014- - 015- + 016- g RTN ``` Regards, Gerson. ▼ M. Joury Posting Freak Posts: 756 Threads: 31 Joined: Aug 2010 10-30-2011, 12:23 PM Hi Gerson, I found the same relationship. The fly in the ointment in my original challenge, so to speak, was the requirement that the stack be preserved. I am trying to think of ways to optimize your solution on the 41 to meet that requirement. Cheers, -Marwan ▼ Gerson W. Barbosa Posting Freak Posts: 2,761 Threads: 100 Joined: Jul 2005 10-30-2011, 12:45 PM Quote: The fly in the ointment in my original challenge, so to speak, was the requirement that the stack be preserved. Yes, I am aware of it. That's not an easy task, congratulations for your and other's accomplishments! Cheers, Gerson. Edited: 30 Oct 2011, 12:55 p.m. ▼ M. Joury Posting Freak Posts: 756 Threads: 31 Joined: Aug 2010 10-30-2011, 01:24 PM Thanks. I have to say that it took me longer than Werner to come up with a less elegant solution . Cheers, -Marwan Edited: 30 Oct 2011, 1:24 p.m. ▼ Werner Member Posts: 163 Threads: 7 Joined: Jul 2007 10-30-2011, 01:42 PM Hi Marwan, I didn't come up with this on the fly, it's been in my files for quite a while now ;-) cheers, Werner ▼ M. Joury Posting Freak Posts: 756 Threads: 31 Joined: Aug 2010 10-30-2011, 05:11 PM You know, you guys are all too damn honest! :) Cheers, -Marwan Werner Member Posts: 163 Threads: 7 Joined: Jul 2007 10-30-2011, 02:28 PM Equivalent formulas: ``` CEIL(x) = x - FRC(FRC(x) - 1) FLOOR(x) = x - FRC(FRC(x) + 1) ``` However, as Dieter pointed out in a previous post a few weeks ago, these do not work for very small x. eg for x = -1e-50 your FLOOR function will return the wrong result Cheers, Werner M. Joury Posting Freak Posts: 756 Threads: 31 Joined: Aug 2010 10-30-2011, 05:17 PM Well, I continued to think about this while out cycling today and I think I have a 37 byte solution. There are a couple of caveats: ```1. LASTX is not preserved and 2. The solution is NOT symmetrical. That is you can't write a solution for FLOOR on it's own it has to be done through a call to CEIL because the HP41 does not have symmetrical tests (that is there is an X<=0? but no X>=0? on the 41. It is symetrical on the 42S which has both tests. ``` Here is my latest effort: ```LBL FLOOR CHS XEQ 00 CHS RTN LBL CEIL LBL 00 FRC X<=0? GTO 00 CLX 1 ST+ L LBL 00 This is *NOT* a NO-OP X<>L INT END ``` Cheers, -Marwan EDIT: Fixes issue with longer fraction (ss.eeeii) as pointed out by Werner but adds 2 bytes. 39 bytes now. Edited: 31 Oct 2011, 7:49 a.m. after one or more responses were posted ▼ Werner Member Posts: 163 Threads: 7 Joined: Jul 2007 10-31-2011, 03:55 AM Perhaps we can use a 'test' suite to guarantee that a program returns the correct solution in all cases. So, how about (just for CEIL): ```CEIL(0) : 0 CEIL(1e-50) : 1 CEIL(-1e-50) : 0 CEIL(2e-5) : 1 CEIL(-2e-5) : 0 CEIL(1) : 1 CEIL(-1) : -1 CEIL(PI) : 4 CEIL(-PI) : -3 CEIL(10) : 10 CEIL(-10) : -10 CEIL(1e50) : 1e50 ``` That will do, I think ;-) Cheers, Werner ▼ M. Joury Posting Freak Posts: 756 Threads: 31 Joined: Aug 2010 10-31-2011, 07:09 AM Good idea. There are so many cases where true decrement / increment operators would have been useful. Cheers, -Marwan ▼ Paul Dale Posting Freak Posts: 3,229 Threads: 42 Joined: Jul 2006 10-31-2011, 07:15 AM That's why the 34S has them :-) I was also tempted to do the equivalent of ISG and DSE but without the skips. - Pauli ▼ M. Joury Posting Freak Posts: 756 Threads: 31 Joined: Aug 2010 10-31-2011, 08:04 AM It always seemed to me that they should have been able to squeeze them into the 41. Allen Senior Member Posts: 562 Threads: 27 Joined: Oct 2006 10-30-2011, 11:06 PM Here's a 28 byte version, including 17 bytes for the alpha labels: Using D. Knuth's definitions (Concrete Mathemetics, Ch. 3, p.67 ```FLOOR(x)="the greatest integer less than or equal to x." CEIL(x) ="the least integer greater than or equal to x." ``` For CIEL, we increment 1 for negative input, for FLOOR we decrement 1 for positive input, then return the IP of the result in all 4 cases (pos,neg input and CIEL,FLOOR selection). ```00 { 28-Byte Prgm } 01>LBL "CIEL" 02 X>0? 03 ISG ST X 04 IP 05 GTO 00 06>LBL "FLOOR" 07 X<0? 08 DSE ST X 09>LBL 00 10 IP 11 .END. ``` Note: Does not account for integer inputs when ciel(x>0) or floor(x<0). Edited: 30 Oct 2011, 11:29 p.m. after one or more responses were posted ▼ M. Joury Posting Freak Posts: 756 Threads: 31 Joined: Aug 2010 10-30-2011, 11:26 PM I came up with this solution very early on in my efforts but it doesn't work. CEIL(2.0) is 2.0 not 3.0 as returned by this algorithm. Similarly FLOOR(-2.0) should return -2.0 and not -3.0. Cheers, -Marwan Edited: 30 Oct 2011, 11:33 p.m. after one or more responses were posted ▼ Allen Senior Member Posts: 562 Threads: 27 Joined: Oct 2006 10-30-2011, 11:29 PM yep, just noted that in the comments. ▼ M. Joury Posting Freak Posts: 756 Threads: 31 Joined: Aug 2010 10-30-2011, 11:34 PM Yes. So does not work as a generalized solution. M. Joury Posting Freak Posts: 756 Threads: 31 Joined: Aug 2010 10-30-2011, 11:49 PM I like the trick you use to save a byte by: ```ISG X IP GTO 00 ``` Saves a byte over: ```ISG X LBL 00 NOP IP RTN ``` Very clever. Can be used to save 3 bytes in Werner's solution (which is, IMHO, the best so far). Cheers, -Marwan Edited: 30 Oct 2011, 11:52 p.m. ▼ Allen Senior Member Posts: 562 Threads: 27 Joined: Oct 2006 10-31-2011, 01:43 AM Ok, last try for the night. Does NOT use synthetic programming or flags. It works by hard-coding a 3-variable K-map for POS/NEG, INT/Non-INT, inputs and CIEL/FLOOR function. (8 cases) ```1) If NEG CEIL then return IP(X) (2 cases) 2) Else If POS FLOOR then return IP(X) (2 cases) 3) Else If FP(X)=0 then return IP(X) (2 cases) 4) Else If X>0 return IP(X+1) (1 case) 5) Else If X<0 return IP(X-1) (1 case) ``` ```00 { 43-Byte Prgm } 01>LBL "CIEL" 02 X<0? 03 GTO 02 04 GTO 00 05>LBL "FLOOR" 06 X>0? 07 GTO 02 08>LBL 00 09 STO ST L 10 FP 11 X=0? 12 GTO 01 13 X>0? 14 ISG ST L 15 X<0? 16 DSE ST L 17>LBL 01 18 X<> ST L 19>LBL 02 20 IP 21 .END. ``` Edited: 31 Oct 2011, 2:04 a.m. ▼ Marcus von Cube, Germany Posting Freak Posts: 3,283 Threads: 104 Joined: Jul 2005 10-31-2011, 02:55 AM Allen, all your solutions have something 'heavenly' ;-) M. Joury Posting Freak Posts: 756 Threads: 31 Joined: Aug 2010 10-31-2011, 07:56 AM This looks like a 42S solution. I count 44 bytes for a 41. Also see Werner's comment below. That got me as well in my second solution (now fixed but 2 bytes longer). Cheers, -Marwan Werner Member Posts: 163 Threads: 7 Joined: Jul 2007 10-31-2011, 03:16 AM But that doesn't work.. ISG and DSE work on numbers in sss.eeeii format, and will thus add/subtract ii, or 1 when ii=0. Try your example with PI for instance ... Cheers, Werner ▼ Allen Senior Member Posts: 562 Threads: 27 Joined: Oct 2006 10-31-2011, 08:09 AM Wow- you're right, I get so used to using ISG/DSE on integers and forget there is a seldom-used increment value on the right! M. Joury Posting Freak Posts: 756 Threads: 31 Joined: Aug 2010 10-31-2011, 10:11 AM Following is a test driver based on Werner's test scenarios. It is not small but it does test all the suggested cases automatically. Since I currently have a number of FLOOR solutions in memory I have set it up so that the user enters the name of the CEIL and FLOOR functions. Run it by "XEQ FLTST" or if from within the program area "XEQ A" or simply A in user mode and then follow the prompts. You will be asked first for the CEIL FN name and then the FLOOR FN name. The calculator is already in ALPHA mode so enter the name and press R/S. Total size: 270 bytes. ```LBL FLTST LBL A SF 21 CEIL FN AON AVIEW AOFF CLD ASTO 01 0 ENTER^ XEQ IND 01 X<>Y? GTO 01 1 ENTER^ 1E-50 XEQ IND 01 X<>Y? GTO 01 0 -1E-50 XEQ IND 01 X<>Y? GTO 01 1 2E-5 XEQ IND 01 X<>Y? GTO 01 1 ENTER^ XEQ IND 01 X<>Y? GTO 01 -1 ENTER^ XEQ IND 01 X<>Y? GTO 01 4 PI XEQ IND 01 X<>Y? GTO 01 -3 PI CHS XEQ IND 01 X<>Y? GTO 01 10 ENTER^ XEQ IND 01 X<>Y? GTO 01 -10 ENTER^ XEQ IND 01 X<>Y? GTO 01 1E50 ENTER^ XEQ IND 01 X<>Y? GTO 01 FLOOR FN AON AVIEW AOFF CLD ASTO 01 0 ENTER^ XEQ IND 01 X<>Y? GTO 01 0 1E-50 XEQ IND 01 X<>Y? GTO 01 -1 -1E-50 XEQ IND 01 X<>Y? GTO 01 0 2E-5 XEQ IND 01 X<>Y? GTO 01 -1 -2E-5 XEQ IND 01 X<>Y? GTO 01 1 ENTER^ XEQ IND 01 X<>Y? GTO 01 -1 ENTER^ XEQ IND 01 X<>Y? GTO 01 3 PI XEQ IND 01 X<>Y? GTO 01 -4 PI CHS XEQ IND 01 X<>Y? GTO 01 10 ENTER^ XEQ IND 01 X<>Y? GTO 01 -10 ENTER^ XEQ IND 01 X<>Y? GTO 01 1E50 ENTER^ XEQ IND 01 X<>Y? GTO 01 SUCCESS AVIEW RTN LBL 01 FAIL AVIEW STOP END ``` I hope this helps a little with testing these routines. Cheers, -Marwan

 Possibly Related Threads... Thread Author Replies Views Last Post HP Prime: FLOOR, iPart , and their use in programs Alberto Candel 6 1,805 12-01-2013, 10:17 PM Last Post: Alberto Candel [PRIME] RPN: another attempt at returning more than one value to the RPN stack Marcus von Cube, Germany 5 1,751 11-05-2013, 02:44 AM Last Post: Marcus von Cube, Germany HHC 2013 RPN Programming Challenge - Final Thought Jeff O. 7 1,732 10-17-2013, 11:02 AM Last Post: Jeff O. HPCC Mini Conference 2013 hugh steers 6 1,577 09-13-2013, 04:27 PM Last Post: BruceH Picture from the Mini-HHC (LA) Geir Isene 11 2,269 07-07-2013, 01:06 PM Last Post: Jim Horn My birthday, so a little commemorative mini-challenge ! Valentin Albillo 43 5,831 03-07-2013, 03:44 AM Last Post: Walter B WP 34S mini-challenge (B) Gerson W. Barbosa 17 3,278 12-27-2012, 04:39 PM Last Post: Marcus von Cube, Germany HHC 2012 RPN Programming Challenge Conundrum Jeff O. 15 2,899 10-08-2012, 03:34 PM Last Post: Gerson W. Barbosa Mini-challenge: HHC2012 RPL programming contest with larger input David Hayden 14 2,596 10-05-2012, 10:36 PM Last Post: David Hayden HP41 / SY41CL Mini-B USB Power Connector (Module) Matt Kernal 5 2,571 07-08-2012, 06:23 PM Last Post: Diego Diaz

Forum Jump: