|
Re: HP-41 Programming Challenge
|
|
|
|
« Next Oldest | Next Newest »
|
▼ 
07-28-2003, 01:15 PM
Just in case this gets buried in the board: I have posted my version of the prime finder program here.
Thanks, ▼
07-28-2003, 06:47 PM
Hi, Axel; I made minor changes to reduce proram size (bytes used) but they are not significant so far. As I am able to show an actual improved "version", I'm posting. For now, congrats! I like seeing others programs. And yours work pretty fine! Best regards. Luiz (Brazil)
07-28-2003, 07:39 PM
here's my entry. it misses out "3".
LBL "MOO" ▼
07-29-2003, 06:42 AM
Hi Hugh,
you got a bug in your program. It finds 35 as a primnumber. I think it does not really check for 5 beeing a divider of the number thats beeing tested.
Regards, ▼
07-31-2003, 06:06 AM
aaawwl. and i thought i had it nailed.... :-) after more testing, i am not happy with this submission of mine. it appears to start quite fast and after a minute or so, is way ahead of the division programs listed here. however, its long term performance suffers because the algorithm can have worst cases later on. i submitted another program below, which (although a bit long) is complementary to the division programs. its a lot slower at first, but gets better (against division for bigger numbers). say you start at 100,000. its happy. the ideal agorithm would be some mix of trial division and the "tortoise". regards, ▼
07-29-2003, 01:15 AM
Hi, Trent; I always like to challenge myself first and then I go for the fight! I tried once to write a program for the HP25 and I did not succeed. It was supposed to compute nPr and nCr (permutations and combinations given n and r). I succeeded writing it for the HP33, that is essentially an HP25 with subroutine and a few extra functionality. I also wrote it for the HP55 and HP38. The key its the fact that both HP55 and HP38 have [n!], primarily needed to compute both nPr and nCr. Both HP25 and HP33 do not have [n!] and it is necessary to implement it OR add some math simplification based on numbers entered. I simply coded the original nCr and nPr expresions so they fitted in the HP33 memory. The only restriction is that neither n nor r might be greater than 69. Would it be possible to write a program for the HP25 to compute both nPr and nCr? In my program for the HP33C/E, you simply do this: key in: press: displayPressing [f]CLEAR[PRGM] before [R/S] or before inputting data ensures that the calculator is "pointing" to the first line of the program. I will add the listing below, but should you prefer trying from scratch, you should simply not to look at it |^). I accept challenges if I think I have a chance to succeed, but I do not feel comfortable challenging... I cannot explain why! I'd rather showing what I achieved and ask for new, different, clever solutions. Thanks.
Luiz (Brazil)
Edited: 29 July 2003, 1:23 a.m. ▼
07-29-2003, 02:06 AM
Hi Luiz, Actually, by using the n! function, you restrict yourself to n <= 69 on the older calcs, or n<= 253 on then newer ones. By programming a loop instead that keeps multiplying and dividing as needed, you will need more time (and space, of course), but you will get an extended range of input values that the program can compute for. I have no access to my calcs at the moment (they're at home, of course, and I'm at work right now), but I'll try to find my old HP41 program I wrote for these functions. Our math teacher got a thrill out of presenting problems that could not be solved with the calculator, and that's why I wrote a program to circumvent these limits. I could, however, write a HP49 program if I find the time to - I have that one at work with me. But it would be fun to see if it fits into the HP25...
Cheers, ▼
07-29-2003, 02:34 AM
Hi, Viktor; thank you for the additional information. In fact, I was aware of the fact that the [n!] limits for a single factorial are not the same when computing nCr or nPr. I tried to mention this fact when I wrote "add some math simplification based on numbers entered", but I simply missed it. Thank you. I'm not sure if both HP11C and HP15C were the first HP pocket calculators to offer Py,x and Cy,x as standard resources, but I know the algorithm used in both works things out in a way these limits are surpassed. What I want to know is if it's worth detecting overflow before it happens and mostly if it is possible to do it. I did not take spare time to think of it, but it seems to me it's not possible to detect such overflow occurrence in other way than using calculator's overflow detection after each successive multiplication to accomplish simplified terms for permutation and combination. (did I write a concise, understandable text? I hope so...:) If I understand it correctly, your program for the HP41 extends [FACT] limits so it computes nCr and nPr with n or c >69 if final result is <= 9.99999999E99. Is it correct? I'm curious to see it. About developing a program for the HP49G: I think using RPL would be very interesting, mostly to handle internal factorial limits. What makes me lazy about this is that all RPL models, since the HP28C, already have COMB an PERM as standard resources... Best regards, Victor. Luiz (Brazil) ▼
07-29-2003, 05:43 AM
Hi Luiz, I have not found a way to detect overflow in advance, so the program has to go for it and see if it overflows or not.
My HP41 program circumvents the limit of FACT by explicitly multiplying and dividing things out. The implementation is not difficult. Consider
n!
For n=7 and r=3, this yields
7x6x5x4x3x2x1
leaving only 7*6*5=210 after cancelling out the corresponding factors in enumerator and denominator. Similarly,
n!
so
7x6x5x4x3x2x1 7x6x5
In the second case, it can be debated whether doing the multiplications (more accurate, but higher risk of overflow) or the divisions (less accurate, lower risk of overflow) first is better. I think I have used an intermediate way doing both alternatingly, so 7C3 is evaluated as 7:3x4:2*5 (=35, at least on the HP49G I have available right now).I will try to find my program, but be warned: Chances are not that high, it's a long time since. If I don't find it, let's simply write new programs. It's fun, after all! Let's try to fit it into the HP25! And let's not forget to thank Harry for starting this challenge, and Axel for restarting the thread. Cheers, Victor
▼
07-29-2003, 08:00 AM
Well, here's mine. ▼
07-30-2003, 03:04 AM
I meant of course, that my program *avoided* all those pitfalls..
07-30-2003, 07:42 AM
six bytes shorter, and still keeping the Z-reg
07-29-2003, 03:05 PM
Luiz, Victor, Here is a program for the HP-25 that calculates either C(n,r) or P(n,r) for all cases where C(n,r) and P(n,r) are less than 1e100. The program fits comfortably in the 49 steps of program memory available on the HP-25. I haven't tested these routines on an actual HP-25, but I have tested them on the simulator found on this museums HP-25 page. The C(n,r) routine is based on the algorithm described by Victor. It makes use of the identity C(n,r) = C(n,n-r), selecting the minimum value of r and n-r for the calculations. In the loop body, the division is done first, to avoid overflows in cases where the intermediate calculations exceed the dynamic range of the HP-25. Since doing division first can result in non-integer results, the final result is rounded to the nearest integer. This routine does work for the case C(355,167), returning a value of 3.0443588e99. Incidentially, the HP-11C also works for this case, returning a value of 3.044358e99. There is a possibility that the final rounding does not produce the correct result, but all the cases I've tested it with seem to work fine so far. The P(n,r) routine uses the identity P(n,r) = n x (n-1) x (n-2) x ... x (n-r+1). No divisions required here, so the result is always an integer. There is no limitation on the values of n and r, as long as P(n,r) is less than 1e100. For example, P(5000,27) is calculated to be 6.9446225e99. To use the C(n,r) routine, position the program counter at step 0 if it's not there already, key in n, hit enter, key in r and hit R/S. To use the P(n,r) routine, position the program counter at step 30 (GTO 30), key in n, hit enter, key in r and hit R/S. Enjoy, Eamonn.
[pre] ▼
07-29-2003, 03:12 PM
Sorry about the last post - used the wrong formatting code for the listing. This should be easier to read. Luiz, Victor, Here is a program for the HP-25 that calculates either C(n,r) or P(n,r) for all cases where C(n,r) and P(n,r) are less than 1e100. The program fits comfortably in the 49 steps of program memory available on the HP-25. I haven't tested these routines on an actual HP-25, but I have tested them on the simulator found on this museums HP-25 page. The C(n,r) routine is based on the algorithm described by Victor. It makes use of the identity C(n,r) = C(n,n-r), selecting the minimum value of r and n-r for the calculations. In the loop body, the division is done first, to avoid overflows in cases where the intermediate calculations exceed the dynamic range of the HP-25. Since doing division first can result in non-integer results, the final result is rounded to the nearest integer. This routine does work for the case C(355,167), returning a value of 3.0443588e99. Incidentially, the HP-11C also works for this case, returning a value of 3.044358e99. There is a possibility that the final rounding does not produce the correct result, but all the cases I've tested it with seem to work fine so far. The P(n,r) routine uses the identity P(n,r) = n x (n-1) x (n-2) x ... x (n-r+1). No divisions required here, so the result is always an integer. There is no limitation on the values of n and r, as long as P(n,r) is less than 1e100. For example, P(5000,27) is calculated to be 6.9446225e99. To use the C(n,r) routine, position the program counter at step 0 if it's not there already, key in n, hit enter, key in r and hit R/S. To use the P(n,r) routine, position the program counter at step 30 (GTO 30), key in n, hit enter, key in r and hit R/S. Enjoy, Eamonn.
01 sto 0 ; X=r, Y=n. Store r in R0
▼
07-30-2003, 03:00 AM
try C(90,7). It should be 7471375560, but your program returns (probably) 7471375562, if you would have done the ▼
07-30-2003, 08:50 PM
Werner, I don't have a HP-25 at hand, but I calculated C(90,7) on a HP-11C, using the algorithm implemented in my original program. It gives a result of 7471375562, as you expected, which is incorrect. When I checked my program on the HP-25 simulator I didn't come across any failure cases. This seems to be because of the 17 digits of percision that the simulator uses. On the simulator, the program I wrote does return the correct value of C(90,7) = 7471375560. I had a look at the programs that you wrote for the HP-41 and now I see how you very elegantly avoided the overflow that can occur with the intermediate calculations. Here is a version of your HP-41 program for the HP-25. It will not overflow for C(n,r) < 1e100 and should return the correct value for C(n,r) < 1e10. It does not preserve the Z register, as your program does, but then again the HP-25 instruction set isn't nearly as powerful as the HP-41 instruction set. It requires the use of several registers, but uses your method to calculate the minimum of r and n-r to save a couple of steps. There's still room to have both this program and the other program that calculates P(n,r) in the 49 steps of HP-25 program memory. Regards, Eamonn.
01 - ; X=n-r
07-29-2003, 05:50 PM
I'm not a statistical power user but my 32SII returns 1,6712 e 105 for C(355,167) and my 11C flashes with 9,999999 99 as a result.
07-31-2003, 01:48 AM
Hi all; I read the posts in this thread again and I can tell you, if you allow me so: if I am the teacher and these are your answers for the task, I'd never feel more proud for them! I'm impressed. I think that dealing with "restrictions" is teasing, and dealing with resourceful equipment may be confusing. Using different resources and combining their power so you can achieve results is sometimes a matter of "taste" and specific knowledge. On the other hand, using all available resources that are not enough to accomplish the task without an specific "treatment" and find a clever "way out" with them is way beyond "taste" and specific knowledge. I'm amazed. Best regards. Luiz (Brazil)
07-29-2003, 08:08 AM
heres another idea. also misses 2 & 3. a bit of a
LBL "FOO" |
