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

• To: mathgroup at smc.vnet.net
• Subject: [mg13120] Re: Max of Concave List...And The Winner Is....
• From: Robert Knapp <rknapp>
• Date: Tue, 7 Jul 1998 03:44:23 -0400
• Organization: Wolfram Research, Inc.
• References: <6n9pf9\$a2v@smc.vnet.net>
• Sender: owner-wri-mathgroup at wolfram.com

```Chris Farr wrote:
>
> 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]]]]

Max takes so long is that it does not know anything about the structure
of your list.  Another more subtle reason Max takes so long is that in
version 3.0, it is optimized to find the maximum of a list of  elements
which are numeric quantities (things like Sqrt[2], Pi), but are  not
represented in  the system.

In the current development version, we have developed better technology
for recognizing lists of numbers, so Max operates much faster than
before on a list of numbers:

In[1]:=
x = Table[40000*x+-(1/2)*x^2,{x,1,80000}]; Timing[Max[x]]

(Version 3.0.1) Out[1]= {5.76 Second, 800000000}  (Development Version)
Out[1]= {0.29 Second, 800000000}

This is quite a bit faster.  However, if your list consists entirely of
approximate machine numbers (or integers), the speed increase is even
greater:

In[2]:=
nx = Table[40000.*x+-.5*x^2,{x,1.,80000.}]; Timing[Max[nx]]

8 (Version 3.0.1) Out[2]=
{2.31 Second, 8. 10 }
8 (Development Version)
Out[2]= {0.01 Second, 8. 10 }

Rob Knapp
Wolfram Research, Inc.

```

• Prev by Date: Re: Restrict domain of Plot3D[]?
• Next by Date: can notebooks be activated on a web server?
• Previous by thread: Re: Max of Concave List...And The Winner Is....
• Next by thread: automatic referencing (almost working)