Path: utzoo!attcan!uunet!lll-winken!ames!mailrus!cwjcc!arun@dsrgsun.ces.cwru.edu
From: arun@dsrgsun.ces.cwru.edu (Arun Lakhotia)
Newsgroups: comp.lang.prolog
Subject: Perfect Numbers, Complexity
Message-ID: <377@cwjcc.CWRU.Edu>
Date: 12 Jan 89 08:11:04 GMT
Sender: news@cwjcc.CWRU.Edu
Reply-To: arun@dsrgsun.ces.cwru.edu (Arun Lakhotia)
Organization: Case Western Reserve University
Lines: 71

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