Testing Hash functions (Hash functions, part III)

So, this week, let’s have a look at how we will test hash functions. Testing is necessary since it’s not because your hash function looks random that it is sufficiently random to be used for look-up.

The anatomy of hash functions (Hash functions, part II)

Before we go on exploring hash functions for look-up, let’s discuss their basic anatomy. This will give us some vocabulary as well as help us identify what are the important characteristics of good hash functions.

Hash Functions (Part I)

Hash tables are a great way of ensuring access to your data. Well, it does, but as long as the hash function is good.

But what exactly makes a hash function a good hash function?

π like an Egyptian

In the Rhind Mathematical Papyrus (RMP) we find that the Egyptians used the approximation

For . The RMP shows how to arrive at this result: you construct a grid and draw an octagon on it that approximates the circle. Turns out this irregular octagon as of the area of the bounding square. But the ancient Egyptians rounded that value, for reasons unknown, from 63 to 64 (I have a theory on why; but that may be a later post). This gives the above approximation.

Optimizing JPEG for bandwidth

Optimizing web content is always complicated. On one hand, you want your users to have the best possible user experience, but on the other hand, you don’t really want to spend much bandwidth delivering the bits.

This week, let’s have a look at how we can optimize images for perceptual quality while minimizing bandwidth. While we could proceed by guesswork—fiddling the parameters until it kind of looks OK—or we can take 5 minutes to write a script that searches the parameter space for the best solution given a constraint, say, perceptual quality.

Unfair Coin Tossing

Suppose you want a fair coin, one that yields heads and tails with equal probability, but only have a bizarre coin that yields a side more often than the other. Can we remove the bias?

John von Neumann gave us a surprisingly simple procedure to remove bias from a coin and yield a fair toss.

A Suspicious Series

Does the series

converge?

At first, you may be reminded of the harmonic series that diverges, because of the divisor following the same progression, and may conclude that this suspicious series diverges because its terms do not go to zero fast enough. But we need to investigate how the part behaves.

Fibonacci rabbits as a rewrite system

In my discrete mathematics class, I often use the Fibonacci rabbits example, here to show how to resolve a recurrence, there a variant where some rabbits go away, here again for rewrite systems.

What are rewrite systems? Not unlike context-free grammars, they provide rules generate “words” in a “language”. Turns out the Fibonacci rabbit population problem is super-easy to model as a rewrite system.

Stirling’s series

Last week, we had a look at how g++ handles tail-recursion. Turns out it does a great job. One of the example used for testing the compiler was the factorial function, .

We haven’t pointed it out, but the factorial function in last week’s example computed the factorial modulo the machine-size (unsigned) integer. But what if we want to have the best possible estimation?

Of Colorspaces and Image Compression (Part III)

Last week, we continued on color spaces, and we showed—although handwavingly—that we’re not very good at seeing color differences in hue and saturation, and that we’re only good at seeing difference in brightness. In this last part, we’ll have a look at how JPEG exploits that for image compression.