math/big: add a method to Int for an absolute value comparison

[ericlagergren]

When writing a couple libraries I've needed to compare the absolute value of two big.Ints, but have had my hands tied a bit because the API doesn't allow me to modify them.

Right now, the only way to get an absolute comparison without modifying either of the inputs is

new(big.Int).Abs(x).Cmp( ... ) // allocation of big.Int + copy of entire backing nat
new(big.Int).SetBits(x.Bits()).Cmp( ... ) // allocation of big.Int + dangerous aliasing
// write my own method with code copied and pasted from math/big.nat.cmp

The first two allocate a big.Int and the second causes aliasing which can cause subtle bugs. The allocations have appeared when benchmarking.

It would be very nice to essentially have this

// Cmp compares, ignoring signs, x and y and returns:
//
//   -1 if x <  y
//    0 if x == y
//   +1 if x >  y
//
func (x *Int) CmpAbs(y *Int) int {
    return x.abs.cmp(y.abs)
}

PS: is there a proposal template?

[randall77]

Why r = -r? It doesn't follow given the doc comment.

[ericlagergren]

Sorry, was in a hurry to leave work. I’m on my phone, but yes just x.abs.cmp(y.abs) should be needed. Le ven. 27 oct. 2017 à 18:14, Keith Randall <notifications@github.com> a écrit :

…

Why r = -r? It doesn't follow given the doc comment. — You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub <#22473 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AFnwZ0Gh4mF4ErJU9Vo-8eqxGUSWhjSFks5swn_-gaJpZM4QJwmO> .

[odeke-em]

I'll /cc @griesemer too.

[cznic]

The first two allocate a big.Int and the second causes aliasing which can cause subtle bugs. The allocations have appeared when benchmarking.

Zero allocation/aliasing CmpAbs:

package main

import (
	"fmt"
	"math/big"
)

func CmpAbs(a, b *big.Int) int {
	x := a.Bits()
	y := b.Bits()
	if len(x) < len(y) {
		return -1
	}

	if len(x) > len(y) {
		return 1
	}

	if len(x) == 0 && len(y) == 0 {
		return 0
	}

	t := x[len(x)-1]
	u := y[len(y)-1]
	if t < u {
		return -1
	}

	if t > u {
		return 1
	}

	return 0
}

func n(s string) *big.Int {
	n, ok := big.NewInt(0).SetString(s, 10)
	if !ok {
		panic(ok)
	}

	return n
}

func main() {
	a := n("-1000000000000000000000000000000000000000")
	b := n("-100000000000000000000000000000000000000")
	fmt.Println(CmpAbs(a, b), CmpAbs(b, a))
	fmt.Println()

	c := n("1000000000000000000000000000000000000000")
	d := n("100000000000000000000000000000000000000")
	fmt.Println(CmpAbs(a, c), CmpAbs(a, d))
	fmt.Println(CmpAbs(b, c), CmpAbs(b, d))
	fmt.Println()

	nm1 := n("-1")
	n0 := n("0")
	n1 := n("1")
	fmt.Println(CmpAbs(nm1, nm1))
	fmt.Println(CmpAbs(nm1, n0))
	fmt.Println(CmpAbs(nm1, n1))
	fmt.Println()

	fmt.Println(CmpAbs(n0, nm1))
	fmt.Println(CmpAbs(n0, n0))
	fmt.Println(CmpAbs(n0, n1))
	fmt.Println()

	fmt.Println(CmpAbs(n1, nm1))
	fmt.Println(CmpAbs(n1, n0))
	fmt.Println(CmpAbs(n1, n1))
}

Playground

Output:

1 -1

0 1
-1 0

0
1
0

-1
0
-1

0
1
0

edit: fix link

[cznic]

The code above obviously fails in the general case as I managed to forgot to include the comparison of all but the last words of .Bits(). Hopefully fixed in https://play.golang.org/p/E0HBJlBccV.

