Cracking Playfair Ciphers
In 2020, the Zodiac 340 cipher was finally cracked after more than 50 years of trying by amateur code breakers. While the effort to crack it was extremely impressive, the cipher itself was ultimately disappointing. A homophonic substitution cipher with a minor gimmick of writing diagonally, the main factor that prevented it from being solved much earlier was the several errors the Zodiac killer made when encoding it.
Substitution ciphers, which operate at the level of a single character, are children’s toys, the kind of thing you might get a decoder ring for from the back of a magazine.
A Seriously Slow Fibonacci Function
I recently wrote an article which was ostensibly about the Fibonacci
series but was really about optimization techniques. I wanted to follow up on
its (extremely moderate) success by going in the exact opposite direction:
by writing a Fibonacci function which is as slow as possible.
This is not as easy as it sounds: any program can trivially be made slower,
but this is boring. How can we make it slow in a fair and interesting way?
A Fairly Fast Fibonacci Function
A common example of recursion is the function to calculate the \(n\)-th Fibonacci number:
def naive_fib(n):
if n < 2:
return n
else:
return naive_fib(n-1) + naive_fib(n-2)
This follows the mathematical definition very closely but it’s performance is
terrible: roughly \(\mathcal{O}(2^n)\). This is commonly patched up with dynamic
programming. Specifically, either the memoization:
from functools import lru_cache
@lru_cache(100)
def memoized_fib(n):
if n < 2:
return n
else:
return memoized_fib(n-1) + memoized_fib(n-2)
or tabulation:
Craps Variants
Craps is a suprisingly fair game. I remember calculating the probability of winning craps for the first time in an undergraduate discrete math class: I went back through my calculations several times, certain there was a mistake somewhere. How could it be closer than $\frac{1}{36}$?
(Spoiler Warning If you haven’t calculated these odds for yourself then you may want to do so before reading further. I’m about to spoil it for you rather thoroughly in the name of exploring a more general case.
Complex Numbers in R, Part II
This post is part of a series on complex number functionality in the
R programming language. You may want to read Part I before continuing if
you are not already comfortable with the basics.
In Part I of this series, we dipped our toes in the water by explicitly
creating some complex numbers and showing how they worked with the most basic
mathematical operators, functions, and plots.
In this second part, we’ll take a more in-depth look at some scenarios where
complex numbers arise naturally – where they are less of a choice an more
of a necessity.
Complex Numbers in R, Part I
R, like many scientific programming languages, has first-class support for
complex numbers. And, just as in most other programming languages, this
functionality is ignored by the vast majority of users.
Yet complex numbers can often offer surprisingly elegant formulations and
solutions to problems. I want to convince you that familiarizing yourself with
R’s excellent complex number functionality is well worth the effort and will
pay off in two different ways: first by showing you how they are so
amazingly useful you’ll want to go out of your way to use them, and then by
showing you how they are so common and fundamental to modern analysis that you
couldn’t avoid them if you wanted to.