* Inefficient algorithms
@ 2010-09-11 4:24 Rick
2010-09-11 6:51 ` J-P. Rosen
` (3 more replies)
0 siblings, 4 replies; 23+ messages in thread
From: Rick @ 2010-09-11 4:24 UTC (permalink / raw)
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.
Thanks
^ permalink raw reply [flat|nested] 23+ messages in thread
* Re: Inefficient algorithms
2010-09-11 4:24 Inefficient algorithms Rick
@ 2010-09-11 6:51 ` J-P. Rosen
2010-09-13 3:45 ` Robert A Duff
2010-09-11 6:54 ` Niklas Holsti
` (2 subsequent siblings)
3 siblings, 1 reply; 23+ messages in thread
From: J-P. Rosen @ 2010-09-11 6:51 UTC (permalink / raw)
Le 11/09/2010 06:24, Rick a �crit :
> 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.
>
Not exactly what you asked for, but a very inefficient array sorting
algorithm:
Generate all possible permutations, and then select the one that is sorted.
It's O(n!) both in time and space...
--
---------------------------------------------------------
J-P. Rosen (rosen@adalog.fr)
Visit Adalog's web site at http://www.adalog.fr
^ permalink raw reply [flat|nested] 23+ messages in thread
* Re: Inefficient algorithms
2010-09-11 4:24 Inefficient algorithms Rick
2010-09-11 6:51 ` J-P. Rosen
@ 2010-09-11 6:54 ` Niklas Holsti
2010-09-11 7:07 ` Niklas Holsti
2010-09-11 14:28 ` stefan-lucks
2010-09-15 1:11 ` BrianG
3 siblings, 1 reply; 23+ messages in thread
From: Niklas Holsti @ 2010-09-11 6:54 UTC (permalink / raw)
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.
Perhaps the canonical example is this: you are given a Boolean formula
containing n Boolean variables. Find a valuation (a value, True or
False, for each variable) that makes the formula True. The O(2^n)
algorithm tries each of the 2^n valuations in some order, evaluates the
formula for this valuation, and stops when True.
In Ada, something like:
N : constant := ...;
type Valuation is array (1 .. N) of Boolean;
-- Valuation(k) is the value of Boolean variable number k.
function Formula (Inputs : Valuation) return Boolean
is begin
return <complex formula>;
end Formula;
The search through all possible valuations is logically like an n-deep
nested loop of the form
for Value1 in Boolean loop
for Value2 in Boolean loop
...
for Value_n in Boolean loop
if Formula ((Value1, Value2, ..., Value_n)) then
<exit and report success>.
end if;
end loop;
...
end loop;
end loop;
Since N is a variable, you cannot write out this N-deep loop nest in the
Ada program. Instead, use a recursive function that is given a partial
valuation, for example a valuation that gives the values for the
variables 1 .. k, and then extends the valuation by trying both False
and True values for variable k+1, calling itself recursively until it
has a full valuation, when it calls Formula to see if this full
valuation is a solution.
HTH,
--
Niklas Holsti
Tidorum Ltd
niklas holsti tidorum fi
. @ .
^ permalink raw reply [flat|nested] 23+ messages in thread
* Re: Inefficient algorithms
2010-09-11 6:54 ` Niklas Holsti
@ 2010-09-11 7:07 ` Niklas Holsti
2010-09-11 9:07 ` Rick
2010-09-11 9:20 ` Ludovic Brenta
0 siblings, 2 replies; 23+ messages in thread
From: Niklas Holsti @ 2010-09-11 7:07 UTC (permalink / raw)
Niklas Holsti wrote:
> 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.
>
> Perhaps the canonical example is this: you are given a Boolean formula
> containing n Boolean variables. Find a valuation (a value, True or
> False, for each variable) that makes the formula True.
Replying to myself, since I realize that I probably misunderstood your
need: what you want is an inefficient O(2^n) solution to an easy
(non-exponential) problem. The problem I suggested is not, of course, an
easy one. But it has easy variants. For example, require that the
Boolean formula uses at most 10 of the n variables, where this limit
(10) is considered a fixed number independent of the total number (n) of
variables.
--
Niklas Holsti
Tidorum Ltd
niklas holsti tidorum fi
. @ .
^ permalink raw reply [flat|nested] 23+ messages in thread
* Re: Inefficient algorithms
2010-09-11 7:07 ` Niklas Holsti
@ 2010-09-11 9:07 ` Rick
2010-09-11 15:05 ` Niklas Holsti
2010-09-11 9:20 ` Ludovic Brenta
1 sibling, 1 reply; 23+ messages in thread
From: Rick @ 2010-09-11 9:07 UTC (permalink / raw)
On Sep 11, 3:07 pm, Niklas Holsti <niklas.hol...@tidorum.invalid>
wrote:
> Niklas Holsti wrote:
> > 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.
>
> > Perhaps the canonical example is this: you are given a Boolean formula
> > containing n Boolean variables. Find a valuation (a value, True or
> > False, for each variable) that makes the formula True.
>
> Replying to myself, since I realize that I probably misunderstood your
> need: what you want is an inefficient O(2^n) solution to an easy
> (non-exponential) problem. The problem I suggested is not, of course, an
> easy one. But it has easy variants. For example, require that the
> Boolean formula uses at most 10 of the n variables, where this limit
> (10) is considered a fixed number independent of the total number (n) of
> variables.
>
> --
> Niklas Holsti
> Tidorum Ltd
> niklas holsti tidorum fi
> . @ .
I must be a bit daft, Niklas, but I don't get it.
What sort of a Boolean formula are you talking about? How do I use it
in a recursive function?
You help is appreciated.
Thanks
^ permalink raw reply [flat|nested] 23+ messages in thread
* Re: Inefficient algorithms
2010-09-11 7:07 ` Niklas Holsti
2010-09-11 9:07 ` Rick
@ 2010-09-11 9:20 ` Ludovic Brenta
2010-09-11 9:23 ` Ludovic Brenta
2010-09-11 11:20 ` Niklas Holsti
1 sibling, 2 replies; 23+ messages in thread
From: Ludovic Brenta @ 2010-09-11 9:20 UTC (permalink / raw)
Niklas Holsti <niklas.holsti@tidorum.invalid> writes:
> Niklas Holsti wrote:
>> 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.
>>
>> Perhaps the canonical example is this: you are given a Boolean
>> formula containing n Boolean variables. Find a valuation (a value,
>> True or False, for each variable) that makes the formula True.
>
> Replying to myself, since I realize that I probably misunderstood your
> need: what you want is an inefficient O(2^n) solution to an easy
> (non-exponential) problem. The problem I suggested is not, of course,
> an easy one. But it has easy variants. For example, require that the
> Boolean formula uses at most 10 of the n variables, where this limit
> (10) is considered a fixed number independent of the total number (n)
> of variables.
Actually I do think that the problem is trivial and that you can solve
it without recursion. If you see your array of Booleans as a number in
binary representation:
procedure Inefficient (N : in Natural) is
subtype Valuation is Natural range 1 .. 2**N;
-- We assume the solution is Valuation'Last but it could be any value.
Solution : constant Valuation := Valuation'Last;
begin
for K in Valuation'Range loop
exit when K = Solution;
end loop;
end Inefficient;
--
Ludovic Brenta.
^ permalink raw reply [flat|nested] 23+ messages in thread
* Re: Inefficient algorithms
2010-09-11 9:20 ` Ludovic Brenta
@ 2010-09-11 9:23 ` Ludovic Brenta
2010-09-11 11:20 ` Niklas Holsti
1 sibling, 0 replies; 23+ messages in thread
From: Ludovic Brenta @ 2010-09-11 9:23 UTC (permalink / raw)
I just wrote on comp.lang.ada:
> Niklas Holsti <niklas.holsti@tidorum.invalid> writes:
>> Niklas Holsti wrote:
>>> 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.
>>>
>>> Perhaps the canonical example is this: you are given a Boolean
>>> formula containing n Boolean variables. Find a valuation (a value,
>>> True or False, for each variable) that makes the formula True.
>>
>> Replying to myself, since I realize that I probably misunderstood your
>> need: what you want is an inefficient O(2^n) solution to an easy
>> (non-exponential) problem. The problem I suggested is not, of course,
>> an easy one. But it has easy variants. For example, require that the
>> Boolean formula uses at most 10 of the n variables, where this limit
>> (10) is considered a fixed number independent of the total number (n)
>> of variables.
>
> Actually I do think that the problem is trivial and that you can solve
> it without recursion. If you see your array of Booleans as a number in
> binary representation:
>
> procedure Inefficient (N : in Natural) is
>
> subtype Valuation is Natural range 1 .. 2**N;
Make that 0 .. 2**N, of course.
> -- We assume the solution is Valuation'Last but it could be any value.
> Solution : constant Valuation := Valuation'Last;
> begin
> for K in Valuation'Range loop
> exit when K = Solution;
> end loop;
> end Inefficient;
Granted, a decent optimizing compiler might grab victory from the jaws
of defeat in this case :)
--
Ludovic Brenta.
^ permalink raw reply [flat|nested] 23+ messages in thread
* Re: Inefficient algorithms
2010-09-11 9:20 ` Ludovic Brenta
2010-09-11 9:23 ` Ludovic Brenta
@ 2010-09-11 11:20 ` Niklas Holsti
2010-09-11 18:29 ` Peter C. Chapin
1 sibling, 1 reply; 23+ messages in thread
From: Niklas Holsti @ 2010-09-11 11:20 UTC (permalink / raw)
Ludovic Brenta wrote:
> Niklas Holsti <niklas.holsti@tidorum.invalid> writes:
>> Niklas Holsti wrote:
>>> 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.
>>> Perhaps the canonical example is this: you are given a Boolean
>>> formula containing n Boolean variables. Find a valuation (a value,
>>> True or False, for each variable) that makes the formula True.
>> Replying to myself, since I realize that I probably misunderstood your
>> need: what you want is an inefficient O(2^n) solution to an easy
>> (non-exponential) problem. The problem I suggested is not, of course,
>> an easy one. But it has easy variants. For example, require that the
>> Boolean formula uses at most 10 of the n variables, where this limit
>> (10) is considered a fixed number independent of the total number (n)
>> of variables.
>
> Actually I do think that the problem is trivial and that you can solve
> it without recursion. If you see your array of Booleans as a number in
> binary representation:
>
> procedure Inefficient (N : in Natural) is
>
> subtype Valuation is Natural range 1 .. 2**N;
That will of course fail to compile when N grows large enough, as it
will when we are talking of order-of-complexity questions. (Also, I
think you really wanted the range 0 .. 2**N - 1, giving the N-bit binary
numbers).
> -- We assume the solution is Valuation'Last but it could be any value.
> Solution : constant Valuation := Valuation'Last;
> begin
> for K in Valuation'Range loop
> exit when K = Solution;
Here you are assuming that the Boolean formula has the simple form
Var1 = K1 and Var2 = K2 and Var3 = K3 and ... Var<N> = K<N>
where K1..K<N> are the Boolean constants that correspond to the constant
bits in your Solution. I had in mind a more general formula where, for
example, we can compare two variables (Var1 = Var4), negate variables,
and so on.
In the terms of my first post, this algorithm would be:
-- The formula for which a solution is sought:
function Formula (Input : Valuation) return Boolean
is begin
return <a complex Boolean formula depending on the N bits
in the Input parameter>;
end Formula;
-- The search for the solution:
for K in Valuation loop
exit when Formula (K);
end loop;
A trivial amount of code, indeed, but since Valuation has 2**N values,
the loop will iterate 2**N times, so this algorithm is also O(2**N), as
for the recursive one.
This example is just the Boolean satisfiability problem (SAT), a
well-known difficult problem, which is not trivial in the general case.
--
Niklas Holsti
Tidorum Ltd
niklas holsti tidorum fi
. @ .
^ permalink raw reply [flat|nested] 23+ messages in thread
* Re: Inefficient algorithms
2010-09-11 4:24 Inefficient algorithms Rick
2010-09-11 6:51 ` J-P. Rosen
2010-09-11 6:54 ` Niklas Holsti
@ 2010-09-11 14:28 ` stefan-lucks
2010-09-12 1:04 ` Wilson
2010-09-12 1:53 ` Rick
2010-09-15 1:11 ` BrianG
3 siblings, 2 replies; 23+ messages in thread
From: stefan-lucks @ 2010-09-11 14:28 UTC (permalink / raw)
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! ------
^ permalink raw reply [flat|nested] 23+ messages in thread
* Re: Inefficient algorithms
2010-09-11 9:07 ` Rick
@ 2010-09-11 15:05 ` Niklas Holsti
2010-09-17 5:26 ` Rick
0 siblings, 1 reply; 23+ messages in thread
From: Niklas Holsti @ 2010-09-11 15:05 UTC (permalink / raw)
Rick wrote:
> On Sep 11, 3:07 pm, Niklas Holsti <niklas.hol...@tidorum.invalid>
> wrote:
>> Niklas Holsti wrote:
>>> 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.
>>> Perhaps the canonical example is this: you are given a Boolean formula
>>> containing n Boolean variables. Find a valuation (a value, True or
>>> False, for each variable) that makes the formula True.
>> Replying to myself, since I realize that I probably misunderstood your
>> need: what you want is an inefficient O(2^n) solution to an easy
>> (non-exponential) problem. The problem I suggested is not, of course, an
>> easy one. But it has easy variants. For example, require that the
>> Boolean formula uses at most 10 of the n variables, where this limit
>> (10) is considered a fixed number independent of the total number (n) of
>> variables.
>>
>> --
>> Niklas Holsti
>> Tidorum Ltd
>> niklas holsti tidorum fi
>> . @ .
>
> I must be a bit daft, Niklas, but I don't get it.
> What sort of a Boolean formula are you talking about?
For example, in Ada, with N = 4:
type Bool_Valuation is array (1 .. 4) of Boolean;
function Formula (Input : Bool_Valuation) return Boolean
is
begin
return Input(1)
and Input(2) /= Input (4)
and (Input(3) or (Input(1) and Input(4)))
and (Input(2) /= Input(1));
end Formula;
The problem is to find some value of the Input parameter (that is, 4
Boolean values, one each for Input(1), Input(2), Input(3), and Input(4))
such that Formula (Input) returns True. One solution is (True, False,
False, True).
In real applications of the Boolean satisfiability problem, the number
of variables can be huge (thousands or millions, I believe -- it keeps
increasing year by year). In real applications the Formula would
typically not be written out in Ada, as in the above example, but would
be given as input to the program and represented by some data structure.
The brute-force exponential algorithm is to try all possible values of
the Input parameter. There are 2**4 = 16 such values in the example.
> How do I use it in a recursive function?
The recursion is just used to enumerate (go through) all possible values
of the Input parameter when (as in the general case) the length of the
Input vector is some variable N. The idea is to first enumerate all
values of Input where Input(1) = False, and then (if no solution was
found yet) enumerate all values of Input where Input(1) = True. To
enumerate all Inputs where Input(1) has a given value, a recursive call
is used to enumerate all the values of the rest of the Input, which is
Input(2..N). The recursion ends when it is trying a value for Input(N),
and then it just calls Formula (Input); if the result is True, this
value of Input is a solution.
I have placed example Ada code at http://www.tidorum.fi/soldem.zip.
But I repeat, this problem is a hard one, for which it is not easy to
find more efficient general solutions, unless you know something more
about the formula. For example, if you know that it uses at most 10
variables (not all the N variables), you can inspect the formula to find
which 10 variables it uses and then limit the search to all the possible
values of these 10 variables, giving a constant 2**10 number of choices
instead of the general 2**N.
--
Niklas Holsti
Tidorum Ltd
niklas holsti tidorum fi
. @ .
^ permalink raw reply [flat|nested] 23+ messages in thread
* Re: Inefficient algorithms
2010-09-11 11:20 ` Niklas Holsti
@ 2010-09-11 18:29 ` Peter C. Chapin
0 siblings, 0 replies; 23+ messages in thread
From: Peter C. Chapin @ 2010-09-11 18:29 UTC (permalink / raw)
On 2010-09-11 07:20, Niklas Holsti wrote:
> This example is just the Boolean satisfiability problem (SAT), a
> well-known difficult problem, which is not trivial in the general case.
Indeed, SAT is NP-complete. I believe it may have been the first problem
proved to be NP-complete (not sure). So if P /= NP as many people
suspect, there is no polynomial time way of solving SAT.
Peter
^ permalink raw reply [flat|nested] 23+ messages in thread
* Re: Inefficient algorithms
2010-09-11 14:28 ` stefan-lucks
@ 2010-09-12 1:04 ` Wilson
2010-09-12 1:53 ` Rick
1 sibling, 0 replies; 23+ messages in thread
From: Wilson @ 2010-09-12 1:04 UTC (permalink / raw)
To: stefan-lucks
I'm not sure if this is what you are looking for or not. How about
printing out all permutations of the first n integers? The algorithm is
in many texts along with an explanation. See, for example:
http://en.wikipedia.org/wiki/Permutation
I'm also don't know which 2**n algorithm is simplest to write or
understand, but there are literally thousands of problems that meet this
criteria. By the way, none of these problems are strictly speaking
"inefficient". Instead, they are just "computationally tedious"(My
term)! (I am taking inefficient to mean that a faster algorithm exits.)
In many of these problems (such as printing all the permutations) a faster
algorithm is impossible. On the other hand, NP-Complete problems such as
the binary problem discussed in some of the other posts have no known
faster solution; i.e., a faster solution might exist, but we have no proof.
Good luck which ever way you choose to go.
--- news://freenews.netfront.net/ - complaints: news@netfront.net ---
^ permalink raw reply [flat|nested] 23+ messages in thread
* Re: Inefficient algorithms
2010-09-11 14:28 ` stefan-lucks
2010-09-12 1:04 ` Wilson
@ 2010-09-12 1:53 ` Rick
2010-09-12 8:35 ` Georg Bauhaus
2010-09-12 11:56 ` stefan-lucks
1 sibling, 2 replies; 23+ messages in thread
From: Rick @ 2010-09-12 1:53 UTC (permalink / raw)
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).
2. How can I write a function which returns a 'choice' of type? All I
can think of is some trick with discriminate record.
^ permalink raw reply [flat|nested] 23+ messages in thread
* Re: Inefficient algorithms
2010-09-12 1:53 ` Rick
@ 2010-09-12 8:35 ` Georg Bauhaus
2010-09-12 11:56 ` stefan-lucks
1 sibling, 0 replies; 23+ messages in thread
From: Georg Bauhaus @ 2010-09-12 8:35 UTC (permalink / raw)
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;
^ permalink raw reply [flat|nested] 23+ messages in thread
* Re: Inefficient algorithms
2010-09-12 1:53 ` Rick
2010-09-12 8:35 ` Georg Bauhaus
@ 2010-09-12 11:56 ` stefan-lucks
1 sibling, 0 replies; 23+ messages in thread
From: stefan-lucks @ 2010-09-12 11:56 UTC (permalink / raw)
[-- Attachment #1: Type: TEXT/PLAIN, Size: 2025 bytes --]
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! ------
^ permalink raw reply [flat|nested] 23+ messages in thread
* Re: Inefficient algorithms
2010-09-11 6:51 ` J-P. Rosen
@ 2010-09-13 3:45 ` Robert A Duff
0 siblings, 0 replies; 23+ messages in thread
From: Robert A Duff @ 2010-09-13 3:45 UTC (permalink / raw)
"J-P. Rosen" <rosen@adalog.fr> writes:
> Not exactly what you asked for, but a very inefficient array sorting
> algorithm:
> Generate all possible permutations, and then select the one that is sorted.
> It's O(n!) both in time and space...
Here's an even slower method: Generate all possible array
values, and select the one that is sorted and is a permutation
of the input.
;-)
- Bob
^ permalink raw reply [flat|nested] 23+ messages in thread
* Re: Inefficient algorithms
2010-09-11 4:24 Inefficient algorithms Rick
` (2 preceding siblings ...)
2010-09-11 14:28 ` stefan-lucks
@ 2010-09-15 1:11 ` BrianG
3 siblings, 0 replies; 23+ messages in thread
From: BrianG @ 2010-09-15 1:11 UTC (permalink / raw)
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.
>
> Thanks
Um, after reading all the responses to date, I don't uderstand what's so
hard about coming up with an _IN_efficient example. I'd think any first
year programming class ought to provide at least one good example.
How about:
-------------------------------------------------------------------------------
-- Bad_Sort.Ada - Example of O(n^2) code
-------------------------------------------------------------------------------
with Ada.Text_IO, Ada.Integer_Text_IO;
use Ada.Text_IO, Ada.Integer_Text_IO;
procedure Bad_Sort is
type My_Array is array (Natural range <>) of Integer;
function Sort (This : My_Array) return My_Array is
Input : My_Array := This;
Result : My_Array (This'first..This'last);
Min, Index : Integer;
begin
for I in Result'range loop
Min := Integer'last;
Index := Input'first-1;
for J in Input'range loop
if Input(J) < Min then
Min := Input(J);
Index := J;
end if;
end loop;
Result(I) := Min;
if Index >= Input'first then
Input(Index) := Integer'last;
end if;
end loop;
return Result;
end Sort;
--
Test : My_Array := (1, 3, 2, 5, 7, 4, 9, 8, 6, 0);
Answ : My_Array := Sort(Test);
begin
Put("Input: ");
for I in Test'range loop
Put(Test(I));
end loop;
New_Line;
Put("Output:");
for I in Answ'range loop
Put(Answ(I));
end loop;
New_Line;
end Bad_Sort;
(of course, this is an O(n^2) implementation; maybe that's not what you
meant :-)
^ permalink raw reply [flat|nested] 23+ messages in thread
* Re: Inefficient algorithms
@ 2010-09-15 8:51 Rick
2010-09-15 21:45 ` John B. Matthews
0 siblings, 1 reply; 23+ messages in thread
From: Rick @ 2010-09-15 8:51 UTC (permalink / raw)
Thanks BrianG but I was chasing O(2^n).
^ permalink raw reply [flat|nested] 23+ messages in thread
* Re: Inefficient algorithms
2010-09-15 8:51 Rick
@ 2010-09-15 21:45 ` John B. Matthews
2010-09-16 12:05 ` Chad R. Meiners
2010-09-17 5:24 ` Rick
0 siblings, 2 replies; 23+ messages in thread
From: John B. Matthews @ 2010-09-15 21:45 UTC (permalink / raw)
In article
<18f4ae08-3112-4f98-bb69-b76ebae6d2b2@p37g2000pra.googlegroups.com>,
Rick <rickduley@gmail.com> wrote:
> Thanks BrianG but I was chasing O(2^n).
The traditional recursive Fibonacci algorithm is exponential in n.
<http://courses.csail.mit.edu/6.01/spring07/lectures/lecture4.pdf>
--
John B. Matthews
trashgod at gmail dot com
<http://sites.google.com/site/drjohnbmatthews>
^ permalink raw reply [flat|nested] 23+ messages in thread
* Re: Inefficient algorithms
2010-09-15 21:45 ` John B. Matthews
@ 2010-09-16 12:05 ` Chad R. Meiners
2010-09-16 20:19 ` John B. Matthews
2010-09-17 5:24 ` Rick
1 sibling, 1 reply; 23+ messages in thread
From: Chad R. Meiners @ 2010-09-16 12:05 UTC (permalink / raw)
On Sep 15, 5:45 pm, "John B. Matthews" <nos...@nospam.invalid> wrote:
> In article
> <18f4ae08-3112-4f98-bb69-b76ebae6d...@p37g2000pra.googlegroups.com>,
>
> Rick <rickdu...@gmail.com> wrote:
> > Thanks BrianG but I was chasing O(2^n).
>
> The traditional recursive Fibonacci algorithm is exponential in n.
>
> <http://courses.csail.mit.edu/6.01/spring07/lectures/lecture4.pdf>
>
> --
> John B. Matthews
> trashgod at gmail dot com
> <http://sites.google.com/site/drjohnbmatthews>
And it is a nice example of an inefficient algorithm that can be made
efficient.
^ permalink raw reply [flat|nested] 23+ messages in thread
* Re: Inefficient algorithms
2010-09-16 12:05 ` Chad R. Meiners
@ 2010-09-16 20:19 ` John B. Matthews
0 siblings, 0 replies; 23+ messages in thread
From: John B. Matthews @ 2010-09-16 20:19 UTC (permalink / raw)
In article
<82880e4e-46a5-4c11-a6d4-a68cda551819@q26g2000vbn.googlegroups.com>,
"Chad R. Meiners" <chad.rmeiners@gmail.com> wrote:
> On Sep 15, 5:45 pm, "John B. Matthews" <nos...@nospam.invalid> wrote:
> > In article
> > <18f4ae08-3112-4f98-bb69-b76ebae6d...@p37g2000pra.googlegroups.com>,
> >
> > Rick <rickdu...@gmail.com> wrote:
> > > Thanks BrianG but I was chasing O(2^n).
> >
> > The traditional recursive Fibonacci algorithm is exponential in n.
> >
> > <http://courses.csail.mit.edu/6.01/spring07/lectures/lecture4.pdf>
>
> And it is a nice example of an inefficient algorithm that can be made
> efficient.
Moreover, the computation can be made more efficient in several
illustrative ways:
1. Iteration, having complexity O(n) and requiring memory O(1)
2. Closed form, having complexity O(1) and requiring memory O(1)
<http://en.wikipedia.org/wiki/Fibonacci_number>
3. Memoization, having complexity O(n) and requiring memory O(n)
<http://www.itl.nist.gov/div897/sqg/dads/HTML/memoize.html>
--
John B. Matthews
trashgod at gmail dot com
<http://sites.google.com/site/drjohnbmatthews>
^ permalink raw reply [flat|nested] 23+ messages in thread
* Re: Inefficient algorithms
2010-09-15 21:45 ` John B. Matthews
2010-09-16 12:05 ` Chad R. Meiners
@ 2010-09-17 5:24 ` Rick
1 sibling, 0 replies; 23+ messages in thread
From: Rick @ 2010-09-17 5:24 UTC (permalink / raw)
Thank you John B Matthews.
That set of lecture notes was very useful.
^ permalink raw reply [flat|nested] 23+ messages in thread
* Re: Inefficient algorithms
2010-09-11 15:05 ` Niklas Holsti
@ 2010-09-17 5:26 ` Rick
0 siblings, 0 replies; 23+ messages in thread
From: Rick @ 2010-09-17 5:26 UTC (permalink / raw)
Thanks Niklas Holsti.
Thank you especially for taking the time to provide me with example
code.
You have been very helpful.
^ permalink raw reply [flat|nested] 23+ messages in thread
end of thread, other threads:[~2010-09-17 5:26 UTC | newest]
Thread overview: 23+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2010-09-11 4:24 Inefficient algorithms Rick
2010-09-11 6:51 ` J-P. Rosen
2010-09-13 3:45 ` Robert A Duff
2010-09-11 6:54 ` Niklas Holsti
2010-09-11 7:07 ` Niklas Holsti
2010-09-11 9:07 ` Rick
2010-09-11 15:05 ` Niklas Holsti
2010-09-17 5:26 ` Rick
2010-09-11 9:20 ` Ludovic Brenta
2010-09-11 9:23 ` Ludovic Brenta
2010-09-11 11:20 ` Niklas Holsti
2010-09-11 18:29 ` Peter C. Chapin
2010-09-11 14:28 ` stefan-lucks
2010-09-12 1:04 ` Wilson
2010-09-12 1:53 ` Rick
2010-09-12 8:35 ` Georg Bauhaus
2010-09-12 11:56 ` stefan-lucks
2010-09-15 1:11 ` BrianG
-- strict thread matches above, loose matches on Subject: below --
2010-09-15 8:51 Rick
2010-09-15 21:45 ` John B. Matthews
2010-09-16 12:05 ` Chad R. Meiners
2010-09-16 20:19 ` John B. Matthews
2010-09-17 5:24 ` Rick
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox