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=-1.9 required=5.0 tests=BAYES_00 autolearn=ham
	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-7-bit
Path: 
 g2news1.google.com!news3.google.com!feeder2.cambriumusenet.nl!feed.tweaknews.nl!85.158.31.10.MISMATCH!newsfeed-0.progon.net!progon.net!newsfeed.ision.net!newsfeed2.easynews.net!ision!newsfeed.arcor.de!newsspool2.arcor-online.net!news.arcor.de.POSTED!not-for-mail
Date: Sun, 12 Sep 2010 10:35:50 +0200
From: Georg Bauhaus <rm-host.bauhaus@maps.futureapps.de>
User-Agent: Mozilla/5.0 (Macintosh; U; Intel Mac OS X 10.6; en-US;
 rv:1.9.2.9) Gecko/20100825 Thunderbird/3.1.3
MIME-Version: 1.0
Newsgroups: comp.lang.ada
Subject: Re: Inefficient algorithms
References: 
 <1f6f73cd-f5ff-4408-a1d7-c9ca7dfa70ee@m35g2000prn.googlegroups.com>
 <Pine.LNX.4.64.1009111612280.19046@medsec1.medien.uni-weimar.de>
 <48279012-6325-47c7-a8a6-8c1dee19a20a@a4g2000prm.googlegroups.com>
In-Reply-To: 
 <48279012-6325-47c7-a8a6-8c1dee19a20a@a4g2000prm.googlegroups.com>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Message-ID: <4c8c90e6$0$6880$9b4e6d93@newsspool2.arcor-online.net>
Organization: Arcor
NNTP-Posting-Date: 12 Sep 2010 10:35:50 CEST
NNTP-Posting-Host: 245fb3ab.newsspool2.arcor-online.net
X-Trace: 
 DXC=kVV:8K1LcFVU6b:FjPaGjQA9EHlD;3YcR4Fo<]lROoRQ8kF<OcfhCO[K^FkDNidX^^BhmZ<nLOhK[fGa209ZXUC_g5;LIDDF[2S
X-Complaints-To: usenet-abuse@arcor.de
Xref: g2news1.google.com comp.lang.ada:14020
Date: 2010-09-12T10:35:50+02:00
List-Id: <comp.lang.ada>

On 9/12/10 3:53 AM, Rick wrote:
> 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
>>    -- pre C>1
>> begin
>>    for I in 2 .. C-1 loop
>>      if I divides C then
>>        return I
>>      end if
>>    end loop
>>    return "is prime"
>> end Factor;
>
> 1.  This algorithm depends on a single loop.

I think the above function wasn't meant to be the completed solution
of "find all (prime) factors of a number".  Also, I'd count the
steps it takes the computer to perform the operations inside
the loop.


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

Doesn't have to be a choice of types, just choice might be enough.

       type Positive_Or_Is_Prime is private;

       subtype Greater_Than_1 is Positive range 1+1 .. Positive'Last;

       function To_Positive_Or_Is_Prime
	(P : Positive) return Positive_Or_Is_Prime;
       function To_Greater_Than_1
         (X : Positive_Or_Is_Prime) return Greater_Than_1;
       function Is_Prime (X : Positive_Or_Is_Prime) return Boolean;

    private
       type Positive_Or_Is_Prime is range 1 .. Positive'Last;
       Is_Prime_Number : constant Positive_Or_Is_Prime := 1;