MathGroup Archive 1998

[Date Index] [Thread Index] [Author Index]

Search the Archive

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

  • To: mathgroup at
  • 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$>
  • Sender: owner-wri-mathgroup at

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

I will add some comments about the built in function Max.  One reason
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:

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 

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)