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)) | |
} | |
} |
This comment has been minimized.
This comment has been minimized.
Correct me if I'm wrong, but to avoid overflow with big (k1, k2) we should use This is similar in nature to what you'd do for (a+b)/2 You'd instead code it as Because for large (a, b), where a+b > MAX_INT, we would still get a usable result. |
This comment has been minimized.
This comment has been minimized.
@dyarosla -- rounding down for int division, we have:
Your method works for approximate results, but not for exact ones. |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
This comment has been minimized.