5
$\begingroup$

Lets say that I have 50 events that generate some unique number (you are free to choose the number, but they should all fit in a 32 bit variable). I want to combine those numbers into a single number(32 bit), which can be used to find the absence of an event (i.e. a number).

If it was just ~10 events, I could have just used prime numbers and multiplied them, but multiplying first 50 primes results in 1.9x10^91 (which will not fit in a 32 bit variable).

Can anyone think of a better way to do this?

|cite|improve this question
$\endgroup$
  • 4
    $\begingroup$ Clearly you can't use a 32-bit value to encode which subset of 50 events is absent, if you can have any number of absences between 0 and 50. I think you should clarify your question to explain exactly what kind of situations you need to handle. $\endgroup$ – Jukka Suomela Sep 16 '10 at 21:13
  • $\begingroup$ Thanks for all the great answers. The original problem (sort of unrelated but caused me to think of a different problem) was that I had a sequence of debug statements being printed in a loop, that I needed in place to diagnose an issue, but memory/space restrictions mandated that I couldn't just print to the logs and wait for the bug to occur.. so I started looking into ways I could combine 50 events (completely random choice of number) into an int that I could print every 50 iterations and which would tell me the specific loop and the condition that had failed. $\endgroup$ – Sridhar Iyer Sep 19 '10 at 0:24
  • $\begingroup$ Well, in that case I think you should just combine 32 events into an int, one bit per event... $\endgroup$ – Jukka Suomela Sep 19 '10 at 17:52
8
$\begingroup$

Well, is it only one missing event you want to detect? It you need to be able to detect the presence or absence of all 50 events, this means distinguishing between $2^{50}$ possibilities which obviously cannot be done with 32 bits. However if you wish to just detect a single missing event, here is a way that will work. Assume you have m events.

  1. Assign each event a sequential number starting at 2.
  2. Calculate $c = (m+1)! \mbox{mod}~p$, where p is some prime number greater than m+1 but less than $2^{32}$.
  3. When registering the events, simply multiply the numbers corresponding to the events sequentially modulo p. Call this result r.
  4. To determine if an event is missing, calculate $x = (c \times r^{-1}) \mbox{mod}~p$. If $x=1$ then no events are missing, otherwise $x$ is the label for the missing event.

UPDATE

