Корень n-ной степени - поразрядный поиск

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

Реализация алгоритма рассмотрена на классе binteger длинной арифметики.

Будем заполнять наше число по одной цифре от старших разрядов к младшим. Каждый раз будем ставить максимально возможную цифру, чтобы полученное число не превосходило исходное число.
Сложность O(N³ * log n) или O(N * M * log n), где N - количество цифр, а O(M) - сложность операции умножения.

Листинг C++
binteger sqrt_radix (binteger a, int n)
{
    binteger x;
    x.a = vsint ((a.a.sz - 1) / 2 + 1, 0);
    for (int i = x.a.sz - 1; i >= 0; -- i)
        for (x.a[i] = 9; x.a[i] > 0; -- x.a[i])
            if (cmp (a, power (x, n)) >= 0)
                break;
    erase_null (x.a);
    return x;
}

18:56
12.07.2010

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