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

Question

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.

Answer 1

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:

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.