Is there another way of testing if a big.Int is 0?

Question

I'm working with big.Ints and need to test for 0. Right now, I'm using zero = big.NewInt(0)and Cmp(zero)==0 which works fine, but I was wondering if there's a quicker way specifically for 0 (I need this program to be very fast)?

Answer 1

big.Int exposes Int.Bits() to access the raw bytes of the representation, which is a slice and it shares the same underlying array: the returned slice is not copied. So it's fast. It's exposed to "support implementation of missing low-level Int functionality".

Perfect, exactly what we want.

0. Testing for 0

Documentation of big.Int also states that "the zero value for an Int represents the value 0". So in the zero value (which represents 0) the slice will be empty (zero value for slices is nil and the length of a nil slice is 0). We can simply check that:

if len(i1.Bits()) == 0 {
}

Also note that there is an Int.BitLen() function returning this, which also states that "the bit length of 0 is 0". So we may also use this:

if i1.BitLen() == 0 {
}

Let's benchmark these solutions:

func BenchmarkCompare(b *testing.B) {
    zero := big.NewInt(0)
    i1 := big.NewInt(1)
    i2 := big.NewInt(0)
    for i := 0; i < b.N; i++ {
        if i1.Cmp(zero) == 0 {
        }
        if i2.Cmp(zero) == 0 {
        }
    }
}

func BenchmarkBits(b *testing.B) {
    i1 := big.NewInt(1)
    i2 := big.NewInt(0)
    for i := 0; i < b.N; i++ {
        if len(i1.Bits()) == 0 {
        }
        if len(i2.Bits()) == 0 {
        }
    }
}

func BenchmarkBitLen(b *testing.B) {
    i1 := big.NewInt(1)
    i2 := big.NewInt(0)
    for i := 0; i < b.N; i++ {
        if i1.BitLen() == 0 {
        }
        if i2.BitLen() == 0 {
        }
    }
}

Benchmark results:

BenchmarkCompare-8      76975251            13.3 ns/op
BenchmarkBits-8         1000000000           0.656 ns/op
BenchmarkBitLen-8       1000000000           1.11 ns/op

Getting the bits and comparing the slice length to 0 is 20 times faster than comparing it to another big.Int representing 0, using Int.BitLen() is also 10 times faster.

1. Testing for 1

Something similar could be made to test if a big.Int value equals to 1, but probably not as fast as testing for zero: 0 is the most special value. Its internal representation is a nil slice, any other value requires a non-nil slice. Also: 0 has another special property: its absolute value is itself.

This absolute value property is important, because Int.Bits() returns the absolute value. So in case of a non-zero value checking just the bits slice is insufficient, as it carries no sign information.

So testing for 1 can be implemented by checking if the bits content represents 1, and the sign is positive:

func isOne(i *big.Int) bool {
    bits := i.Bits()
    return len(bits) == 1 && bits[0] == 1 && i.Sign() > 0
}

Let's benchmark this along with comparing the number to one := big.NewInt(1):

func BenchmarkCompareOne(b *testing.B) {
    one := big.NewInt(1)
    i1 := big.NewInt(0)
    i2 := big.NewInt(1)
    i3 := big.NewInt(2)
    for i := 0; i < b.N; i++ {
        if i1.Cmp(one) == 0 {
        }
        if i2.Cmp(one) == 0 {
        }
        if i3.Cmp(one) == 0 {
        }
    }
}

func BenchmarkBitsOne(b *testing.B) {
    i1 := big.NewInt(0)
    i2 := big.NewInt(1)
    i3 := big.NewInt(2)
    for i := 0; i < b.N; i++ {
        if isOne(i1) {
        }
        if isOne(i2) {
        }
        if isOne(i3) {
        }
    }
}

And the benchmark results:

BenchmarkCompareOne-8       58631458            18.9 ns/op
BenchmarkBitsOne-8          715606629            1.76 ns/op

Not bad! Our way of testing for 1 is again 10 times faster.