Prime number finder HP11C?

06132016, 07:15 PM
Post: #1




Prime number finder HP11C?
I'm sure I am 30 odd years too late with this topic, but I am curious to know if it is possible to write a shorter program for the 11C which finds the next prime number. I only recently bought an 11C, and I like it very much. I'd like to know if any of the many features can improve my prime finding program.
The conditions are: start with odd number in x, start program (say A). The first prime number equal or greater than the entered number is displayed (after some time, of course). Push R/S and the next number is shown. The program steps count. A final RTN may be omitted. No entry of any registers before execution should be necessary. I have discovered that the 11C is very much slower than a 48G (no surprise), but my last program was 10% faster than the previous. 

06132016, 11:09 PM
Post: #2




RE: Prime number finder HP11C?
.
Hi, jbhp55: (06132016 07:15 PM)jbhp55 Wrote: I am curious to know if it is possible to write a shorter program for the 11C which finds the next prime number. It would help if you first post here your best attempt, then we'll see if it can be improved. There are two possible optimizations for a primefinder program (or most any program for that matter): a) optimize for size: the shortest program possible but not the fastest one. b) optimize for speed: the fastest program but longer than option (a) above. and of course some compromise: not the shortest but not the fastest either. The HP11C is indeed a wonderful calculator, I used one while in Africa courtesy of an old friend of mine and it performed flawlessly. I still have it with me to this day, 36+ years later, and it looks and works as new. Again: post your HP11C program here and we'll see if it can be meaningfully improved. V. . All My Articles & other Materials here: Valentin Albillo's HP Collection 

06142016, 06:33 AM
Post: #3




RE: Prime number finder HP11C?
Thank you, Valentin, for your reply.
My program: 01 LBL C 02 STO 1 03 1 04 STO 2 05 LBL 7 06 2 07 STO + 2 08 RCL 1 09 RCL 2 10 / 11 FRAC 12 x=0 13 GTO 8 14 LST X 15 RCL 2 16 x<= y 17 GTO 7 18 RCL 1 19 R/S 20 LBL 8 21 RCL 1 22 2 23 + 24 GTO C I didn't get it smaller by working on stack only, nor by using register I. I had with flags, but it was 2 lines longer. Best regards, J. 

06142016, 11:35 PM
Post: #4




RE: Prime number finder HP11C?
Runs on my Sammy Galaxy app just fine (tweaked a tad).
Fun to watch the primes drift by as the program takes longer and longer and longer to find them, 2speed HP41CX,int2XMEM+ZEN, HPIL+DEVEL, HPIL+X/IO, I/R, 82143, 82163, 82162 25,35,45,55,65,67,70,80 

06152016, 10:59 PM
(This post was last modified: 06162016 02:19 AM by Valentin Albillo.)
Post: #5




RE: Prime number finder HP11C?
.
Hi again, jbhp55: (06142016 06:33 AM)jbhp55 Wrote: Thank you, Valentin, for your reply. You're welcome. Quote:The conditions are: start with odd number in x, start program (say A). I assume that by "start program (say A)" you mean that you start the program either by pressing the [A] key in USER mode or else pressing [GSB][A] in any mode (though you actually use LBL C in your program, not LBL A). Quote:The program steps count. A final RTN may be omitted. I assume you're interested in the shortest program possible which meets your specified requirements, not the fastest one. Quote:My program: Subject to the aforementioned assumptions and requirements, a cursory glance at your code reveals that there's a fairly trivial technique which saves 2 steps, i.e. the lengthoptimized program is 22 steps long. I'll refrain from spoiling the fun by posting it here right now, to give you the chance to reexamine your code and find it out yourself, but if you'd rather see it immediately just ask and I'll post it. Best regards. V. . All My Articles & other Materials here: Valentin Albillo's HP Collection 

06162016, 07:56 PM
Post: #6




RE: Prime number finder HP11C?
I don't see it, please enlighten me!


06162016, 10:22 PM
Post: #7




