Finding Collisions

Some time ago, a friend was trying to find an efficient way (storage and time complexity) to find collisions for a (secure) hash function. Hashing random keys until you get a collision is reminiscent of von Mises’ birthday paradox.

In is simplest form, the birthday paradox states that, amongst (randomly) gathered people, the probability that (at least) two share a birthday increases counter-intuitively fast with the number of gathered people. This mean that even if your hash function is random (i.e., strong), you may not have to try a very large number of random keys before finding collisions. Or does it?

OpenMP and The N Queens Problem

Now that we all have multi-core CPUs (multiple cores, simultaneous multi-threading, with uniform memory, etc.) I think it’s about time we really get the hang of it.

However, correctly threading applications is hard in general, and not all applications can gain significantly from parallelism. But some applications are embarrassingly parallel by their nature, and in this case, breaking down the problems into independent sub-problem is not hard at all, often requiring little more synchronization than waiting for all worker threads to finish.

Wallpaper: Concrete Art

(Concrete Art, 1920×1200)

Wallpaper: Fast Forward

(Fast Forward, 1920×1200)

Wallpaper: Stainless Entity

(Stainless Entity, 1920×1200)

Wallpaper: Moria

(Moria, 1920×1200)

Drawing Random Numbers from Disjoint Ranges (Generating Random Sequences V)

On a number of previous installment of this series, I’ve discussed permutations, generating uniform random points in a triangle, on a sphere, the inversion method, even recycling expensive random bits. In this entry, I will use the rejection method to generate random numbers from disjoint ranges.

For simplicity, let us consider only the uniform case, where all values are equally likely to be drawn. So instead of drawing a number from a range, say , we’re interested in the case where the set is composed from several intervals, something like . We may think of drawing uniformly from and retry if we “fall in the gaps”, that is, if we draw a number in or .

A first, it doesn’t seem like a bad plan, especially if the “holes” are rather small and easy to miss—that is, we have a good chance of hitting in an allowable range in a very few tries. For example, if the ranges we’re interested in look like and , drawing from really doesn’t sound like a good idea.

But what if we compacted the ranges?