From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me
X-Spam-Level: 
X-Spam-Status: No, score=-0.9 required=5.0 tests=BAYES_00,FORGED_GMAIL_RCVD,
	FREEMAIL_FROM autolearn=no autolearn_force=no version=3.4.4
X-Google-Thread: 103376,9dfc10efb95ba130
X-Google-NewGroupId: yes
X-Google-Attributes: gida07f3367d7,domainid0,public,usenet
X-Google-Language: ENGLISH,ASCII
Path: 
 g2news1.google.com!postnews.google.com!a4g2000prm.googlegroups.com!not-for-mail
From: Rick <rickduley@gmail.com>
Newsgroups: comp.lang.ada
Subject: Re: Inefficient algorithms
Date: Sat, 11 Sep 2010 18:53:58 -0700 (PDT)
Organization: http://groups.google.com
Message-ID: <48279012-6325-47c7-a8a6-8c1dee19a20a@a4g2000prm.googlegroups.com>
References: 
 <1f6f73cd-f5ff-4408-a1d7-c9ca7dfa70ee@m35g2000prn.googlegroups.com>
 <Pine.LNX.4.64.1009111612280.19046@medsec1.medien.uni-weimar.de>
NNTP-Posting-Host: 122.110.165.254
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
X-Trace: posting.google.com 1284256438 1401 127.0.0.1 (12 Sep 2010 01:53:58
 GMT)
X-Complaints-To: groups-abuse@google.com
NNTP-Posting-Date: Sun, 12 Sep 2010 01:53:58 +0000 (UTC)
Complaints-To: groups-abuse@google.com
Injection-Info: a4g2000prm.googlegroups.com; posting-host=122.110.165.254;
 posting-account=q18aiAoAAADbiIPIlD5R8oYVGhuoBvVA
User-Agent: G2/1.0
X-HTTP-UserAgent: Mozilla/4.0 (compatible; MSIE 8.0; Windows NT 5.1;
 Trident/4.0; GTB6.5; .NET CLR 2.0.50727; .NET CLR 3.0.4506.2152;
 .NET CLR 3.5.30729),gzip(gfe)
Xref: g2news1.google.com comp.lang.ada:14019
Date: 2010-09-11T18:53:58-07:00
List-Id: <comp.lang.ada>

Hi Stefan

I have a couple of problems with this algorithm:

> But if you really need (worst-case) exponential time, here is such an
> algorithm for for factoring a number n (or for detecting if n is prime):
>
> function Factor(C: Positive) return (Positive or "is prime") is
> =A0 -- pre C>1
> begin
> =A0 for I in 2 .. C-1 loop
> =A0 =A0 if I divides C then
> =A0 =A0 =A0 return I
> =A0 =A0 end if
> =A0 end loop
> =A0 return "is prime"
> end Factor;

1.  This algorithm depends on a single loop.  As I understand loops,
the worst case scenario is C-2 iterations.  That is to say the
algorithm is linear i.e. O(n).

2. How can I write a function which returns a 'choice' of type?  All I
can think of is some trick with discriminate record.