On 05/28/2015 05:59 AM, Waldek Hebisch wrote:
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.
Okay, I don't use failed now.
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'.
Is this fine:
https://github.com/fandango-/fricas/commit/cb10ae48ffc8e32924abcc5c39d8d3b84bba81f5
Thanks,
Abhinav.
--
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.
