ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1621. Definite Integral

GCD (P(x), P'(x)) = const ?
Posted by Anisimov Dmitry 18 Aug 2008 22:54
As I understand, this conditions means P(x) has only simple roots. I tried various solutions to find roots and have got an impression this is not true.
Re: GCD (P(x), P'(x)) = const ?
Posted by [SPbSU ITMO] WiNGeR 19 Aug 2008 00:40
I think you have problem with precision. It is very hard to solve this problem with numeric solver, try to calculate exact solution
Re: GCD (P(x), P'(x)) = const ?
Posted by Anisimov Dmitry 19 Aug 2008 21:40
True. Reimplementing same thing for 64-bit precision (in Pascal) works okay.
Re: GCD (P(x), P'(x)) = const ?
Posted by svr 27 Sep 2008 15:30
I succeed with numeric Barstow method and avoid
monkey Ferrari formulas. Because evil Olympiad precision 1.e-09 I was forced to implement Barstow above BigGecimal in Java.
Who want good tests use MathCad. It's integration in case
rather accurate.
For those who inerested I write Barstow method from my prog:
shorten- also my method for cutting off long BigDecimals
public static BigDecimal Barstow(BigDecimal a[], int N, BigDecimal u0, BigDecimal v0, BigDecimal eps, int MaxIter, int MaxLen)[]

        {
            BigDecimal u, v;
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            String str = null;
            int k, n,faza;
            u = u0;
            v = v0;
            BigDecimal[] b = new BigDecimal[N+1];
            BigDecimal[] c = new BigDecimal[N+1];
            BigDecimal rez[] = new BigDecimal[N+3];
            BigDecimal d, s, q,h;
            BigDecimal Z = new BigDecimal("0.0");
            BigDecimal bb1, bb2;
            h = new BigDecimal("0.0000000000000000000000000000000000000001");
            faza = 0;
            for (k = 0; k <= MaxIter; k++)
            {

                for (n = 0; n <= N; n++)
                {
                    if (n < 1) bb1 = Z; else bb1 = b[n - 1];
                    if (n < 2) bb2 = Z; else bb2 = b[n - 2];
                    b[n] = shorten(a[n].add(bb1.multiply(u)).add(bb2.multiply(v)), MaxLen);

                }
                for (n = 0; n <= N - 1; n++)
                {
                    if (n < 1) bb1 = Z; else bb1 = c[n - 1];
                    if (n < 2) bb2 = Z; else bb2 = c[n - 2];
                    c[n] = shorten((b[n].add(bb1.multiply(u))).add(bb2.multiply(v)), MaxLen);

                }
                d = shorten(((b[N].multiply(c[N - 3])).subtract(b[N - 1].multiply(c[N - 2]))), MaxLen);
                q = shorten((c[N - 2].multiply(c[N - 2])).subtract(c[N - 1].multiply(c[N - 3])), MaxLen);

                d = shorten(d.divide(q, BigDecimal.ROUND_FLOOR), MaxLen);
                s = shorten(((b[N - 1].multiply(c[N - 1])).subtract(b[N].multiply(c[N - 2]))), MaxLen);
                s = shorten(s.divide(q, BigDecimal.ROUND_FLOOR), MaxLen);
                if ((d.abs().compareTo(eps) < 0) && (s.abs().compareTo(eps) < 0))
                {
                    if (faza == 0) { faza = 1; MaxLen = MaxLen * 4; eps = eps.multiply(h); }
                    else break;
                }

                u = u.add(d);
                v = v.add(s);
                k = k;


            }
            rez[0] = u;
            rez[1] = v;
            for (n = 0; n <= N; n++) rez[n + 2] = b[n];
        return rez;

        }


Edited by author 27.09.2008 15:32
Re: GCD (P(x), P'(x)) = const ?
Posted by Martin_fmi 22 Jul 2009 15:50
  I implemented Barstow in C++ as svr suggested but wa11 ... Is there any possibility that good initial guesses obtain a result up to desired precision using Barstow without long arithmetics ?