How to generate $n$ FP32 rationals s.t. no two distinct k-el. subsets have same sum?

Question

First some

Background: I have lots and lots of integer matrices, whose rows are $k$-combinations (without repetitions and sorted) of numbers from the set $S:=\{1,...,n\}$ and needed to be compared against each other in MATLAB. Naturally, the fastest way to do so is via well vectorized GPGPU-accelerated code (CUDA) utilizing a suitable FP32- or (u)int32-valued hash function on the rows of the matrices, that is each row/combination receives its own hash value. Since performance is of utmost importance, the number and type of operations involved as well as their domain, being FP32 or FP64, is crucial.

As an example for order of magnitude, one may think of $n=30$ and $k=2,3,4,5$. Note that ${30 \choose 5}=142506$.

Things I have thought of so far / already tried:

1. Approach from algebraic number theory: square roots of square-free numbers are linearly independent over $\mathbb{Q}$, in particular over $\mathbb{N}$ => use something like $v = (1,\sqrt{2},\sqrt{3},\sqrt{5},\sqrt{6})$ to encode a matrix $M$ into a vector $M_{hash} = M.v$ via matrix multiplication, or use something like $V = (1,\sqrt{2},\sqrt{3},...,\sqrt{s_{30}})$, where $s_{30}$ denotes the 30th square-free number, to encode $M$ into $M_{hash}$ via indexing $V$ into $M$ and summing each row, that is M_hash = sum(V(M),2) in MATLAB's notation.

2. Approach from transcendental number theory: similarly to approach 1., but instead of roots of square-free integers, use logarithms of pair-wise coprime integers.

Unfortunately, there is a two-fold problem with those two approaches: firstly, it turns out that FP32 is not nearly enough precision for the square-root or the $\log$ approach to avoid collisions. FP64 does suffice though, which in turn slows things down since neither square-root nor $\log$ are "simple" functions.

3. Approach No.1 from combinatorics: use Combinatorial number system. In order to avoid overflowing, one first has to resort to $\log\Gamma(z)$ and $\exp$, which works just fine in FP32, has the advantage that the hashes don't grow rapidly, but unfortunately is slower by virtue of calling 4 instances of transcendental functions for each matrix entry.

4. Approach No. 2 from combinatorics: since the combinations are sorted (w.l.o.g. in ascending order), the map $f:(a_1,a_2,a_3,a_4,a_5)\mapsto a_1+a_2^2+...+a_5^5$ avoids collisions. The problem with this is that it works in the FP32 range for the smaller $k$-s only (can be partially accommodated in uint32 though), but either way it turns out to be slower than expected, probably having to do with raising to power. For the sake of completeness,I should also mention another approach, sort of a middle between 1. and 4., basing on the 31-adic number representation. Obviously it suffers from the same problems.

So far, the fastest I have is

5. Approach based on unique factorization in primes: it indexes $V:=(2,3,...,p_{30})$, where $p_i$ denotes the $i$-th prime number, into $M$ and computes the product in each row, that is M_hash = prod(V(M),2) in MATLAB notation. Even though it operates in the FP64 domain due to the growth of the hashes, it's faster than any of the above methods, probably because of the very few and simple arithmetic operations involved (per row).

So, all this got me thinking about the following

Q1: Given $n$ and $k$ sufficiently small, how can one find / generate a set of $n$ distinct single-precision rational numbers such that no two distinct subsets with $k$ elements have the same sum (after or without loss of precision) lying again in the FP32 range?

If I have such a set pre-generated, I can use it as my $V$ instead of primes and sum instead of product, resulting in the same number of operations as in 5., but in FP32 domain, so I expect it to be a tad faster on a large scale.

I am also aware of the Conway-Guy sequence, which unfortunately breaks the uint32 limit for $n$ slightly bigger than 30, but it also seems an overkill since it guarantees that all subsets yield distinct sums, no just the ones of $k$ elements, which brings me to my next question:

Q2: How much better than the difference sequence of Conway-Guy's can we do in Q1 in terms of lower bound for a fixed $k$ if we restrict ourselves to integers only?

Thanks!

Answer 1

A ranker is the term for a function that takes an element of an ordered sequence and return its ordinal number inside the sequence. Your problem can be solved by a ranker on the set of (n,k) combinations. Check for instance this book, or for a quick-and-easy algorithm here (found by googling "ranking combinations algorithm", you can surely find more). (EDIT: this is basically the same formula as your approach 3. Read on, though).

Note that this requires computing several binomials. From what you write, it seems that this part is troublesome for you. Are you using the naive definition with factorials? There are surely better methods (for instance, use recursively the formula $\binom{n}{k}=\frac{n}{k}\binom{n-1}{k-1}$, which uses only integer arithmetic and does not require computing humongous factorials). Another approach that you should consider is computing them all with the $O(n^2)$ Fermat triangle rule and then caching them in a table; depending on the values of $n$ and $k$ that you are working with, this might be the fastest solution.