Instantly share code, notes, and snippets.

# dyoo/cantor_pairing.go

Last active October 27, 2021 19:20
Show Gist options
• Save dyoo/8062270 to your computer and use it in GitHub Desktop.
Cantor pairing function
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 // 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

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.