HP41 Programming challange



#24

The challange is:

Write a program that lists primnumbers and there number (I don't know the correct english word for that, what I mean is, the primnumbers should be numbered or "counted").
The main challange is to write a program that is as fast as possible.

The program I wrote searches for a common divider of the number it is testing and the products of the primnumbers it has stored in registers.

Now what you should not do is store the products of primnumbers (that you would have to compute in another way or take out of a book) in registers before the program has found them.

At least not a whole lot of them, lets say you can use all primnumbers no greater than 20. My program takes 2, 3 and 5 as given primnumbers.

This is my program.

It is not perfect and there would still be something to optimize, anyway, it was good enough to beat the program my dad wrote, hehe.
It calculates the first 500 primnumbers in less than 2 hours. I will let you know the exact time as soon as I know (just started it).

Happy programming :)

Regards,
Harry (Germany)


#25

At the beginning the program is slowed down a lot by displaying the numbers by "PSE". This takes about 2.2 seconds per primnumber.


Sorry for my bad english, I hope you can read it anyway.

Regards,

Harry (Germany)

PS: 111 primnubers after 12 minutes. The 111th one is 607


#26

0h 06min: 068th 0337

0h 12min: 111th 0607

0h 32min: 249th 1579

0h 58min: 392th 2693

1h 16min: 482th 3449

1h 27min: 537th 3877

1h 30min: 552th 4003

now the "BAT" indicator has come on, I will have to restart with new Batteries or on the emulator, but then the speed won't be as it should be.

Regards,

Harry


#27

Harry,

I've got the old 67 plugged in the wall using a 49 line program adapted from Peter Henrici's book "Computational Analysis with the HP-25 Pocket Calculator". Later when I have more time I'll run in on my 32Sii. For the record the 67 took 20m 01s to reach the 73rd prime (starting out from 0), the number 359.

tm


#28

Could you post the program here so we can participate?

Cheers,
Victor


#29

Hi, Victor;

the program is listed in teh image below:

The image file can be also downloaded in the starting post. There is a link Harry posted.

Cheers.

Luiz (Brazil)

#30

I think Victor is referring to my post that I am using a 49 line program. I dont't know to how to type this out and then somehow post it into the Forum.

tm


#31

Hey, Trent;

I'm sorry; I thought that Victor was asking for Harry's listing; to be honest, I read his post and did not realise it followed yours. Please, forgive me.

