Uniquely identifying sets of numbers

60 Views Asked by At

I am working on an app that needs a certain level of AI, which might be speeded up if I can quickly find matching integer pairs... it asks if integers a & b match integers c & d, irrespective of order? Pair c & d are stored in a B-tree wherein c & d is the equivalent of d & c.

The first thing I think is combining the pair members into one identifier, by adding for instance. The problem is collisions...

a=4 + b=1 == c=2 + d=3. No Good.

Or

(a=7)² + (b=1)² == (c=5)² + (d=5)². Also no good.

But 2ᵃ + 2ᵇ and 2ᶜ + 2ᵈ are distinct if a & b are different than c & d. Similarly for 3 number values, 3ᵃ + 3ᵇ + 3ᶜ will never collide with 3ᵈ + 3ᵉ + 3ᶠ. But these numbers are too large for me to work with in an efficient way: 2⁶⁴⁰⁰⁰ + 2³²⁰⁰⁰ != 2⁴⁸⁰⁰⁰ + 2⁴⁸⁰⁰⁰

After playing with it, I imagined that instead of using 2 for the base, I could use a smaller number to exponentiate, as long as it was greater than 1. For instance, 1.001. And still result a unique identifier for the combination. It would follow that for 3 numbers, any base larger than 2 would suffice. And so on.

Maybe I should have asked the question then. But I decided to write a small test app to check for collisions in say the first 64000 values which is as much as I have need for I think. Brute force

for a = 2 to 64000
    for b = 0 to a - 2
        for c = b + 1 to a - 1
            for d = c to a - 1 
                does 1.0001ᵃ + 1.0001ᵇ == 1.0001ᶜ + 1.0001ᵈ
            }
        }
    }
}

It improves if I don't recalculate a, b, and c, each loop. And multithread it. However

After seven hours a = 2700 with no collisions, just another 61300 outer loops to go, but it is slowing down too much. There must be octillions of tests.

My first question is, will they collide? Here I'm not considering imprecise floating-point number results.

And secondly, is there a higher order approach to this problem?