RE: Prime number finder HP11C?
.
Hi, jbhp55: (06162016 07:56 PM)jbhp55 Wrote: I don't see it, please enlighten me! Ok, here we go. As I said, a trivial technique will shorten your program by 2 steps. The crux of the matter has to do with code relocation. Your program begins with 01 LBL C, then enters a loop at 05 LBL 7 to try each potential divisor in turn (implicitly up to the square root of the number). If one is found the number can't be prime so it branches to 20 LBL 8 which generates the next odd number to be tested for primality and then it simply branches back to 01 LBL C to repeat the whole procedure with the new number. If the loop at 04 LBL 7 exhausts all potential divisors without finding one, the number is prime so it's recalled to the display and execution stops at 19 R/S, so once the user takes note and presses [R/S] to find the next prime number the program simply falls through the next step, which is 20 LBL 8, to generate the next odd number and proceed as explained before. So far so good. Now, to optimize the length of the program the key idea is this: there's no need for the main entry point LBL C to be at step 01 because when you start your program by either pressing [C] in USER mode or else [GSB][C] in any mode, the HP11C will automatically search through the code for LBL C and once found it will immediately start execution there, whether LBL C is located at step 01 or at step 05, say. With this in mind, we now rearrange the code, essentially moving before LBL C the instructions from LBL 8 to the end of the code, like this: 01 LBL 8 02 RCL 1 03 2 04 + 05 LBL C 06 STO 1 07 1 08 STO 2 09 LBL 7 10 2 11 STO + 2 12 RCL 1 13 RCL 2 14 / 15 FRAC 16 x=0 17 GTO 8 18 LST X 19 RCL 2 20 x<= y 21 GTO 7 22 RCL 1 where the original GTO C instruction has been deleted, as 05 LBL C is now the very next instruction after LBL 8, RCL 1, 2, +, and the original R/S instruction has also been deleted after 22 RCL 1 because the end of program memory acts like an implicit stop/return instruction and the program will thus stop there by itself, leaving the program counter at the top of program memory (step 000), so once the user takes note of the newly found prime and presses [R/S] the execution will continue from step 01 which is LBL 8, exactly as it did in your original code. This way the rearranged code works exactly like your original code did before but is only 22 steps long instead of 24. Best regards. V. . All My Articles & other Materials here: Valentin Albillo's HP Collection 

06172016, 07:08 AM
Post: #8




RE: Prime number finder HP11C?
Hi Valentin,
thank you for your very instructive post. This is a useful technique, especially for more complex programs. Thank you for teaching me! If there are more programs in memory, one extra GTO would be required, which would still leave the program one step shorter than the original. I wonder if anyone can make a shorter program which satisfies the conditions. Also, I'm interested in the speed of this program on an 11C. I found somewhere in the forum archive a post with speeds for many different calculators, and there were two results for the 11c; I checked, and mine was two times slower! For this program, mine takes 38 seconds to find 1009 if I start it at 999. Best regards, Jaap. 

06172016, 09:41 AM
Post: #9




RE: Prime number finder HP11C?
(06172016 07:08 AM)jbhp55 Wrote: Also, I'm interested in the speed of this program on an 11C. I found somewhere in the forum archive a post with speeds for many different calculators, and there were two results for the 11c; I checked, and mine was two times slower! The faster 11C has been modified for double speed. Yours is an original one. http://www.hpmuseum.org/cgisys/cgiwrap/...read=78272 Speedwise, the HP15C LE is way better: about 150 time faster, which means it takes no more than one fourth of a second to find 1009 in your example. 01 LBL A 02 MATRIX 1 03 STO 0 04 LBL 7 05 2 06 STO + 1 07 RCL 0 08 RCL / 1 09 FRAC 10 x=0 11 GTO 8 12 LST X 13 RCL 1 14 x<= y 15 GTO 7 16 RCL 0 17 R/S 18 LBL 8 19 2 20 RCL + 0 21 GTO A 999 GSB A > 1009 R/S > 1013 R/S > 1019 R/S > 1021 ... The HP15C version might be made even shorter by using Valentin's technique. I learned the MATRIX 1 trick in line 2 from him, BTW. Regards, Gerson. 

