Max of Concave List...And The Winner Is....

*To*: mathgroup at smc.vnet.net*Subject*: [mg13016] Max of Concave List...And The Winner Is....*From*: "Chris Farr" <farr at brown.edu>*Date*: Tue, 30 Jun 1998 00:26:13 -0400*Sender*: owner-wri-mathgroup at wolfram.com

Math Group: Thanks for all of your help in finding the maximum of a list which is concave. I tested the speed of 3 algorithms sent in on a list of values yielded by a quadratic function. In short, in terms of speed, "The Bisection Method" won with "The Binary Search Method" coming in a close second. Here is the list: x = Table[40000*x+-(1/2)*x^2,{x,1,80000}]; The position of the list at the optimum is 40,000 (half way on the grid of 80,000). Here is the list from slowest to fastest (the code for each algorithm is below)... "Max[x]" ==>3.35 seconds Catch-Throw Method" ==> 1.93 seconds "Binary Search Method" ==> 0.05 seconds "The Bisection Method" ==> 0. seconds "Max[x]" Max[x] "Catch-Throw Method" e=First[x]; Catch[Scan[If[#<e,Throw[e],e=#]&,Rest[x]]] "Binary Search Method" (While[Length[x]>1,i=Floor[Length[x]/2]; If[x[[i]]<= x[[i+1]],x=Take[x,-Length[x]+i];,x=Take[x,i];]]; First[x]) "The Bisection Method" concaveMax[li_]:= Module[{a=1,b=Length[li]}, While[b-a>1, With[{n=Quotient[b+a,2]}, If[li[[n]]==li[[n+1]],Return[li[[n]]]]; If[li[[n]]<li[[n+1]],a=n+1,b=n]]]; Max[li[[a]],li[[b]]]]