Prime number finder HP11C?

[jbhp55]

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.

[Valentin Albillo]

.
Hi, jbhp55:

(06-13-2016 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.
[...]
I'd like to know if any of the many features can improve my prime finding program.

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 prime-finder 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 HP-11C 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 HP-11C program here and we'll see if it can be meaningfully improved.

V.
.

[jbhp55]

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.

[TASP]

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,

[Valentin Albillo]

.
Hi again, jbhp55:

(06-14-2016 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:

01 LBL C
02 STO 1
[...]
23 +
24 GTO C

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 length-optimized program is 22 steps long.

I'll refrain from spoiling the fun by posting it here right now, to give you the chance to re-examine 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.
.

[jbhp55]

I don't see it, please enlighten me!

[Valentin Albillo]

.
Hi, jbhp55:

(06-16-2016 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 HP-11C 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.
.

[jbhp55]

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.

[Gerson W. Barbosa]

(06-17-2016 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!
For this program, mine takes 38 seconds to find 1009 if I start it at 999.

The faster 11C has been modified for double speed. Yours is an original one.

http://www.hpmuseum.org/cgi-sys/cgiwrap/...read=78272

Speedwise, the HP-15C 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 HP-15C 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.

[jbhp55]

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.

[Dieter]

(06-17-2016 09:41 AM)Gerson W. Barbosa Wrote:  

(06-17-2016 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!
For this program, mine takes 38 seconds to find 1009 if I start it at 999.

...
Speedwise, the HP-15C 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.

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

[Gerson W. Barbosa]

(06-17-2016 06:42 PM)Dieter Wrote:  

(06-17-2016 09:41 AM)Gerson W. Barbosa Wrote:  ...
Speedwise, the HP-15C 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.

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. ;-)

Well, I said 'better', not 'the best'. With built-in NEXTP five more primes are reached, up to 1091, perhaps more with fresh batteries (2.6V here).

Gerson.

[bshoring]

I took your original program and modified it to work on an HP-38C. But if you ignore the key codes it should work just fine on a 12C or 11C. Of course on the HP-38C emulator (RPN-38 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

[Don Shepherd]

(06-17-2016 10:43 AM)jbhp55 Wrote:  Apparently, the equation solver can use efficient algorithms internally.

Can you list the equation you used on the 17bii?

[rprosperi]

(06-18-2016 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 re-keying the whole thing since there is no way to save it.

So, thanks Don!

[jbhp55]

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.

[jbhp55]

I see there are some smileys which replace meaningful text.

the first smiley should be ": D"

the second: ": P"

[Don Shepherd]

(06-19-2016 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

[jbhp55]

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.

[Don Shepherd]

(06-19-2016 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.