About your post, is there anything I can I do for you? I'd gladly help you. If you list your 49-steps program in an HP97 printer or in an HP41's, scan the image and send it to me, I'll type it in for you. Is this what you need? I think I am the one that's confusing stuffs for good... 8*( Sorry!

Whatever you want, let me know. I'd be glad helping.

Best regards.

Luiz (Brazil)

Edited: 23 July 2003, 11:18 p.m.

#32

Prime number program:

001 LBL A 025 x=<y?
DSP 0 GTO 3
LBL 0 2
2 STO X 3
STO 3 1
1 030 STO - 3
STO 4 GTO 2
RCL 1 LBL 3
LBL 1 3
010 SQRT STO + 3
STO 2 RCL 4
LBL 2 CHS
RCL 2 STO 4
RCL 3 STO + 3
x>y? GTO 2
GTO 5 040 LBL 4
RCL 1 1
RCL 3 STO+ 1
DIVIDE GTO 0
020 FRAC LBL 5
x=0? RCL 1
GTO 4 PAUSE
RCL 3 1
024 4 STO + 7
049 GTO 4

tm


#33

I did't type in the program in this way. I can see now that this message board is NOT like a word processor! I will try to figure out what to do next.

tm


#34

Hihi, such are the dangers in this zoo...

Anyway, I guess you'd have to use [nl] for the line breaks, or enclose the entire listing betwenn [pre] and [/pre] tags.

Thanks anyway for your effort. Looking forward to keep my 25 busy...

Cheers, Victor

#35

Trent

On your post, click on Edit Message.

Put [PRE] before your listing.
Put [/PRE] after.

Type your password and press Save.

There's more info here

#36

Trent:

Is this what you intended?

001 LBL A     025 x=<y?
DSP 0 GTO 3
LBL 0 2
2 ST* 3
STO 3 1
1 030 ST- 3
STO 4 GTO 2
RCL 1 LBL 3
LBL 1 3
010 SQRT ST+ 3
STO 2 RCL 4
LBL 2 CHS
RCL 2 STO 4
RCL 3 ST+ 3
x>y? GTO 2
GTO 5 040 LBL 4
RCL 1 1
RCL 3 ST+ 1
/ GTO 0
020 FRAC LBL 5
x=0? RCL 1
GTO 4 PAUSE
RCL 3 1
024 4 ST+ 7
049 GTO 4

I have not verified the code or anything; I just reconstructed what appeared to be a multi-column original with line numbers.

Ocassionally skulking,

Bruce.


#37

Bruce,

You made my day, I was so frustrated. The program looks the way it should have been. I'm so greatful for your help. Just a note about line 48. As you see, this records the count that Harry in his original post asks for. So now everyone can test it out on different caluclators to give us the fastest run, and more importantly, shave off a few steps. If I have missed something please reply.

tm

#38

Ok, here's my version of the program. I've added a few lines to time the program (lines 06-08, 56 and 58-60), and also the possibility to provide a maximum number to test (say, you want all primes up to 1000).

If we remove the special case of '2' as a prime (by starting at 3 instead of 1), we can reduce the running time of the program by about 25% since we only need to test uneven numbers in this case.

To run it, you put the maximum number to test on the stack, and do an [XEQ] "PRIME1".

 01 LBL "PRIME1"
02 STO 06 ; last number to test
03 FIX 00 ; set display to show integers
04 CF 29 ; no decimal point
05 0

06 STOPSW ; start stopwatch (remove lines 06-08 if you
07 SETSW ; don't want to use the stopwatch)
08 RUNSW

10 STO 07
11 3
12 STO 01
13 LBL 00
14 2
15 STO 03
16 1
17 STO 04
18 RCL 01
19 SQRT
20 STO 02
21 LBL 02
22 RCL 02
23 RCL 03
24 X>Y?
25 GTO 05
26 RCL 01
27 RCL 03
28 /
29 FRC
30 X=0?
31 GTO 04
32 RCL 03
33 4
34 X<=Y?
35 GTO 03
36 2
37 ST* 03
38 1
39 ST- 03
40 GTO 02
41 LBL 03
42 3
43 ST+ 03
44 RCL 04
45 CHS
46 STO 04
47 ST+ 03
48 GTO 02
49 LBL 04
50 2 ; only uneven numbers (3, 5, 7, ...)
51 ST+ 01
52 RCL 06 ; loop if not maximum number
53 RCL 01
54 X<=Y?
55 GTO 00

56 STOPSW ; remove if no timing needed

57 SF 29 ; reset decimal flag

58 FIX 06 ; 6 decimal places to show time
59 RCLSW ; show expired time
60 VIEW X ; lines 58-60 can be removed if you
; don't want to time the program
61 STOP
62 LBL 05 ; show prime number
63 CLA
64 ARCL 01
65 AVIEW
66 1 ; count primes
67 ST+ 07
68 GTO 04
69 END

I haven't been able to test it on a real HP-41, since I sent mine back for replacement (it suffered from frequent memory losses, if you remember). I ran it in V41 though, where finding all primes up to 100 takes 41 s instead of 56 s.

Axel

Edited: 28 July 2003, 1:09 p.m.


#39

Testing only odd numbers is a good idea. My Program also does not test numbers that can be divided by 3. This is done by increasing the number by 2 and 4 like this:

5 +2

7 +4

11 +2

13 +4

17 +2

19 +4

23 +2

25 +4.....

Regards,
Harry


#40

Yes, I know. For this version I only made a simple change which could not negatively affect runtime through the additional required logic - the inner loop stayed the same excpet for the step width. I'm going to try to avoid numbers divisible by 3 (and perhaps 5) now.

Axel

#41

The 32SII is faster than the 67 and the 41 I think.

I would also transfer my program, but the 32 does not provide the 107 register it needs. At least if it is set up to compute all primnumbers up to 1E6.

I have adapted it to an HP48 wich is a lot faster.

Regards,

Harry


#42

Harry,

I haven't heard from you. Have you used the program that I posted after it was reformatted by Bruce?

tm


#43

Yes, I have tested it, although i did not fully understand it.
As I expected the speeddiffrence gets more significant with bigger numbers. The 29C I programmed it into was at #1500 after 2 days.

Regards, Harry


#44

Well, the program works much the same way you suggested. Although it tests ALL number for primality, it only tests each number against a sequence of numbers avoiding multiples of 3, up to the square root of the original number (since 4 * 6 = 6 * 4 = 24). The sequence is as follows:

 2  3  5                      ; lines 23-31
+1 +2

7 11 13 17 19 23 ... ; lines 32-39
+2 +4 +2 +4 +2 +4 +2 ...

I hope this clarifies things a bit.

Axel

Edited: 28 July 2003, 3:30 p.m.


#45

Yes, I see it now. To be honest, I did not spend too much time on analysing it. But now I did.

Regards,
Harry

#46

My program also stops when it reaches the square root of the number that is beeing tested. Thats why I had to store the biggest prime number that is in the product in addition to the product itself.
The disadvantage of my program is 1st its length (It is twice as long as the other one) and second its need for memory. It needs 108 registers if I want to search for primnumbers up to 1E6.

Regards,
Harry


Possibly Related Threads...
Thread Author Replies Views Last Post
  Custom Programming vs. Pre-packaged programming Eddie Shore 3 526 01-24-2005, 03:42 AM
Last Post: Karl Schneider
  hp41 programming questions Fulcrum 5 531 04-25-2004, 06:34 PM
Last Post: Miki Mihajlovic
  HP41 programming. Howard 4 510 02-04-2003, 09:28 AM
Last Post: Johnny Billquist
  RPN/RPL and the HP41 Programming Language Vieira, Luiz C. (Brazil) 3 469 11-10-2001, 02:56 PM
Last Post: Andrés C. Rodríguez (Argentina)
  An HP 17BII equation challange for all who love problem solving using a calculator Mike Burns 8 772 02-23-2001, 02:55 PM
Last Post: Dave Hicks

Forum Jump: