Search code examples
mathhashgreatest-common-divisor

How can you create a unique key for two interchangable integers?

I am trying to write a simple caching mechanism for Euclid's method of finding the GCD of two numbers:

gcd(a,0) = a
gcd(a,b) = gcd(b, a % b)

Note that gcd(a,b) == gcd(b,a).

For the cache, I need to find a key for a given (a,b) or (b,a), with 0 < a < 20 and 0 < b < 20.

Of course, I could use key = a*20 + b, or key = a + b*20, but those are asymmetric - the key for (1,5) is different than for (5,1).

How could I implement this?

Solution

  • First, sort the numbers.

    key = a > b ? b*20 + a : a*20 + b;