Abhinav Baid wrote:
>
> On Wednesday, May 27, 2015 at 1:02:06 AM UTC+5:30, Waldek Hebisch wrote:
> >
> > >
> > > Sorry for the silence. So, the GSoC coding period has started and I've
> > > finished the implementation of the newtonpolygon
> > > function [1]. Could you please review it?
> >
> > Some remarks:
> >
>
> > 6) I do not see why you have "failed" as part of the result?
> > Whithout it the result would be simpler.
> >
>
> Yes, but what should I do about the final point in the polygon? It doesn't
> have any
> slope or Newton polynomial associated with it. Should I just set them to 0?
I do not think you need final point -- normaly you will need slopes,
and starting point. If for some reason you will need final point
it is easy to recomput from other data.
> > 7) AFAICS you use quadratic method for computing convex envelope.
> > There is simple linear method. Namely given points a1, ..., an
> > given in increasing order of x-coordinate we proceed as follows.
> > We keep a tentative list of points with slopes [[p1, s1], ..., [pk,
> > sk]].
> > At the beginning we accept [a1, 0] to tentative list. Then we
> > handle a2, ..., an iteratively. In itertaion dealing with al we
> > compare slope between pk and al and sk. If sk is bigger or equal,
> > then we drop [pk, sk] from tentative lists. We keep dropping points
> > and stop when we find [pi, si] with slope between pi and al bigger
> > than si. Then we add al with the slope between pi and al to
> > tentative list.
> >
> >
> I've tried to change the function according to the above. [1]
>
AFAICS it is still quadratic in worst case: you add and remove
points at the end which require traversing the whole list. Usual
trick with lists is to keep them in reverse order, so that adding
point is just 'cons' and removing is 'rest'.
--
Waldek Hebisch
[email protected]
--
You received this message because you are subscribed to the Google Groups
"FriCAS - computer algebra system" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/fricas-devel.
For more options, visit https://groups.google.com/d/optout.
