Monthly Archives: September 2012

Modeling and measuring string comparison performance in C, C++, C# and Python.

O(1) Comparing strings is often — erroneously — said to be a costly process. In this article I derive the theoretical asymptotic cost of comparing random strings of arbitrary length, and measure it in C, C++, C# and Python.

Continue reading

Generating uniformly random data from skewed input: biased coins, loaded dice, skew correction, and the Von Neumann extractor

A spinning coin, about to fall on tailsIn a famous article published 1951, John Von Neumann presented a way of skew-correcting a stream of random digits so as to ensure that 0s and 1s appeared with equal probability. This article introduces a simple and mentally workable generalization of his technique to random dice, so a loaded die can be used to uniformly draw numbers from the set \(\{1, 2, 3, 4, 5, 6\}\), with reasonable success.

Continue reading