arun@dsrgsun.ces.cwru.edu (Arun Lakhotia) (01/12/89)
Talking about efficiency of perfect number generation programs. The
one that I had posted earlier is about 6000 times faster than the best
of others posted on the net. What follows is a comparison of 3
programs and the reason behind the differences.
CLASSIFICATION
--------------
All programs posted were of generate and test type. They may be
classified in three categories (P1, P2, and P3) on the basis of the
algorithm they use for:
generation of numbers upto 'N'
A) generate all integers, or -- O(N)
B) generate powers of 2 -- O(log2(N))
testing for 'perfect'-ness of some number 'M'
C) get list of divisors by dividing from 1..M//2, or -- O(M)
D) or by dividing from 1.. sqrt(M), or -- O(sqrt(M))
E) check for primeness by dividing from 1..sqrt(M) -- O(sqrt(M))
Programs\Algo used --> generate test O(generate * test)
v
P1 A C O(N * N)
P2 A D O(N * sqrt(N))
P3 B E O(log2(N) * sqrt(N))
My program belonged to category P3
NOTE: The above complexity measures do not include complexities due to
unification, choice-points creation. They are just algorithmic
complexities.
SOME FIGURES
------------
Following are run times for 3 program instances of these categories
for running under two popular Prolog systems on a Sun 3/60.
All times are in SECONDS. The figures for P3 are averaged over 1000
iterations for accuracy. Others are over 2, 5, 10 iterations depending
on how much patience they required.
Prolog System I
N --> 496 8128 33550336 Beyond
P1 32.78 Stack Overflow
P2 12.99 740.89 Patience Overflow
P3 0.0083 0.01501 0.066 Arithmetic Overflow
Prolog System II
N --> 496 8128 33550336 Beyond
P1 12.5 Stack Overflow
P2 0.66 30.525 Patience Overflow
P3 0.0031 0.0056 0.025 Arithmetic Overflow
THE PROGRAM
-----------
Theorems posted by Dale Miller provide a foundation for developing P3
type programs.
My program had scope for further improvement. (Re: Saumya Debray's
posting on improvement of efficiency of 'isprime').
Arun
PS: Let's move on to some other program :-)dave@quintus.uucp (David Bowen) (01/14/89)
/* There seems to be some suggestion that the question of perfect numbers has been worked to death. Not so! Previous programs have used the theorem: > if (2^p-1) is a (mersenne) prime > then (2^p-1) * 2^(p-1) is a perfect number. The program below makes use of the fact that there are not many values of p for which 2^p-1 is a prime, and the first 24 of them are listed in Knuth's "The Art of Computer Programming", Volume 2. (Look in the index under "Mersenne primes".) These values of p are tabulated below. This program uses the Quintus library package "long" to handle the large integers which are involved. I'm sorry to say that it runs up against a current limitation in "long" that exponents over 9999 are not allowed. All the same, it does manage to generate 22 perfect numbers, the last of which is a 5985 digit number (if I counted correctly). That number (p=9941) took 199.5 seconds to generate on a Sun-3/60. The first 12 numbers, with the times taken to generate them on a Sun-3/60, are: 6 [P=2, 0.017 sec] 28 [P=3, 0.033 sec] 496 [P=5, 0.033 sec] 8128 [P=7, 0.017 sec] 33550336 [P=13, 0.016 sec] 8589869056 [P=17, 0.033 sec] 137438691328 [P=19, 0.017 sec] 2305843008139952128 [P=31, 0.033 sec] 2658455991569831744654692615953842176 [P=61, 0.033 sec] 191561942608236107294793378084303638130997321548169216 [P=89, 0.033 sec] 13164036458569648337239753460458722910223472318386943117783728128 [P=107, 0.050 sec] 14474011154664524427946373126085988481573677491474835889066354349131199152128 [P=127, 0.100 sec] */ :- ensure_loaded(library(long)). % for eval/[1,2], portray_number/1 portray(N) :- portray_number(N). perfect_numbers :- mersenne_prime_exponent(P), statistics(runtime, [T0|_]), eval((2^P)-1, M), % M = 2^P-1 is a Mersenne prime eval(M*(2^(P-1)), N), % N = M*2^(P-1) statistics(runtime, [T1|_]), Time is T1 - T0, format('~p~n[P=~p, ~3D sec]~n~n', [N, P, Time]), fail. perfect_numbers. mersenne_prime_exponent(2). mersenne_prime_exponent(3). mersenne_prime_exponent(5). mersenne_prime_exponent(7). mersenne_prime_exponent(13). mersenne_prime_exponent(17). mersenne_prime_exponent(19). mersenne_prime_exponent(31). mersenne_prime_exponent(61). mersenne_prime_exponent(89). mersenne_prime_exponent(107). mersenne_prime_exponent(127). mersenne_prime_exponent(521). mersenne_prime_exponent(607). mersenne_prime_exponent(1279). mersenne_prime_exponent(2203). mersenne_prime_exponent(2281). mersenne_prime_exponent(3217). mersenne_prime_exponent(4253). mersenne_prime_exponent(4423). mersenne_prime_exponent(9689). mersenne_prime_exponent(9941). mersenne_prime_exponent(11213). mersenne_prime_exponent(19937).