быстрый код для 64-битных (без знака) корней куба. (Я использую C и компилирую с помощью gcc, но я думаю, что большая часть требуемой работы будет зависеть от языка и компилятора.) Я буду обозначать через ulong 64-битное целое число без проверки.

Учитывая вход n, я требую, чтобы (целое) возвращаемое значение r было таким, чтобы

r * r * r <= n && n < (r + 1) * (r + 1) * (r + 1)

То есть я хочу кубический корень из n, округленный вниз. Базовый код вроде

return (ulong)pow(n, 1.0/3);

неверно из-за округления к концу диапазона. Неискушенный код вроде

ulong
cuberoot(ulong n)
{
    ulong ret = pow(n + 0.5, 1.0/3);
    if (n < 100000000000001ULL)
        return ret;
    if (n >= 18446724184312856125ULL)
        return 2642245ULL;
    if (ret * ret * ret > n) {
        ret--;
        while (ret * ret * ret > n)
            ret--;
        return ret;
    }
    while ((ret + 1) * (ret + 1) * (ret + 1) <= n)
        ret++;
    return ret;
}

дает правильный результат, но медленнее, чем нужно.

Этот код предназначен для математической библиотеки и будет вызываться много раз из различных функций. Скорость важна, но вы не можете рассчитывать на теплый кеш (так что предложения типа бинарного поиска с 2 642 245 записями верны).

Для сравнения вот код, которыйправильно вычисляет целочисленный квадратный корень.

ulong squareroot(ulong a) {
    ulong x = (ulong)sqrt((double)a);
    if (x > 0xFFFFFFFF || x*x > a)
        x--;
    return x;
}