▼
Posts: 52
Threads: 11
Joined: Jan 1970
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)
▼
Posts: 52
Threads: 11
Joined: Jan 1970
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
▼
Posts: 52
Threads: 11
Joined: Jan 1970
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
▼
Posts: 406
Threads: 47
Joined: Jul 2005
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
▼
Posts: 182
Threads: 9
Joined: Jun 2013
Could you post the program here so we can participate?
Cheers,
Victor
▼
Posts: 4,027
Threads: 172
Joined: Aug 2005
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)
Posts: 406
Threads: 47
Joined: Jul 2005
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
▼
Posts: 4,027
Threads: 172
Joined: Aug 2005
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.
Posts: 406
Threads: 47
Joined: Jul 2005
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
▼
Posts: 406
Threads: 47
Joined: Jul 2005
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
▼
Posts: 182
Threads: 9
Joined: Jun 2013
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
Posts: 155
Threads: 5
Joined: Jan 1970
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
Posts: 180
Threads: 23
Joined: Apr 2012
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.
▼
Posts: 406
Threads: 47
Joined: Jul 2005
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
Posts: 30
Threads: 4
Joined: Jan 1970
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.
▼
Posts: 52
Threads: 11
Joined: Jan 1970
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
▼
Posts: 30
Threads: 4
Joined: Jan 1970
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
Posts: 52
Threads: 11
Joined: Jan 1970
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
▼
Posts: 406
Threads: 47
Joined: Jul 2005
Harry,
I haven't heard from you. Have you used the program that I posted after it was reformatted by Bruce?
tm
▼
Posts: 52
Threads: 11
Joined: Jan 1970
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
▼
Posts: 30
Threads: 4
Joined: Jan 1970
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.
▼
Posts: 52
Threads: 11
Joined: Jan 1970
Yes, I see it now. To be honest, I did not spend too much time on analysing it. But now I did.
Regards,
Harry
Posts: 45
Threads: 7
Joined: Jan 1970
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
|