[ALTree]

(x *Int) Bits() []Word's documentation says:

Bits provides raw (unchecked but fast) access to x by returning its absolute value as a little-endian Word slice. [..] Bits is intended to support implementation of missing low-level Int functionality outside this package

Note

Bits is intended to support implementation of missing low-level Int functionality outside this package

Which is exactly what you're trying to do.

I'm not sure extending further the (already big) math/big API would be worth it. Is this 'absolute value comparison' operation commonly needed?

[ericlagergren]

@ALTree yeah, when I first noticed the allocs I wrote my own comparison function like @cznic's.

At least in the code I've been writing lately it's common enough. It's a much more efficient way of determining if z is in [-x, x] than creating x and -x and calling Cmp twice. And it's just about the only way to accurately get the length of a big.Int (via https://graphics.stanford.edu/~seander/bithacks.html#IntegerLog10) (with the assumption you can't modify the input, etc.)

It's not too concerning and I understand not wanting to clutter the API. :-)

[griesemer]

@ericlagergren Note that you can do x.Abs(x) at basically no cost; x will not be copied in this case. So if you can temporarily change the sign of x and then reset it, it's easy to do.

[ericlagergren]

@griesemer right. I’ve hesitated to do that since it’s something else to keep track of when, eg, needing abs cmp inside a loop or handing off the big.Ints to other methods, etc.

[griesemer]

@ericlagergren The only thing that matters is whether you have concurrent access to the same big.Int or not. If you don't, you can trivially change the sign locally and then change it back. Factor it out into a CmpAbs function and you're done.

But all that said and done, I'm just going to add this function. There are definitively algorithms that care about the relative magnitudes of values, so this is in fact a useful function to have. I've got the CL, will have tests tomorrow.

[gopherbot]

Change https://golang.org/cl/74971 mentions this issue: math/big: implement CmpAbs

[ericlagergren]

Yeah, perhaps I’m too paranoid. :-) Thanks for adding it Robert. Le mar. 31 oct. 2017 à 22:44, Robert Griesemer <notifications@github.com> a écrit :

…

@ericlagergren <https://github.com/ericlagergren> The only thing that matters is whether you have concurrent access to the same big.Int or not. If you don't, you can trivially change the sign locally and then change it back. Factor it out into a CmpAbs function and you're done. But all that said and done, I'm just going to add this function. There are definitively algorithms that care about the relative magnitudes of values, so this is in fact a useful function to have. I've got the CL, will have tests tomorrow. — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#22473 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AFnwZ94kzI8F0vXkYRQDLZY08ftcBkzfks5syAVNgaJpZM4QJwmO> .

[l0k18]

There is a situation where this gets complicated, that is in finding an absolute differential between two unsigned integers. This is how I solved it in my code:

// Bast - Bifurcation Array Search Tree organising data structure
type Bast struct {
	Weights [2][32]uint32 // Keeps track of the number of elements total in Weights[0,1][0] and rest for each row downwards
	Depth   uint8         // Depth of the Store in rows of the binary tree (cannot be more than 32 due to golang 32 bit array indices)
	Length  Index         // Length of the array, updated when adding rows to cut some time out of the walk operations
	Store   []Data
}

/* ... */

// IsBalanced - returns true if balance is within tolerance prescribed by BalanceTolerance
func (b *Bast) IsBalanced() bool {
	if b.Weights[0][0] > b.Weights[1][0] {
		if b.Weights[0][0]-b.Weights[1][0] > BalanceTolerance {
			return false
		}
	} else if b.Weights[1][0] > b.Weights[0][0] {
		if b.Weights[1][0]-b.Weights[0][0] > BalanceTolerance {
			return false
		}
	}
	return true
}

An Abs(x) function would have made that a little bit less verbose, as I could just Abs(a-b)<BalanceTolerance but I am pretty sure that the code above is what basically would have been executed anyway.