The Museum of HP Calculators

HP Forum Archive 10

[ Return to Index | Top of Index ]

A New Challenge
Message #1 Posted by Katie Wasserman on 18 Jan 2003, 7:03 p.m.

Since at least a few people here seem to like my solution to the last challenge I thought that I'd pick up the gauntlet and propose another little challenge.....

I often find the need for a MOD function (remainder after division) on the HP calculators, but only a very few of the non-HPL machines have it (the 41C, 42S and 16C come to mind). How can this be done on a less-sophisticated RPN calculator in the fewest instruction steps?

Assume that the dividend is in Y and the divisor is in X and that you can only use the stack and last X register. One obvious solution using FP (Fractional Part) doesn't work because of rounding problems.

For example:

/, LAST X, X<>Y, FP, x

If you had the DUP2 function it would be easy:

DUP2, /, IP, x, -

But you donít. On the 32S/SII you can do this trick for DUP2:

0, ENTER, CMPLX+, /, IP, x, -

But that's hardly a general solution and it's still 7 steps.

Is there a shorter way? (I donít have an answer.)

-Katie

      
Re: A New Challenge
Message #2 Posted by Vieira, Luiz C. (Brazil) on 19 Jan 2003, 3:35 a.m.,
in response to message #1 by Katie Wasserman

Hi;

wow, hard to achieve another "shorter" version. The one I developed sometime ago is one byte longer:

INT  (to save X-contents in L)
x<>y
LSTx
ų
FRC
◊

I think it's gonna be hard to beat you, Katie...

Best regards

      
Re: A New Challenge
Message #3 Posted by Ed Martin on 19 Jan 2003, 2:22 p.m.,
in response to message #1 by Katie Wasserman

This problem is more tricky than it appears at first glance. One way to "cheat" is to use the RND function at the end of Katie's "obvious" FP solution to get rid of the rounding error, but that isn't a pure algorithm.

The best general (non-RND) solution I could come up with for RPN calcs is as follows. However, you need to make sure the "x" register (divisor) is not in entry mode (a quick x<>y x<>y will ensure that).

ENTER ENTER + x<>y - / LASTx x<>y INT * -

It's really long at 11 steps but avoids the rounding error and will work on any RPN calc with a 4 level stack that replicates the "t" register on a stack drop.

Surely someone can do better than this .....

            
Re: A New Challenge - Improved
Message #4 Posted by Ed Martin on 19 Jan 2003, 5:53 p.m.,
in response to message #3 by Ed Martin

OK, so this is only a minor improvement over my last post. It's one step shorter, and on top of that, it doesn't care if "x" is in the middle of entry:

x<>y ENTER ENTER RUP / LASTx x<>y INT * -

                  
Re: A New Challenge - Improved
Message #5 Posted by Christof on 20 Jan 2003, 4:21 a.m.,
in response to message #4 by Ed Martin

after a lot more working it looks like both of our 10 step solutions are about the best that can be done without some really off the wall trick.

I've run through 7 various 10 step program variants now (all seem to end up being basically similar to either your 10 step or my 10 step "style" - the 4 step finish and fully loaded stack or the 6 step finish and partially loaded stack.) All are 18 bytes with program RTN statements and LBLs.

            
Re: A New Challenge
Message #6 Posted by Katie Wasserman on 19 Jan 2003, 11:12 p.m.,
in response to message #3 by Ed Martin

Ed, you and Luiz both mentioned using FRAC and the RND function. But if you use really big integers as input to the MOD function you'll get the wrong answer sometimes. For example: try 555,555,555,555 mod 333,333,333,333. Obviously the answer is 222,222,222,222 but using FRAC and RND you won't get that.

Stack manipulation seems to be the hard part of this problem, but there might be some clever technique that gets around all that. I wonder why HP left out the MOD function on its scientific calculators (for the most part) surely itís more useful to most engineers and scientists than % is, for example.

                  
Re: A New Challenge
Message #7 Posted by Christof on 20 Jan 2003, 1:21 a.m.,
in response to message #6 by Katie Wasserman

okay, my code for the 32Sii seems to be non original, but at least not entirely lame :)

here's another version that is still in the same realm of byte use, but uses a slightly different approach

x<>y enter rolldown swap / lastx swap ip * swap rolldown -

there doesn't seem to be a way to directly store to a stack register in the 32Sii, otherwise that could be cut down a bit with a x<>y STO-z x<>y STO-t / IP * -

Maybe there is something I'm not seeing -C

      
Re: A New Challenge
Message #8 Posted by Christof on 20 Jan 2003, 12:52 a.m.,
in response to message #1 by Katie Wasserman

