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:
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.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.
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.
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
- 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!