precision

Should i use long ariphmetics???

How should i correctly calculate the value of polynom for given variable?

Re: precision

Posted by

svr 3 Nov 2006 00:33

Interesting question. I think that is important to understand distinction between root and point of small value. Now i am solving 1503 but have wa9. I have program for finding all roots in complex plane but can't improve precision from 0.0001 to 0.000001. For it would enough to have float with 30 right digits. Question depend also on position of testmakers. I think that if we have

a +0.000001*i complex root then answer a+-0.000001 must be right. To approach root near 0.000001 we must have 30 digits int results.

Re: precision

I've calculated precision up to last digit of standard pascal's type Extended, so, my precision should be up to 1e-16. But still WA #9...

*Edited by author 03.11.2006 14:45*

Re: precision

Posted by

svr 3 Nov 2006 15:02

example:

x^5==0

x0=0-root;

x1=0.00001- bad value

but x1^5=1.0*E-25- very small

Re: precision

My reqursive approach of solving equation P(x)=0 is: to solve equation P'(x)=0, and then binary search on all the intervals, whose ends are roots of equation P'(x)=0. So, I haven't problems with "excess psevdoroots", but still WA #9...

Re: precision

Posted by

svr 3 Nov 2006 23:41

Eqution P'(x)=0 is also bad because P'(x) may has multiple roots. It should start from d(N-1)P/dx=0 which is linear and go up applying binary search on each stage. If root multiple then on previous stage it was simple and is founded. As result all candidates for roots will be found with hight precision. The problem is to make choice which of them are roots of P(x)=0. Here we must use existence theoren of Sturm . Simplest variant is P(a)*P(b)<0=> x in [a,b]. I used with success long aritmetic and now on WA16.

AC finally.

In Java only using my BigFraction baseg on BigInt

I implemented famous Stourm's theorem which garantees

absolutely correct considering multiple roots

without any eps and so on.

But in question what degree of found multiple root

I needed in unknown constant h which garantes that if

d/dtP(t)!=0 and P(t)==0 than in (t-h,t+h) d/dtP(t)!=0.

I taken h=1e-12. In other words I think that if

P(t)==0 and in (t-h,t+h) exists t1 such that d/dtP(t1)==0

then t==t1.

h=1e-6 works also.

*Edited by author 08.12.2007 19:43*

Re: precision

Should i use long ariphmetics???

How should i correctly calculate the value of polynom for given variable?

I think it's impossible to calculate P(x) with

given accuracy (10^-6), without long arrithmetics

Re: precision

Eqution P'(x)=0 is also bad because P'(x) may has multiple roots. It should start from d(N-1)P/dx=0 which is linear and go up applying binary search on each stage. If root multiple then on previous stage it was simple and is founded. As result all candidates for roots will be found with hight precision. The problem is to make choice which of them are roots of P(x)=0. Here we must use existence theoren of Sturm . Simplest variant is P(a)*P(b)<0=> x in [a,b]. I used with success long aritmetic and now on WA16.

i do it more simply.

int r[n] - array of int which represent roots P'(x)

int i,j;

for (i=0;i<n;i++)

for (j=0;j<n;j++) if (i!=j) trytofindroot(P,r[i],r[j]);

*Edited by author 04.11.2006 15:41*Re: precision

Fortunatelly, it is possible... :)

I don't know what in fact is the problem with test #9 but I had WA10 and the problem with is was the equal roots. If you concern about these particular cases, you won't have the need of long arrithmetics (I don't wish long float arithmetics to anyone!!!)

Re: precision

And what problem with my approach, when P'(x) has multiple roots? At some stage we make binsearch from x to x, where x - multiple root, and, as a result, we'll get still 3 new roots of P(x). For input

5

1

0

0

0

0

0

my program outputs

0

0

0

0

0

I think, it is right answer. Isn't it?

*Edited by author 06.11.2006 00:54*

Re: precision

Fortunatelly, it is possible... :)quote>

and how I can do it?

Re: precision

Vedernikoff Sergey: yes, this output is correct.

Alexander Prudaev: I had a precision error but eliminated it by checking whether the given function has zero value for the borders of the searching interval.

p.s. I am sorry for the late post. I haven't seen your posts (it might be usefull the admins to create an informational/notificational system)

*Edited by author 17.01.2007 06:59*

*Edited by author 24.01.2007 02:22*

*Edited by author 24.01.2007 02:23*

Re: precision

I solve it problem with long double!!

Re: precision

Posted by

Makarov 30 Jan 2008 16:16

Did you use Ferrary method or Euler solution for polynomial of fourth degree? I understood that you don't find root using general methods because of your time.