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.3 required=5.0 tests=BAYES_00, REPLYTO_WITHOUT_TO_CC 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!news4.google.com!feeder.news-service.com!newsfeed.straub-nv.de!news-1.dfn.de!news.dfn.de!news.uni-weimar.de!not-for-mail From: stefan-lucks@see-the.signature Newsgroups: comp.lang.ada Subject: Re: Inefficient algorithms Date: Sun, 12 Sep 2010 13:56:28 +0200 Organization: Bauhaus-Universitaet Weimar Message-ID: References: <1f6f73cd-f5ff-4408-a1d7-c9ca7dfa70ee@m35g2000prn.googlegroups.com> <48279012-6325-47c7-a8a6-8c1dee19a20a@a4g2000prm.googlegroups.com> Reply-To: stefan-lucks@see-the.signature NNTP-Posting-Host: medsec1.medien.uni-weimar.de Mime-Version: 1.0 Content-Type: MULTIPART/MIXED; BOUNDARY="8323584-1408986433-1284291945=:29891" X-Trace: tigger.scc.uni-weimar.de 1284285267 14012 141.54.178.228 (12 Sep 2010 09:54:27 GMT) X-Complaints-To: news@tigger.scc.uni-weimar.de NNTP-Posting-Date: Sun, 12 Sep 2010 09:54:27 +0000 (UTC) X-X-Sender: lucks@medsec1.medien.uni-weimar.de In-Reply-To: <48279012-6325-47c7-a8a6-8c1dee19a20a@a4g2000prm.googlegroups.com> Content-ID: Xref: g2news1.google.com comp.lang.ada:14022 Date: 2010-09-12T13:56:28+02:00 List-Id: This message is in MIME format. The first part should be readable text, while the remaining parts are likely unreadable without MIME-aware tools. --8323584-1408986433-1284291945=:29891 Content-Type: TEXT/PLAIN; CHARSET=ISO-8859-1 Content-Transfer-Encoding: 8BIT Content-ID: On Sat, 11 Sep 2010, 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. As I understand loops, > the worst case scenario is C-2 iterations. That is to say the > algorithm is linear i.e. O(n). No, n is the number of bits required to store C. So the algorithm is exponential in the input size, which is what one usually counts. > 2. How can I write a function which returns a 'choice' of type? All I > can think of is some trick with discriminate record. Think of an underlying application. One application might be a test if C is prime. You need a function Is_Prime(C: Positive) return Boolean. Replace "return I" by "return False". Another application may actually as for the smallest positive factor of C (except for 1). In that case, you could "return C" instead of "return 'is prime'". Instead of returning something, one may also call a subprogram: type Callback_1 is access procedure (Candidate: Positive); type Callback_2 is access procedure (Candidate, Factor: Positive); procedure Factor(C: Positive; Found_A_Factor: Callback_2; Is_Prime: Callback_1) is -- pre C>1 begin for I in 2 .. C-1 loop if I divides C then Found_A_Factor(Candidate => C, Factor => I); return; end if; end loop; Is_Prime(C); return; end Factor; -- ------ Stefan Lucks -- Bauhaus-University Weimar -- Germany ------ Stefan dot Lucks at uni minus weimar dot de ------ I love the taste of Cryptanalysis in the morning! ------ --8323584-1408986433-1284291945=:29891--