Квадратный корень - модифицированный поразрядный поиск



Необходимо найти квадратный корень из числа, представимого с помощью длинной арифметики

Реализация алгоритма рассмотрена на классе 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