c - Integer cube root -

i'm looking fast code 64-bit (unsigned) cube roots. (i'm using c , compiling gcc, imagine of work required language- , compiler-agnostic.) denote ulong 64-bit unisgned integer.

given input n require (integral) return value r such that

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

that is, want cube root of n, rounded down. basic code like

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

is incorrect because of rounding toward end of range. unsophisticated code like

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; } 

gives correct result, slower needs be.

this code math library , called many times various functions. speed important, can't count on warm cache (so suggestions 2,642,245-entry binary search right out).

for comparison, here code correctly calculates integer square root.

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

the book "hacker's delight" has algorithms , many other problems. code online here. edit: code doesn't work 64-bit ints, , instructions in book on how fix 64-bit confusing. proper 64-bit implementation (including test case) online here.

i doubt squareroot function works "correctly" - should ulong a argument, not n :) (but same approach work using cbrt instead of sqrt, although not c math libraries have cube root functions).