I was working on this at lunch and am posting before reading all the other answers. So I will probably look dumb.

solution 1 takes 16.5 bytes (no rtn because I left it at end of program memory. cheating, yes.).

A01 LBL A

A02 ENTER

A03 ENTER

A04 R(UP)

A05 ENTER

A06 R(DOWN)

A07 x<>y

A08 /

A09 IP

A10 *

A11 -

R(UP) being roll up, etc. It's a lot of steps, 16.5 bytes, and can be duplicated on most calculators.

solution 2 is a bit longer, but interesting:

B01 LBL B

B02 x<>y

B03 ENTER

B04 ENTER

B05 R(UP)

B06 /

B07 LASTx

B08 x<>y

B09 IP

B10 *

B11 -

B12 RTN

and that is 18 bytes.....

Those are first thoughts, now I will read what is posted and see

      
Re: A New Challenge
Message #9 Posted by Ex-PPC member on 20 Jan 2003, 5:20 a.m.,
in response to message #1 by Katie Wasserman

Hi Katie, thanks for the interesting challenge, I've just read your post while in transit.

Using the HP-15C I always carry with me, I've come up with a 7-step solution with no rounding problems whatsoever, but it's still a little rough and perhaps I can improve it tonight, when I'll finally be able to allocate some free time to think about it.

Best regards.

      
Re: A New Challenge
Message #10 Posted by hugh on 21 Jan 2003, 2:29 p.m.,
in response to message #1 by Katie Wasserman

recently i had the urge to write a easter day program for the HP25. however the lack of accurate modding scuppered my plan. the following logic,

STO 1 1 9 / FRAC 2 0 9 * 2 0 4 - CHS 3 0 / FRAC 3 0 * 2 2 + 5 0 x<>y x<y GTO 32 1 - ENT RCL 1 + RCL 1 4 / INT + 7 / FRAC 7 CHS * 6 + +

is correct (enter y R/S) but the use of FRAC to make the mods causes round errors that give some years wrong. no good then. there's 1 spare step :-)

my theory of why MOD is scarce is because its not easy to implement. try 1e50 mod 9. what do you get?

            
Re: A New Challenge
Message #11 Posted by Katie Wasserman on 21 Jan 2003, 8:37 p.m.,
in response to message #10 by hugh

Good point! The method that I've presented here would give 0 as 1e50 MOD 9 which is wrong. But other (higher end) HP calculators get this right, like the 42S. It's not a hard problem when you can do it in assembly language you need only deal with an adjusted mantissa. It's much harder to do on the lower end calculators, but not impossible. Certainly HP could have found room in the 32SII ROM for this if they thought it was useful.

                  
Re: A New Challenge
Message #12 Posted by hugh on 22 Jan 2003, 6:49 a.m.,
in response to message #11 by Katie Wasserman

yes thats right. adjusting the mantissa was the method i used recently implementing a working mod function. for a number `x', i had to scale it into y * 10^e where y is a n-digit integer and n is your calculator precision. eg 10 (i was using n = 30). this is especially important if `x' internally is binary. then you do, mod(mod(y,m)*mod(10^e, m),m) and 10^e is done by binary powering.

there's more. the second problem is you also need double-precision arithmetic. if you are 10 digit accurate, you need 20 internally. consider calculating a = 1e10, b = 3.141592654 (dont call this pi for another reason) and find mod(a, b) the right 10 digit answer is: 1.326632906, thats because internally you had to work with a/b = 3183098861.4222803693 in order to get 10 final digits correct.

even more amusing are mods truly involving pi or 2pi, like those required to perform sin, cos or tan. try sin(1e50), the right answer is: -.7896724934 because the problem is actually sin(mod(1e50,2pi)). these mods are even harder because you need a table of around 100 digits internally of 1/2pi to perform mod(10^n,2pi).

some time ago, i wrote a page on this, but its not very well explained.

http://www.voidware.com/modsecret.htm

                        
Re: A New Challenge
Message #13 Posted by Katie Wasserman on 22 Jan 2003, 4:19 p.m.,
in response to message #12 by hugh

Hugh,

Your web page on this is very understandable and makes total sense. HP must have been quite aware of this and designed their trig functions to work differently when the calcualtor is in "degrees" mode. The 32SII (and all the other HP's I've cheked so far) do the mod 360 degrees correctly before computing the trig function values.

Computing MOD does require double precsision when you do it as: y - x*floor[y/x], but not if you're computing it in assmebly langauge (or doing long division explicity on the calculator); the remainder after the division is likely just sitting around in a register (if you divide the obvious way).

-Katie


[ Return to Index | Top of Index ]

Go back to the main exhibit hall