Prime numbers
danfan
and wrote an workable algorithm to generate them in REXX.
Getting interested I extended my efforts and trimmed my program
to generete prime numbers from 2 - 99991 in an hour and half.
I used a rather straight forward method, and I realise there must
be more intelligent algorithms available.
Do you have any suggestions, examples written in REXX?
/DG
Barry Mann
Lots of computer and intellectual time has been spent on the problem.
Years ago I saw a clever mechanical trick that used written tables of
numbers and a tricky scheme to walk through the list and cast out non
primes. Unfortunately, I don't recall how it worked or if it was truly
general or lent itself to being programmed.
For your REXX program you can use the following hints to reduce the number
of trials.
Easy and obvious:
1): The largest possible divisor you need to try is the square root of the
number being tested.
2): Skip all even numbers and numbers ending in "5".
3): Your trial divisors should come from the list of primes you've already
found.
Not so easy:
4): When optimizing this sort of task use the 90/10 rule. 10% of your code
uses 90% of the process time. Therefore, you need to spend your
intellectual time fussing with only 10% of the code to reap large
execution time benefits.
5): If you plan to repeatedly work with a large list of primes, you'll
save processor time by generating a working list of primes and storing
them in a disk file. Generating the list could take days, weeks, months,
or more. With some extra logic (part of the 90% of your code that won't
impact execution speed) you could run the program in the background or
over night and on weekends. On command or at a specific time the program
would quit. Next time the program would continue where it left off.
We had a mainframe modeling program that ran two years in this
intermittent fashion on a two processor system. We would start the program
around midnight when the operator went to lunch. For the first hour or so
the modeling program would be a pig and use all the system resources it
could reach. Finally it would settle down, take over the second processor
and quietly chew on its matrix for the rest of the night. We would run I/O
intensive programs and hardly notice the modeling program was running. We
could book almost two hours of computer use per hour of wall clock time.
-----------------------------------------------------------
nite...@voicenet.com (Barry Mann)
-----------------------------------------------------------
Juergen Kehr
I don't know if my algorithm is fast (I don't think so), but when I
tested it on a quite old P133 PC it cost me about 3 minutes with WinREXX
to generate the prime numbers up to 99991. Here you may get my
procedure:
/* REXX */
arg lastno
tab. = 0
do n = 3 to lastno by 2
if tab.n = 1 then
do
iterate n
end
else
do
say n 'is a prime number'
do k = 1 while k * n <= lastno
x = k * n
tab.x = 1
end
end
end
exit
The funny thing with this procedure is, that it's speed depends on the
last prime number you want to calculate. As larger this number is, as
slower the procedure is mainly in the starting phase.
In my opinion I think it's a funny example for working with stem
variables in REXX.
Kind regards.
danfan schrieb:
> I had a need for a list of prime numbers
> and wrote an workable algorithm to generate them in REXX.
>
> Getting interested I extended my efforts and trimmed my program
> to generete prime numbers from 2 - 99991 in an hour and half.
>
> I used a rather straight forward method, and I realise there must
> be more intelligent algorithms available.
> Do you have any suggestions, examples written in REXX?
> /DG
___________________________________________________________
Freundliche Gruesse
Dipl.-Math. Juergen Kehr
Senior Consultant
rubin Software GmbH
Tel. +49-511-463050
Fax +49-511-463055
Mobil +49-172-5129389
e-Mail KehrJ...@t-online.de
KehrJ...@netscape.net
KehrJ...@csi.com
Fax -> e-Mail +49-40-3603022846
___________________________________________________________
Carl Byington
In article <75j1se$51a$1...@zingo.tninet.se>, nfy...@tninet.se says...
>
>I had a need for a list of prime numbers
>and wrote an workable algorithm to generate them in REXX.
>
>Getting interested I extended my efforts and trimmed my program
>to generete prime numbers from 2 - 99991 in an hour and half.
>
>I used a rather straight forward method, and I realise there must
>be more intelligent algorithms available.
>Do you have any suggestions, examples written in REXX?
The following program generates all the primes between 2 and 99991
in 6 seconds on a PII/300 running NT4 and Quercus rexx.
say time()
parse arg lim
last = 0
primes. = 0
do i = 2 to lim
if primes.i = 0 then do
last = i
do j = i*2 to lim by i
primes.j = 1
end
end
end
say 'highest prime less than' lim 'is' last
say time()
- --
PGP key available from the key servers.
Key fingerprint 95 F4 D3 94 66 BA 92 4E 06 1E 95 F8 74 A8 2F A0
-----BEGIN PGP SIGNATURE-----
Version: 4.5
iQCVAgUBNn2DNtZjPoeWO7BhAQEukAQAnroDqO5L2Au6ZgNGainHHjusWZf7ZOwg
c3xFNlp9YafYzppdmYGXT3d5yB8prz+7yJikeAjWWhoWsgPNqNNk0iPCsZm7azQt
BF4Y1sqZysFfD8ZnwHJ8lZZPi1btdW+ihLHDrzx6vYCSb7SQv8imz+OcETngse4t
BULAsEYXnkE=
=MzUs
-----END PGP SIGNATURE-----
Ian Collier
>I don't know if my algorithm is fast (I don't think so), but when I
>tested it on a quite old P133 PC it cost me about 3 minutes with WinREXX
>to generate the prime numbers up to 99991.
The algorithm is known as the Sieve of Eratosthenes and is an efficient
way to produce a list of all prime numbers below a certain number (actually
the Sieve conceptually goes on forever but then you probably don't want
to wait for it to produce the results. (-: ).
To be pedantic, the program as you supplied it should start with
say "2 is a prime number" since you start testing at 3. Here is
a slimmed down version of it which I find runs in about 35% of
the time though your mileage may vary. The main advantage is
using "do ... by ..." instead of performing a multiplication at
each step; also I'm not checking off the even multiples as we know
they are not prime. :-)
/* REXX */
arg lastno
say '2 is a prime number'
prime. = 1
do n = 3 to lastno by 2
if prime.n then do
say n 'is a prime number'
do k = n to lastno by n+n
prime.k = 0
end
end
end
Oddly, REXX/imc and Regina both take 38 seconds to run this program with
argument 99991 on my P150 even though Regina runs rexxcps 2.6 times as
fast.
--
---- Ian Collier : i...@comlab.ox.ac.uk : WWW page (including REXX section):
------ http://www.comlab.ox.ac.uk/oucl/users/ian.collier/imc.html
New to this group? Answers to frequently-asked questions can be had from
http://rexx.hursley.ibm.com/rexx/ .
Juergen Kehr
good work.
I never thought that there is no chance for faster solutions. When I wrote the
procedure something reminds me that this is an often used algorithm, but I
can't remember what its name was, thank you for clarifing this.
BTW: I'm glad that such a small procedure could be an entertainment :-)
Kind regards.
Ian Collier schrieb:
--