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?
Find a function that combines a set of integers and outputs an integer. This output can be used to deduce the absence of any integer in the set.
ds.algorithms
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.Assign each event a sequential number starting at 2.Calculate $c = (m+1)! \mbox{mod}~p$, where p is some prime number greater than m+1 but less than $2^{32}$.When registering the events, simply multiply the numbers corresponding to the events sequentially modulo p. Call this result r.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. UPDATEA simpler solution (coming from Jukka's comment) is simply to do the following:Assign each event a sequential number starting at 1.Calculate $c = \sum_{j=1}^m j~ \mbox{mod}~2^{32} = \frac{j(j+1)}{2} \mbox{mod}~2^{32}$.When registering the events, simply add the numbers corresponding to the events sequentially modulo $2^{32}$. Call this result r.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. 