Квадратный корень - модифицированный поразрядный поиск
Необходимо найти квадратный корень из числа, представимого с помощью длинной арифметики
Реализация алгоритма рассмотрена на классе binteger длинной арифметики.
Сведём количество произведений длинных чисел в поразрядном поиске к минимуму. На каждом шаге основного цикла мы дописываем цифру и возводим полученное число в квадрат. Заметим, что новый "квадрат" с дописанной цифрой можно представить как квадрат суммы текущего числа и цифры, умноженной на степень десятки. Раскроем этот квадрат суммы и получим формулу для нахождения текущего "квадрата", зная предыдущий "квадрат" и само число с цифрой и её индексом. Таким образом, на каждом шаге основного цикла нам больше не нужно будет перемножать длинные числа, а все остальные операции будут являться линейными.
Сложность O(N2).
Листинг C++
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_modradix (binteger a)
{
binteger x;
binteger A;
binteger _A = binteger (0);
binteger _B;
binteger _C;
x.a = vsint ((a.a.sz - 1) / 2 + 1, 0);
for (int i = x.a.sz - 1; i >= 0; -- i)
{
for (int c = 9; c > 0; -- c)
{
/*
A = (x + c * 10^i)^2 = x^2 + 2*x*c*10^i + c^2*10^(2i)
*/
_B = x;
mul_int (_B, c + c);
_B = _B << i;
_C = binteger (c * c) << (i + i);
A = _A + _B + _C;
if (cmp (a, A) >= 0)
{
x.a[i] = c;
_A = A;
break;
}
}
}
erase_null (x.a);
return x;
}
19:00
12.07.2010
По всем вопросам обращаться: rumterg@gmail.com