06172016, 10:43 AM
Post: #10




RE: Prime number finder HP11C?
Hello Gerson,
that explains it! I am not the happy owner of a 15c (LE), but I found to my surprise that the humble HP20S takes only 3 s. for the 999  1009 step, using virtually the same code. My 32SII is only very slightly faster (this I can understand in view of the processor). My fastest option is a 48G, which I haven't tried with an equivalent program, but a similar program takes roughly one second. For the 17BII, I only have an equation which states whether or not a number is prime. It verifies 1009 a lot quicker than the 20S (10,007 in 2 s. on the 17BII, and 4 s. on the 20S). Apparently, the equation solver can use efficient algorithms internally. Best regards, Jaap. 

06172016, 06:42 PM
Post: #11




RE: Prime number finder HP11C?
(06172016 09:41 AM)Gerson W. Barbosa Wrote:(06172016 07:08 AM)jbhp55 Wrote: Also, I'm interested in the speed of this program on an 11C. I found somewhere in the forum archive a post with speeds for many different calculators, and there were two results for the 11c; I checked, and mine was two times slower!... FWIW: I keyed the original program without any optimizations into a (real hardware) WP34s. Since the result appeared virtually immediately I replaced the R/S with a VIEW instruction. Within one second the 34s computed nine (!) primes up to 1051, even with the slight slowdown caused by VIEW. So it's about 0.1 s on average. I doubt there is a faster classic RPN calculator around. ;) Dieter 

06172016, 07:36 PM
Post: #12




RE: Prime number finder HP11C?
(06172016 06:42 PM)Dieter Wrote:(06172016 09:41 AM)Gerson W. Barbosa Wrote: ... Well, I said 'better', not 'the best'. With builtin NEXTP five more primes are reached, up to 1091, perhaps more with fresh batteries (2.6V here). Gerson. 

06182016, 07:23 PM
Post: #13




RE: Prime number finder HP11C?
I took your original program and modified it to work on an HP38C. But if you ignore the key codes it should work just fine on a 12C or 11C. Of course on the HP38C emulator (RPN38 CX) it is super fast.
This program works two ways: 1. If X contains 0 or a negative number, the program will display all prime numbers until you press R/S. A count is maintained in Y. 2. If X contains a positive integer, the program will return the corresponding prime value. For example: If X contains 5, the program will return the 5th prime number, which is 11. Always initialize by pressing g CLP in Run Mode, to reset the program counter. 01  0 0 02  33 x≷y 03  25 5 x≤y 04  34 CLx 05  21 3 STO 3 06  25 6 x=0 07  25 7 12 GTO 12 08  2 2 09  21 0 STO 0 10  3 3 11  25 7 20 GTO 20 12  1 1 13  31 ENTER 14  2 2 15  21 0 STO 0 16  25 4 PSE 17  31 ENTER 18  3 3 19  25 4 PSE 20  21 1 STO 1 21  1 1 22  21 2 STO 2 23  2 2 24  21 51 2 STO + 2 25  22 1 RCL 1 26  22 2 RCL 2 27  71 ÷ 28  25 61 FRAC 29  25 6 x=0 30  25 7 48 GTO 48 31  25 31 LASTx 32  22 2 RCL 2 33  25 5 x≤y 34  25 7 23 GTO 23 35  1 1 36  21 51 0 STO + 0 37  22 3 RCL 3 38  25 6 x=0 39  25 7 45 GTO 45 40  22 0 RCL 0 41  22 3 RCL 3 42  25 5 x≤y 43  25 7 52 GTO 52 44  25 7 48 GTO 48 45  22 0 RCL 0 46  22 1 RCL 1 47  25 4 PSE 48  2 2 49  22 1 RCL 1 50  51 + 51  25 7 20 GTO 20 52  2 2 53  22 3 RCL 3 54  25 5 x≤y 55  25 7 58 GTO 58 56  22 1 RCL 1 57  25 7 00 GTO 00 58  31 ENTER 59  31 ENTER 60  1 1 61  51 + 62  25 7 00 GTO 00 Regards, Bob 

