The Substitution Cipher

29/10/2013

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

22/10/2013

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

15/10/2013

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)

08/10/2013

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 $X$ if

• all integers may show up: $P(X=n)\neq 0$, $\forall n \in \mathbb{N}$,
• and if beyond $n_0$, the distribution is non-increasing, that is, for $n>n_0$ and $m>n_0$, $n, we have $P(X=n)\geqslant P(X=m)$.

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 $L_u(n)$ (the length of the code for the integer $n$) is $k$-universal if, and only if

$\displaystyle\lim_{n\to\infty}\frac{\sum_{i=1}^n P(X=n)L_u(n)}{\sum_{i=1}^n P(X=n)\log_2 n}=k$

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

06/10/2013

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

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

06/10/2013

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

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++

01/10/2013

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