Is there a Go function for obtaining the cube root of a big integer?

I have a big.Int variable, and wish to find the cube root of it.

Is this implemented somewhere in the library? The Exp function seems to only take an integer, and big.Rat seems to be lacking Exp entirely.

Sadly but there is no such function in math/big package. This means that you have to roll out something on your own. One of the easiest to understand and implement is the Newton's method.

All you need is to select some starting number x_0 and use the recursive formula

You have to use it in the following way: Let your integer is b. Then your x^3 = b^3 and your f(x) = x^3 - b^3 and f'(x) = 3 * x^2.

So you need to iterate:
x_{n+1}=x_n - \frac{x_{n}^{3} + b^3}{3x_{n}^{2}}

(check this link with the image of the formula, SO sucks in inserting math formulas).

You start from a guess and ends when previous x_n is close to the next one. How close is for you to decide.

P.S.1 you can look for more complicated numerical methods to find roots (you will need less iterations to converge)

P.S.2 if you need, I wrote a method for calculating arbitrary precision square roots in Go.

I've implemented a cube root function for big.Int, both using a simple binary search and Newton's method as per Salvador Dali's formula. Although I am pretty sure there is room for improvement, here is the code that I've got:

<!-- language: lang-golang -->

var (
n0  = big.NewInt(0)
n1  = big.NewInt(1)
n2  = big.NewInt(2)
n3  = big.NewInt(3)
n10 = big.NewInt(10)
)
func cbrtBinary(i *big.Int) (cbrt *big.Int, rem *big.Int) {
var (
guess = new(big.Int).Div(i, n2)
dx    = new(big.Int)
absDx = new(big.Int)
minDx = new(big.Int).Abs(i)
step  = new(big.Int).Abs(new(big.Int).Div(guess, n2))
cube  = new(big.Int)
)
for {
cube.Exp(guess, n3, nil)
dx.Sub(i, cube)
cmp := dx.Cmp(n0)
if cmp == 0 {
return guess, n0
}
absDx.Abs(dx)
switch absDx.Cmp(minDx) {
case -1:
minDx.Set(absDx)
case 0:
return guess, dx
}
switch cmp {
case -1:
guess.Sub(guess, step)
case +1:
guess.Add(guess, step)
}
step.Div(step, n2)
if step.Cmp(n0) == 0 {
step.Set(n1)
}
}
}
func cbrtNewton(i *big.Int) (cbrt *big.Int, rem *big.Int) {
var (
guess   = new(big.Int).Div(i, n2)
guessSq = new(big.Int)
dx      = new(big.Int)
absDx   = new(big.Int)
minDx   = new(big.Int).Abs(i)
cube    = new(big.Int)
fx      = new(big.Int)
fxp     = new(big.Int)
step    = new(big.Int)
)
for {
cube.Exp(guess, n3, nil)
dx.Sub(i, cube)
cmp := dx.Cmp(n0)
if cmp == 0 {
return guess, n0
}
fx.Sub(cube, i)
guessSq.Exp(guess, n2, nil)
fxp.Mul(n3, guessSq)
step.Div(fx, fxp)
if step.Cmp(n0) == 0 {
step.Set(n1)
}
absDx.Abs(dx)
switch absDx.Cmp(minDx) {
case -1:
minDx.Set(absDx)
case 0:
return guess, dx
}
guess.Sub(guess, step)
}
}

Surprisingly enough, the simple binary algorithm is also the fastest:

BenchmarkCbrt/binary/10e6-4    	  100000	     19195 ns/op
BenchmarkCbrt/binary/10e12-4   	   30000	     43634 ns/op
BenchmarkCbrt/binary/10e18-4   	   20000	     73334 ns/op
BenchmarkCbrt/newton/10e6-4    	   30000	     47027 ns/op
BenchmarkCbrt/newton/10e12-4   	   10000	    123612 ns/op
BenchmarkCbrt/newton/10e18-4   	   10000	    214884 ns/op

Here is the full code, including tests and benchmarks: https://play.golang.org/p/uoEmxRK5jgs.