ENG  RUS Timus Online Judge Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

## Обсуждение задачи 1503. Многочлен

precision
Послано Dirty Man 2 ноя 2006 20:18
Should i use long ariphmetics???
How should i correctly calculate the value of polynom for given variable?
Re: precision
Послано svr 3 ноя 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
Послано Vedernikoff Sergey 3 ноя 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
Послано svr 3 ноя 2006 15:02
example:
x^5==0
x0=0-root;
but x1^5=1.0*E-25- very small
Re: precision
Послано Vedernikoff Sergey 3 ноя 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
Послано svr 3 ноя 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
Послано Alexander Prudaev 4 ноя 2006 15:33
Dirty Man писал(a) 2 ноября 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
Послано Alexander Prudaev 4 ноя 2006 15:39
svr писал(a) 3 ноября 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
Послано Peter Ivanov 5 ноя 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
Послано Vedernikoff Sergey 6 ноя 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
Послано Alexander Prudaev 7 ноя 2006 23:39
Peter Ivanov писал(a) 5 ноября 2006 18:36
Fortunatelly, it is possible... :)quote>
and how I can do it?
Re: precision
Послано Peter Ivanov 17 янв 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
Послано Yevgeniy 29 июл 2007 15:31
I solve it problem with long double!!
Re: precision
Послано Makarov 30 янв 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.