El corte de Leones

The Alhambra, in Granada, Spain, is one of the most precious treasures of architecture, and rightfully a UNESCO World Heritage Site. I had the chance of visiting it a few years ago, and I had the chance of taking tons of photos. Recently, and that’s why I’m telling you about the Alhambra, I stumble upon a couple of texts that say that the proportions of the Alhambra are somewhat all built around ratios of . But, well, is it true?

In this week’s entry, let us first see what geometry is supposed to give us in the Alhambra, then we will look for it in the actual building, and finally, we will see that we can arrive to the same results with a much easier method.

Breaking the Substitution Cipher (Substitution Cipher, part II)

A while ago, we had a look at a (simple) substitution cipher. Recall, this cipher proceeds by, as its name suggests, substituting one letter for another. For the cipher to be reversible, the substitution table is in fact a permutation of the alphabet. This permutation is the cipher “key”.

We surmised that frequency analysis can help us decode a message enciphered with a substitution, but that does not help us with atypical or very short messages. What if the message is somewhat skewed, say it doesn’t even have the letter E? Can we still use the (expected) letter frequencies to start decoding it? Well, maybe. Could we use some other approach? What if we had a language model that helps us decide if a tentative deciphering makes sense? Oh, right, we do have one. And since we can use it as a “fitness” function, we can apply genetic programming to find the code!

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,

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.

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.

Amicable Numbers (Part II)

In the first part we discussed how to compute the sum of proper divisors function from the sum of divisors function, . We saw that if we factorize the number then compute the list divisors from prime factor, it was much faster (on average) than testing each possible numbers from to (or , since we get one large divisor for every small divisors).

So now, let’s all put that together to get an efficient program that enumerates amicable pairs. First, we obtain a list of primes (not missing any) where the largest prime is , the largest number we will be testing—we need it to compute (up to) . If we were to search for all amicable numbers, the list would need to be unbounded, maybe we would need to produce it as we go along; but if we look for amicable pairs up to, say, about , we only need primes up to (and there’sn’t that many of them). For the sake of efficiency, we also need a way of not testing a number twice.

The Sieve of Eratosthenes

The Ancient Greeks never fail to amaze me. Sometimes their ideas border the merely superstitious, sometimes you find a guy like Eratosthenes (c. 275 BC – c. 195 BC) that comes up with a truly modern idea. I’m not talking about his invention of geography (in the modern sense of the word) nor about his suspiciously accurate estimate of Earth’s size. No, I’m talking about an algorithm that has a very modern feel to it: the sieve of Eratosthenes

So what is it that I find so modern about this algorithm? Well, it has a computational feel to it, replacing smarts with a simple procedure, regular and repetitive. So, how hard is Eratosthenes’ sieve to implement? Not every: about 10 lines of code is needed in C++ (and possibly quite fewer if we use some other language).

Amicable Numbers (part I)

I know of no practical use for Amicable numbers, but they’re rather fun. And rare. But let’s start with a definition. Let be a natural number (a positive integer), and let

with and , be the sum of the divisors of . We’re in fact interested in the sum of the proper divisors of , that is,

Now we’re ready to define amicable numbers!

Amicable numbers: Two numbers, are amicable, if, and only if, and .

Given , we can find and test if . But to do that efficiently, we need to compute (or ) very rapidly. The first expression above requires , but we can do much better. Let’s see how.