06182016, 08:32 PM
Post: #14




RE: Prime number finder HP11C?  
06182016, 10:27 PM
Post: #15




RE: Prime number finder HP11C?
(06182016 08:32 PM)Don Shepherd Wrote: Can you list the equation you used on the 17bii? I was going to ask, but I know it means manually rekeying the whole thing since there is no way to save it. So, thanks Don! Bob Prosperi 

06192016, 01:14 PM
Post: #16




RE: Prime number finder HP11C?
Dear Don,
'the whole thing' is in fact quite short: 0xP+L(K:1)x0+PRIME=(L(C:1)C+SIGMA(D:3:SQRT(P)+1:2:IF(FP(P/D)<>0:1+L(C)x0+L(K:0)x0)))xK+PxK+L(P+2)x0 (SIGMA means the Greek capital, of course) Use: type starting number (must be odd), press P outcome is 0 if P is not a prime, otherwise P is given. Press PRIM to continue search. (new P is two higher than original) This equation has evolved and is not optimized for shortness. Also, I don't remember why C and K are output. The advanced guide for the 19B and 28C/S gives the way to suppress them (quite easy). The main algorithm is standard for the solver. It seems quite rough, as the search for a divisor is always continued up to the square root, but that is the consequence of the fact that you cannot branch out of a sum. Nevertheless, the search is quite quick, as I mentioned earlier. best regards, Jaap. 

06192016, 01:17 PM
Post: #17




RE: Prime number finder HP11C?
I see there are some smileys which replace meaningful text.
the first smiley should be ": D" the second: ": P" 

06192016, 02:55 PM
Post: #18




RE: Prime number finder HP11C?
(06192016 01:14 PM)jbhp55 Wrote: the search for a divisor is always continued up to the square root, but that is the consequence of the fact that you cannot branch out of a sum. You may not be able to branch out of a sigma loop, but you can stop the loop by performing an illegal operation. Here is an example of that. This is a solver equation that shows the prime factors of a number, one factor at a time. Enter the number you want to factor, then press N. Then press FACT. When it finds a factor, it performs an illegal operation (divide by 0) after storing the factor in FACT. The calculator will beep and display "SOLUTION NOT FOUND". You can then RCL FACT and it will show you the factor it found. Then press FACT to find the next factor, then RCL FACT when it displays the error message. It is done when it displays the last factor without you having to RCL it. IF(MOD(N:2)=0:L(FACT:2)+L(N:N\(\div\)2)\(\div\)0:\(\Sigma\)(I:3:SQRT(N):2:IF(MOD(N:I)=0:L(FACT:I)+L(N:N\(\div\)I)\(\div\)0:0))+N)FACT 

06192016, 05:35 PM
Post: #19




RE: Prime number finder HP11C?
Dear Don,
Thank you for teaching me another useful technique! As to the original post: anyone who can better 22 program lines for the 11C? Best regards, Jaap. 

06192016, 06:43 PM
Post: #20




RE: Prime number finder HP11C?
(06192016 05:35 PM)jbhp55 Wrote: Thank you for teaching me another useful technique! You are welcome, Jaap. I am not clever enough to have come up with this idea myself, I learned it from another fellow on this forum, Mike Engle, several years ago. Mike, are you still around? Interestingly, if you run this solver equation on the 19bii, you don't have to RCL FACT each time, it will automatically show you each factor as it displays the error message. And, it shows you the original number you started factoring at the beginning, too. Very nice. But if you ever want to write solver equations, especially complex ones, on the 19bii, be aware that there is a major gotcha: it will not store your equation if it has any errors in it. You must correct the error immediately, unlike the solver in the 17bii which goes on and stores your erroneous equation and lets you fix it later. 

« Next Oldest  Next Newest »

User(s) browsing this thread: 1 Guest(s)