"Le Forgeron" ha scritto 
: 
: You mean that you understood that optimisation code ? Greats if true!!
: 

What I understood is this:

You've got a polynomial and are interested in roots that lie
in the interval (l l+w):

b0 x^4 + b1 x^3 + b2 x^2 + b3 x + b4 = 0

First you change the coordinate with a transformation of this kind:

  x = l + t w    <--> t = (x - l) / w

so the interesting interval becomes (0 1), the substitution is trivial
and in the code it is correct AFAICS.

So you obtain a polynomial in t

a0 t^4 + a1 t^3 + a2 t^2 + a3 t + a4 = 0

you could already say that if all ajs are non negative (non positive)
then there is no root in (0 1), it's the sum of non negative () 
quantities..., but this is not really meaningful, since happens often
that one aj has a different sign from the others, but there is no root 
in that interval.

So he transforms the polynomial to the Bezier form, and the same 
reasoning holds (sum of non negative). And expressed in this form 
it is meaningful since when skipping the search the execution times 
decrease significantly.

I did not consider the case of all ajs == 0 or what happens in zero, 
one. But I'm confident in who wrote originally the code.

Massimo

Post a reply to this message