{{ message }}

Instantly share code, notes, and snippets.

# dyoo/cantor_pairing.go

Last active Jul 7, 2020
Cantor pairing function
 // http://en.wikipedia.org/wiki/Pairing_function package main import ( "fmt" "math" ) func InvertedCantorPairing(z int) (int, int) { w := int(math.Floor((math.Sqrt(float64(8*z+1)) - 1) / 2)) t := (w*w + w) / 2 y := z - t x := w - y return x, y } func CantorPairing(k1, k2 int) int { return (k1+k2)*(k1+k2+1)/2 + k2 } func main() { for i := 0; i < 100; i++ { x, y := InvertedCantorPairing(i) fmt.Println(i, x, y, CantorPairing(x, y)) } }

### dyarosla commented Jan 20, 2018

 Correct me if I'm wrong, but to avoid overflow with big (k1, k2) we should use (k1/2+k2/2)*(k1+k2+1) + k2 This is similar in nature to what you'd do for (a+b)/2 You'd instead code it as a/2 + b/2 Because for large (a, b), where a+b > MAX_INT, we would still get a usable result.

### shaunc commented Jan 19, 2019

 @dyarosla -- rounding down for int division, we have: ``````(3+3)/2 = 6/2 = 3 3/2 + 3/2 = 1 + 1 = 2 `````` Your method works for approximate results, but not for exact ones.