5
$\begingroup$

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.

  1. 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.

  2. 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

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

$\endgroup$
8
  • $\begingroup$ Where are these matrices coming from? Are you generating them so fast you can't even afford to calculate an MD5 hash for each one of them? $\endgroup$ Dec 10, 2014 at 17:59
  • $\begingroup$ I think performance issues are off topic for this site. $\endgroup$ Dec 10, 2014 at 18:00
  • $\begingroup$ @Andrej Bauer: sorry, I edited to clarify that each row receives hash value, not just the matrix, as I need to compare rows from different matrices. $\endgroup$
    – M.G.
    Dec 10, 2014 at 18:30
  • $\begingroup$ @AlexDegtyarev: Neither of the questions is about performance, so your comment is off topic. $\endgroup$
    – M.G.
    Dec 10, 2014 at 18:30
  • 1
    $\begingroup$ Why rational FP32 as opposed to 32 bit int? Does the type difference affect a) the basic abstracted problem b) the problem as you will implement it? $\endgroup$ Dec 11, 2014 at 4:48

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thanks! I am already aware of various ways to enumerate combinations and similar, but I did not know it was called ranking. Indeed the recursive property avoids integer overflow without resorting to transcendental functions and is also a tad faster for the same reason (esp. after exploiting basic properties of ${n \choose k}$), but it is still slower than the primes method for real-time ranking since it adds several more operations per matrix entry. With a theoretical "only" 3:1 FP32-to-FP64 op./s ratio, this is probably not that surprising. (continued) $\endgroup$
    – M.G.
    Dec 11, 2014 at 14:53
  • $\begingroup$ (from prev. comment) But of course you are right that the fastest way is to use a pre-generated table of the binomial coefficients instead of computing them every time, which is nearly the same as using a pre-generated sequence of primes or of integers/rationals with the asked property. In the example $n=30, k=5$, I guess the only difference is that a table of binom. coeff. with 30x5 entries is 5 times bigger than a vector/seq. of 30 entries, difference is negligible though. Still, none of this answers my Q1 and Q2 :-) $\endgroup$
    – M.G.
    Dec 11, 2014 at 15:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.