|
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