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

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

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

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

Листинг 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 div2 (binteger & x)
{
    int buffer = 0;
    for (int i = x.a.sz - 1; i >= 0; -- i)
    {
        x.a[i] += buffer * 10;
        buffer = x.a[i] % 2;
        x.a[i] /= 2;
    }
    erase_null (x.a);
}
binteger sqrt_bin (binteger a, int n)
{
    binteger left = binteger (0);
    binteger right = binteger (a);

    while (cmp (right, left) >= 0 && greate1 (right, left))
    {
        binteger mid = right + left;
        div2 (mid);

        binteger A = power (mid, n);
        int cmpAa = cmp (A, a);
        if (cmpAa == 0)
            return mid;
        else
            if (cmpAa > 0)
                right = mid;
            else
                left = mid;
    }

    return left;
}

18:53
12.07.2010

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