Enumerating 32 bits Floats

This week, let’s go back to (low level) programming, with IEEE floats. To unit test a function of float, it does not sound unreasonable to just enumerate them all. But how do we do that efficiently? Clearly f++ will not get us there.

Nor will the machine-epsilon (the std::numeric_limits::epsilon()) because this value works fine around 1, but as the value diverges from 1, the epsilon basically becomes useless. We would either need a magnitude-dependent epsilon (which the standard library does not provide) or a way of enumerating explicitly the floats in increasing or decreasing order (something also not provided by the standard library). Well, let’s see how we can do that

The Substitution Cipher

Some time ago, we presented the Caesar Cipher, developed a simple language model that allowed us to break the cipher relatively easily. This week, we will look at (simple) substitution ciphers.

Superficially, substitution ciphers seem much stronger than Caesar’s
cipher because, rather than just using shifting of the alphabet, it uses an
arbitrary substitution, for example,

Numerological Transform

I was reading Les jeux et les hommes (the original of Man, Play and Games, [wikipedia] [Amazon.com] and Caillois (the author) makes a remark about numerology. First, he discredits it as merely superstitious (on which I agree totally), but he then makes the remark that the “numerological transform”, this operation that consists in adding the digits of a number repeatedly until only one digit is obtained is uniform over all numbers. Does that makes intuitively sense? Well, we can at least verify it experimentally first!

First, let’s write a short program to generate the raw data. This time, I’ll use Mathematica because it’ll be easier to plot the results. The procedure is as follows:

Simple Random Generators

We all need (pseudo)random numbers sooner or later. Are they hard to generate? Depends. If you want them to be really strong (that is, very random), yes, it’s difficult. If you merely need something random-looking, well, you still need some number theory, but it’s rather not complicated.

Let’s have a look at three simple types: additive, multiplicative, and the infamous linear congruential generator.

Universal Coding (Part I)

It’s been a while since I last talked about data compression. Let us return to the topic this week with universal codes. Universal codes are entropy-like codes, but, unlike, say, Huffman codes, they presuppose very little on the distribution of the integers to code.

We can use optimally a universal code for a random variable if

• all integers may show up: , ,
• and if beyond , the distribution is non-increasing, that is, for and , , we have .

We will show how to build an universal code in a moment, but we will first state the condition that makes a code universal if the probability distribution satisfies the above condition. A code with length function (the length of the code for the integer ) is -universal if, and only if

That is, the expectation of the length (in bits) of the code is proportional to the logarithm of the number being coded.

Let’s now see what an universal code looks like

Suggested Reading:How Children Succeed

Paul Though — How Children Succeed: Grit, curiosity, and the hidden power of character — HMH Books, 2012, 230 pp. ISBN 978-0-547-56465-4

(Buy at Amazon.com)

In this book, Paul Tough explores the links between poverty, domestic violence, ethnicity, grit, tenacity, and the chances children have of succeeding in school and later in life. Some of the conclusions are expected, but the detailed explanations are sometimes surprising. He also discusses at length that grit, endurance and determination, is what makes the main difference between a student that will succeed, and those that will not.

The book is thoroughly researched, but is centred exclusively on the US, with little or no comparisons with other countries, which makes it not that interesting for, say, Canadians. It would have been especially interesting to see why some countries (like those of Scandinavia) seem to fare so well compared to the US that fell far behind in degree completion, despite a slow but steady rise in enrolment.

Suggested reading: Da Vinci Cod

Don Brine — Va Dinci Coddah — Bragelonne, 2006, 200 pp. ISBN 2-915549-70-2

(Buy at Amazon.com)

This parody of Dan Brown’s The Da Vinci Code is much more entertaining than the orginal that I found boring, predictable, and pseudo-intellectual —so much in fact that I gave up reading the original after about one third of the book! The author of the parody (Don Brine… Dan Brown, get it?) does a very good job exploiting all of the very annoying devices of the original: digressions, historical factoids, and all the other silliness.

In this parody, some really evil and even more really secret society rules the world on the behalf of sentient and transcendant cods that are the real superior beings on Earth… or under the oceans, whatev. The parody reuses all the plot devices of classical mystery/conspiracy novels, but with just one extra serving.

Of course, this book isn’t great art, but it has its moments. It got me to laugh a couple of times, and it made a great read for a lazy sunday in the last days of summer (or early fall)

Two Features I’d Like to See in C and C++

This week, let’s discuss two features I’d really like to see in C and
C++; one trivial, one not so trivial.

Euclid, Primes numbers, and a Bit of Algorithm Analysis (Part IV)

While we looked at using the GCD for devising a Las Vegas-type algorithm to test for the primality of a number in a previous entry, we saw that actually testing the number against a list of primes (therefore assuming we have an arbitrarily long list of primes), one prime at a time, is much faster.

The GCD method, for divisor , tests a number in steps, but we haven’t determined the complexity of the other method. Let’s do that now.

Hash Table and Magic (Relatively Primes) Numbers

Today, let’s talk about hash tables. Or, more precisely, one type of secondary probing technique, one that uses some number theory—but not quadratic residues, just relatively prime numbers.

I don’t know if you’re like me, but it often bugs me when I read something in a textbook that seems to make sense, but is claimed without proof nor demonstration (oh, I think I said that before). That seems to happen particularly often when I read stuff about data structures, and this time I decided to explore one of those claims.