ENG  RUS Timus Online Judge Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1503. Polynomial

precision
Posted by Dirty Man 2 Nov 2006 20:18
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
Posted by Vedernikoff Sergey 3 Nov 2006 14:44
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;
but x1^5=1.0*E-25- very small
Re: precision
Posted by Vedernikoff Sergey 3 Nov 2006 23:29
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
Posted by Alexander Prudaev 4 Nov 2006 15:33
Dirty Man wrote 2 November 2006 20:18
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
Posted by Alexander Prudaev 4 Nov 2006 15:39
svr wrote 3 November 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.

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
Posted by Peter Ivanov 5 Nov 2006 18:36
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
Posted by Vedernikoff Sergey 6 Nov 2006 00:54
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
Posted by Alexander Prudaev 7 Nov 2006 23:39
Peter Ivanov wrote 5 November 2006 18:36
Fortunatelly, it is possible... :)quote>
and how I can do it?
Re: precision
Posted by Peter Ivanov 17 Jan 2007 03:02
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
Posted by Yevgeniy 29 Jul 2007 15:31
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.