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