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-7-bit
Path: 
 g2news1.google.com!news4.google.com!feeder.news-service.com!feeder.erje.net!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: Sat, 11 Sep 2010 16:28:20 +0200
Organization: Bauhaus-Universitaet Weimar
Message-ID: <Pine.LNX.4.64.1009111612280.19046@medsec1.medien.uni-weimar.de>
References: 
 <1f6f73cd-f5ff-4408-a1d7-c9ca7dfa70ee@m35g2000prn.googlegroups.com>
Reply-To: stefan-lucks@see-the.signature
NNTP-Posting-Host: medsec1.medien.uni-weimar.de
Mime-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
X-Trace: tigger.scc.uni-weimar.de 1284207977 22185 141.54.178.228 (11 Sep 2010
 12:26:17 GMT)
X-Complaints-To: news@tigger.scc.uni-weimar.de
NNTP-Posting-Date: Sat, 11 Sep 2010 12:26:17 +0000 (UTC)
X-X-Sender: lucks@medsec1.medien.uni-weimar.de
In-Reply-To: 
 <1f6f73cd-f5ff-4408-a1d7-c9ca7dfa70ee@m35g2000prn.googlegroups.com>
Xref: g2news1.google.com comp.lang.ada:14014
Date: 2010-09-11T16:28:20+02:00
List-Id: <comp.lang.ada>

On Fri, 10 Sep 2010, Rick wrote:

> I am working on a class in algorithmic efficiency and, to make a
> point, need an algorithm that runs O(2^n) - a factoring algorithm
> perhaps.  All I can find is 'C' code I can't decipher.  Can someone
> please help with an Ada example.

Technically,all polynomial-time algorithms are in O(2^n), since the 
"big-Oh" means something like "not faster than". 

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;

This is pseudo-code with an Ada-like syntax, and shouldn't be hard to 
translate into Ada. (Hey, this is *your* homework!)

Note that if C is a prime, this the loop iterates C-2=Theta(C) times. If C 
is an n-bit prime, the number of iterations is 
   2**(log_2(C)) - 2  >  2**(n-1) - 2.

-- 
------ Stefan Lucks   --  Bauhaus-University Weimar  --   Germany  ------
               Stefan dot Lucks at uni minus weimar dot de
------  I  love  the  taste  of  Cryptanalysis  in  the  morning!  ------