A simpler solution (coming from Jukka's comment) is simply to do the following:

  1. Assign each event a sequential number starting at 1.
  2. Calculate $c = \sum_{j=1}^m j~ \mbox{mod}~2^{32} = \frac{j(j+1)}{2} \mbox{mod}~2^{32}$.
  3. When registering the events, simply add the numbers corresponding to the events sequentially modulo $2^{32}$. Call this result r.
  4. To determine if an event is missing, calculate $x = (c - r) \mbox{mod}~2^{32}$. If $x=0$ then no events are missing, otherwise $x$ is the label for the missing event.
|cite|improve this answer
$\endgroup$
  • $\begingroup$ In this case, sums would be simpler than products. No need for modulo $p$, either... $\endgroup$ – Jukka Suomela Sep 16 '10 at 21:42
  • $\begingroup$ Yes, sums modulo $2^{32}$ actually seems the best solution. The modulo arithmetic lets you go above $2^{16}$ events though, so it seems useful to keep. $\endgroup$ – Joe Fitzsimons Sep 16 '10 at 21:48
  • $\begingroup$ Anyway, I think we have here an interesting question: if you just assign labels $a_1, a_2, ..., a_n$ to $n$ events and calculate the sum modulo $2^{32}$, how many missing events can you identify? Obviously, if $n = 32$ we can detect any subset of events (by using labels that are powers of 2), but what about the original question with $n = 50$? $\endgroup$ – Jukka Suomela Sep 16 '10 at 21:55
  • $\begingroup$ Well, a bound is simple enough. It is just the largest number y such that $\sum_{i=1}^y \frac{50!}{i!(50-i)!} \leq 2^{32}$. $\endgroup$ – Joe Fitzsimons Sep 16 '10 at 22:02
  • $\begingroup$ Sure, but is the bound achievable? How do you construct the labels? $\endgroup$ – Jukka Suomela Sep 16 '10 at 22:11
5
$\begingroup$

You can use "binomial encoding" (I forgot the real name). As Joe suggested, we can store the information "the set contains all numbers but for those in S" for any S of size at most 9. The question is how to find a bijection between subsets of $[50]$ of size at most 9 and numbers between 0 and 13432735555 (as it happens).

Let's generalize by replacing 50 with $n$ and 9 with $k$. We use the notation

$$ D(m,t) = \sum_{s=0}^t \binom{m}{t} $$

This quantity satisfies Pascal's identity $D(m,t) = D(m-1,t) + D(m-1,t-1)$ (but different initial conditions: $D(0,t) = 1$). We can use this to encode all subsets of size at most $k$ using the numbers up to $D(m,t)$ by using the first $D(m-1,t)$ numbers for the case in which $0 \notin S$, and the next $D(m-1,t-1)$ for the case in which $0 \in S$; continue recursively.

An alternative way is to first encode the size of the set (implicitly) and then use binomial coefficients instead of their running sum. In that approach, the first $\binom{n}{0}$ integers are used for $|S|=0$, the next $\binom{n}{1}$ are used for $|S|=1$, and so on; once in the given range, we do the same thing as before (with binomial coefficients). The advantage of this variant is that smaller sets get smaller numbers.

|cite|improve this answer
$\endgroup$
5
$\begingroup$

An extremely simple (but not optimal) solution is to just pick an appropriate set of 32-bit labels like

809304A4 81086020 85408488 86001692 8847B001 90345788 B5B20840 E0300CB0
F2509412 00201046 00220002 002881C5 00401294 00473641 00908800 00E03790
010488F0 01100801 0110A012 01444A06 02B81688 04212440 044818B8 05EC2980
080000C8 08C27034 08C41000 10900521 13408948 14A00284 19189450 1CA9C469
20100542 20901B3A 210760A5 21450B84 22904411 283A0220 2C850080 31400049
34C44604 407C4260 4A465204 5CE00080 6080166C 61A93080 62080010 6300084B
68490802 6CA08029

and then take XOR of all labels that are present. I think this particular set of labels allows you to identify up to 5 missing events. This might be close to the spirit of your question; the part of "combining" the numbers is extremely simple.

However, something to keep in mind with any approach. As you can't identify an arbitrary set of missing events with 32-bit labels, then you might have different kinds of weaker goals like these:

  1. Detect if there are any missing events.
  2. Count the exact number of missing events.
  3. If the number of missing events is at most $k$, find out what are the missing events.

For example, this particular approach solves the goal 3 (for $k = 5$) but not necessarily goals 1 and 2. It would be good if you clarified what are the exact requirements.

|cite|improve this answer
$\endgroup$
1
$\begingroup$

It isn't clear to me from the question whether more than one event could be missing. Here I propose a solution for the case where only 1 event is missing.

Assign values based on a Golomb Ruler - ``a set of non-negative integers such that no two distinct pairs of numbers from the set have the same difference''.

Here is a set of mark locations for a 51-mark Golomb Ruler:

     1     8    26    39   149   223   247   355   384   419
   439   485   506   508   548   585   644   650   761   900
   936   950  1018  1035  1040  1110  1168  1217  1244  1289
  1322  1337  1480  1489  1492  1508  1670  1732  1785  1815
  1826  1858  1912  1983  2043  2095  2099  2146  2156  2190

The maximum value if all 50 events are present is 2190. Subtract the value returned by the function from this to determine which distance is missing and look it up to determine which event is missing.

Example: If the function return value is 2183 then the missing value is the one with distance 2190-2183 = 7. The 2nd mark has distance 7 therefore the event associated with that mark was not seen.

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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