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,

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.

The conjecture of 8

The other day I found an amusing short from numberphile about “happy numbers”. Not unlike the Collatz problem, a number is happy if, through successive transformations, it reaches one. The transformation is rather numerological in nature (i.e., it’s arbitrary and so why not): To get the next number in the series to happiness, you take the current number and sum the squares of its digits.

The example in the video is that is a happy number:

Therefore is a happy number. That’s cool, but are all numbers happy, and, if not, what happens when a number is unhappy?

Fast Path Finding (part II)

Last week we had a first look at a simple path finding algorithm with application to games. This week, let us have a look a the relative performance of the implementations considered: C# with a naïve implementation that scans the whole map multiple times; a C# implementation that uses lists to maintain and visit only the border of the solved region (affording massive speed-ups, one hopes); and C++ versions of these two variants, plus a C++ variant that uses set (as bitmaps) to maintain the border list.

In any quantitative study, the first thing to do is to collect data. The best way is to automate the collection, by, for example, adding a function that puts the player in all legal positions on the map, compute all the shortest paths, and measures how long it takes. One may also consider disabling the on-demand power policy as the CPU may jump (progressively?) in high gear as the data collection progresses, introducing bias.

Fast Path Finding (part I)

The other day in class I was telling my students that sometimes simple strategies simply do not cut it. As an easy-to-understand example, I discussed the behavior of baddies in video games. If your game asks for the baddies to chase the player, the first thing you might try is to move the baddies in the direction of the player, without any other sophistication.

So the algorithm in this case is that you move the baddie closer to the player (or try to, as there might be obstacles), and this translates to something like two lines of code:

Building a Tree from a List in Linear Time (II)

Quite a while ago, I proposed a linear time algorithm to construct trees from sorted lists. The algorithm relied on the segregation of data and internal nodes. This meant that for a list of data items, nodes were allocated (but only contained data; the others just contained pointers.

While segregating structure and data makes sense in some cases (say, the index resides in memory but the leaves/data reside on disk), I found the solution somewhat unsatisfactory (but not unacceptable). So I gave the problem a little more thinking and I arrived at an algorithm that produces a tree with optimal average depth, with data in every node, in linear time and using at most extra memory.

Shallow Constitude

In programming languages, there are constructs that are of little pragmatic importance (that is, they do not really affect how code behaves or what code is generated by the compiler) but are of great “social” importance as they instruct the programmer as to what contract the code complies to.

One of those constructs in C++ is the const (and other access modifiers) that explicitly states to the programmer that this function argument will be treated as read-only, and that it’s safe to pass your data to it, it won’t be modified. But is it all but security theater?

Compressed Series (Part II)

Last week we looked at an alternative series to compute , and this week we will have a look at the computation of . The usual series we learn in calculus textbook is given by

We can factorize the expression as

Float16

The possible strategies for data compression fall into two main categories: lossless and lossy compression. Lossless compression means that you retrieve exactly what went in after compression, while lossy means that some information was destroyed to get better compression, meaning that you do not retrieve the original data, but only a reasonable reconstruction (for various definitions of “reasonable”).

Destroying information is usually performed using transforms and quantization. Transforms map the original data onto a space were the unimportant variations are easily identified, and on which quantization can be applied without affecting the original signal too much. For quantization, the first approach is to simply reduce precision, somehow “rounding” the values onto a smaller set of admissible values. For decimal numbers, this operation is rounding (or truncating) to the th digit (with smaller than the original precision). A much better approach is to minimize an explicit error function, choosing the smaller set of values in a way that minimizes the expected error (or maximum error, depending on how you formulate your problem).

Fat, Slim Pointers

64 bits address space lets us access tons more memory than 32 bits, but with a catch: the pointers themselves are … well, yes, 64 bits. 8 bytes. Which eventually pile up to make a whole lot of memory devoted to pointers if you use pointer-rich data structures. Can we do something about this?

Well, in ye goode olde dayes of 16 bits/32 bits computing, we had some compilers that could deal with near and far pointers; the near, 16-bit pointers being relative to one of the segments, possibly the stack segment, and the far, 32-bits pointers being absolute or relative to a segment. This, of course, made programming pointlessly complicated as each pointer was to be used in its correct context to point to the right thing.