Perfect Numbers, Complexity 
Author Message
 Perfect Numbers, Complexity

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 :-)



Fri, 19 Jun 1992 08:11:00 GMT  
 Perfect Numbers, Complexity
/*

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:

Quote:
>   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).



Fri, 19 Jun 1992 09:08:00 GMT  
 
 [ 2 post ] 

 Relevant Pages 

1. New user need help with perfect numbers.

2. Perfect Numbers

3. Perfect Numbers

4. ASM to test Perfect Number

5. Finding perfect numbers

6. Perfect Number

7. Yet another perfect number program

8. Yet another perfect number program

9. perfect numbers

10. Numbers Numbers Numbers

11. Perfect example of why subclassing can be dangerous...

12. Golf - The perfect problem to compare languages with?

 

 
Powered by phpBB® Forum Software