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!  ------