n- - ( )



n ,

binteger .

, x0 f(x). , :
x1 = x0 - f(x0) / f'(x0)
n- .
f (x) = A - xn, x0, f (x0) = 0, x0n = A.
, f (x) = A - xn, f' (x) = - nxn-1.
:
x1 = x0 - (A + xn(n - 1)) / (n * xn-1).
n , . , . 1 .
x0 . ( n > 2 n ). .
O(k * (N2 * log n + N2)) O (k * (M * log n + D)), k - , ( k , ), O(M) - , O(D) - .


C++
bool greate1 (binteger & right, binteger & left)
{
    binteger c = right - left;
    return c.a.sz > 1 || (c.a.sz == 1 && c.a[0] > 1);
}
void mul_int (binteger & x, int c)
{
    for (int i = 0; i < x.a.sz; ++ i)
        x.a[i] *= c;
    for (int i = 0; i < x.a.sz; ++ i)
        next_mod (x.a, i);
    while (x.a.back () > 9)
    {
        x.a.push_back (x.a[x.a.sz - 1] / 10);
        x.a[x.a.sz - 2] %= 10;
    }
    erase_null (x.a);
}
binteger sqrt_geron (binteger a, int n)
{
    a = a << n;
    
    binteger x;
    binteger x1;
    binteger _A;
    binteger _B;
    x1.a = vsint ((a.a.sz - 1) / 2 + 1);
    
    for (int i = 0; i < x1.a.sz; ++ i)
        x1.a[i] = (int)sqrt ((double)(at (a.a, 2 * i + 1) * 10 + at (a.a, 2 * i)));
    
    do
    {
        x = x1;
        
        /*
        x1 = (A + x^n * (n - 1)) / (n * x^(n - 1));
        */

        
        _B = power (x, n - 1);
        _A = x * _B;
        mul_int (_B, n);
        mul_int (_A, n - 1);
        _A = _A + a;
        
        x1 = _A / _B;
    }
    while (greate1 (x, x1) || greate1 (x1, x));
    
    binteger res;
    if (cmp (power (x, n), a) > 0)
        res = x1;
    else
        if (cmp (power (x1, n), a) > 0)
            res = x;
        else
            if (cmp (x, x1) >= 0)
                res = x;
            else
                res = x1;
    return res >> 1;
}

19:04
12.07.2010


По всем вопросам обращаться: rumterg@gmail.com