[Maxima] simplifying sums of numbers
fateman at cs.berkeley.edu
Sat Dec 30 13:18:05 CST 2006
> -----Original Message-----
> From: maxima-bounces at math.utexas.edu
> [mailto:maxima-bounces at math.utexas.edu] On Behalf Of sen1 at math.msu.edu
> Sent: Saturday, December 30, 2006 8:11 AM
> > For searching, a bipartition method could be fast enough:
> first compare
> > x with element in position length(z)/2, and take the inferior or
> > superior half of pairs, and repeat this process until you find the
> > interval.
> > Does this help?
A suggestion, if this is to be fast, storing the elements in a LIST is a bad
idea, because to get the element in position L takes L steps. This converts
a fast method (binary search which takes logarithmic time) into linear time.
If you want to do linear time, just iterate down the list searching for the
right interval in order.
Allocating a proper array and sorting it is very easy in lisp; it can't be
too hard in maxima.
On the other hand, the linear time search might be so fast that you don't
really need to do binary search at all.
I don't know what the objective really is here, but there are lots of
geometric computation packages, and I have recently looked at a
computational vision package (associated with another version of lisp, LUSH)
with lots of tools that probably include more general stuff than this, at
least for numerical inputs.
More information about the Maxima