Sheep Photos
Blizzard Sledding, Skiing, and Kayaking
Earlier this week, I ventured into a beautiful blizzard with a friend to go sledding and skiing at President’s Lawn, Tufts University. Here are the resulting video and photos, including shots of the amazing Tufts Ski Team:
Cryptography, Dancing, Morse Code, Number Theory, and Music
What do cryptography, dancing, Morse code, number theory, and music have in common? My latest album: Sweet Suites, Volume 1: Um… What?
Cipher Suite no. 1, Fs PSK_PBKDF2_SNOW_HMAC, “Deprecated” (music video, sheet music) is my attempt to turn a cipher suite into a suite of dance music based on the cryptographic algorithms. In Pavane for a Pre‐Shared Key, Alice (clarinet) and Bob (violin) are in perfect sync throughout a slow and formal key agreement (dance). For the Password‐Based Key Derivation Function Two‐Step, cryptographic key derivation is represented by frequent musical key changes. Sometimes Alice derives new keys from a secret; sometimes Bob does; sometimes they both derive the same keys from the same secret. Once data encryption key(s) are available, Alice and Bob can start sending encrypted messages using a stream cipher, in Snoa in the SNOW. As they go through the ciphertexts in this dance music, they frequently lose synchronization, but they recover each time. Finally, they authenticate their messages with a Hash‐Based Message Authentication Zwiefacher. The zwiefacher’s formula is (PPWWP)2: initialize inner hash (pivot), XOR with inner pad (pivot), update inner hash with K′ XOR inner pad (waltz), update inner hash with message (waltz), finalize inner hash (pivot), initialize outer hash (pivot), XOR with outer pad (pivot), update outer hash with K′ XOR outer pad (waltz), update outer hash with inner hash result (waltz), finalize outer hash (pivot).
Morse Code Suite no. 1, Fs 1865 (music video, sheet music) comes from my realization a while ago that I really like the sound of International Morse Code’s rhythm, and my inability to find any music with that rhythm. (There is plenty of music that incorporates Morse code, but I didn’t find any that used standard timings for a significant portion of the tune.)
Piano Axioms Suite no. 1, Fs ℕ (music video, sheet music) exists because I saw an unfulfilled mathematical pun opportunity in the name of the Peano axioms (a.k.a., Peano postulates). In each of the five axioms/postulates/movements, rests represent zero and successive notes represent successive natural numbers.
Finally, because vuvuzelas amuse me, I arranged Morse Code Suite no. 1 for Solo Vuvuzela, Fs 1865‽ (music video, sheet music). It sounds pretty bad, but that’s definitely the point.
Get the album today (or tomorrow, or not at all, who am I to tell you what to do?) on Bandcamp.
Inbreeding, Time Travel, and Graph Theory
While working on livestock management software for a client, I got to thinking. How much harder would inbreeding calculations be, if an organism could travel back in time to be its own ancestor? Disclaimer: this has not been peer reviewed, let alone reviewed by anybody with more than a high school level understanding of biology or time travel.
First, let’s start with an incredibly degenerate case. Alice takes her son Bob on a vacation into the future. While then, Bob picks a pretty flower and hides it in his pocket. He names the flower Carol. Upon returning to their native time, Bob immediately runs outside and replants the flower. Some time later, the flower fertilizes itself and produces an offspring, which is later picked up by young Bob.
In this case, Carol contributed both of the haploids that merged to form herself. She’s her own parent, twice over. Each of Carol’s homozygous loci has a 100% chance of producing identical alleles in the gametes, and therefore the same homozygous locus in the offspring (which is also Carol). Each of Carol’s heterozygous loci has a 50% chance of giving the same allele to the male gamete as what was in the male gamete that produced Carol; similarly and independently, it has a 50% chance of giving the correct allele to the female gamete. Combined, there’s a 25% chance that a single heterozygous locus will result in the same genetic path that produced itself. However, unlike with normal inbreeding calculations, we know that all the genes of Carol as a child are equal to Carol as the parent. Therefore, let n be the number of loci, and the probability of heterozygosity due to descent is 0.25n. The probability of homozygosity due to descent, i.e., the coefficient of inbreeding, is therefore 1 − 0.25n. Luckily, Alice is a botanist, so when she discovers what Bob did, she teaches her son an interesting lesson about genetics and time travel.
Elsewhere in the world, Dave is a sheep farmer who’s about to go on a business trip to a few years in the past. Unfortunately, things don’t go according to plan, when his prized ewe Eve sees the portable time machine and thinks it’s a bucket of corn. She bumps into Dave, who was already nervous about time travel. He fumbles the time machine, which falls on Eve and activates. Dave spends the rest of the day talking to insurance companies. Meanwhile in the past, Eve meets a very attractive ram named Fred.
Since this is theory instead of reality, let’s ignore what actually happens next, and instead generalize and assume. Two of Eve’s ancestors are a mated couple, herself and Fred. Without looping, there are n generations from Eve as an ancestor to Eve as a descendant. I.e., n=1 represents Eve as her own parent, n=2 represents Eve as her own grandparent but not her own parent, etc. To make things easier, assume there are no other common ancestors, so that every ancestor of Eve that is not also a descendant of Eve has a coefficient of inbreeding of 0. Tracing genetic paths from Eve0 back n generations gives 2n distinct genetic paths, one of which is to Eve1 herself. Thus, each locus has a probability of 2−n+1 of having an allele passed down from Eve1 to Eve0. For each of those loci, if Eve1 is homozygous at the locus, she’ll pass down the correct allele (the one she got from herself, Eve2). If Eve1 is heterozygous at that locus, there’s a 50% chance she’ll pass down the correct allele. As in the degenerate case, we know that all of the genes that are passed down to herself are the same ones received from herself. So let m be the total number of loci, and the expected number of loci with alleles Eve passes to herself is 2−n+1m. Therefore, the probability of heterozygosity at those loci is 0.5(2−n+1m). The other loci have alleles from unrelated ancestors, so Eve’s total probability of homozygosity is 2−n+1(1 − 0.5(2−n+1m)). Except for small values of n, that’s really not bad at all!
Generalizing these cases into a comprehensive algorithm for calculating inbreeding in the face of time travel is left as an exercise for the reader. But I suspect it involves a multidigraph where each vertex represents an individual organism, and each arrow represents a gamete, pointing from the parent that created the gamete to the child created from the gamete. Then that type of graph can be split into cases, with some subgraphs analyzed separately. I think that would probably give an algorithm that’s a hybrid between the above cases and normal inbreeding calculations, but I’m not sure.
Bailey at Nod Brook
Waves of Sin
What do you get when you combine a pseudo‐random number generator, the sine function, and some C++ code? In this case, an album of very strange music. With a POSIX shell script and ffmpeg thrown into the mix, you also get music videos.
The album opens with Signals of Sin and closes with Signals of Sin (reprise), because of course music needs telephony signals to frame it. (These are the only two tracks that are not pseudo‐randomly generated.)
Tracks 2–10 explore what happens when you use a pseudo‐random number generator to pick the number of simultaneous “notes,” and the duration, pitch, volume, and left–right pan of each note. To create variety, some tracks (e.g., Sparse Waves of Sin) have very few simultaneous notes, while others (Way Too Many Waves of Sin) have… more. Some tracks have normal‐length notes; Super Fast Waves of Sin and Hyper Fast Waves of Sin don’t. Some tracks include harmonics (e.g., Harmonic Waves of Sin), others have only fundamentals. And for the strangest tracks (Interfering Waves of Sin and Harmonic Interfering Waves of Sin), each note is represented by a spread of interfering frequencies, instead of a single fundamental frequency and optional harmonics.
Finally, the album would not be complete without the raw output of its pseudo‐random number generator, i.e., some white noise: Dedication to Mersenne Twister 19937, Without Which This Album Would Have Been Slightly Different.
I’m definitely not claiming that this is my new favorite form of music, or even that it’s particularly consonant, but after playing around with the code and parameters a bunch, I grew to actually enjoy this music. Unlike my previous album. That one just started to grate on me more and more.
Functional Video Generation
Back in 2011–2012, I played around with generating static images from mathematical functions. Each function effectively took an (x,y) coordinate and returned an RGB tuple. (By mathematical functions, I mean deterministic functions that don’t rely on external input and have no side effects. I.e., given the same input parameters, the function will always return the same value, and do nothing other than return that value.) Some scaffolding code called the function repeatedly and performed anti‐aliasing to produce an image. It was fun to see what I could do just by mapping spatial coordinates to color values.
Then earlier this year, I decided to add a time coordinate and make abstract, ambient videos using the same technique. The single‐threaded python code I used for still images was too slow to be practical for long videos, so I started from scratch with new C++ code and an improved interface. The video scaffolding code exposes the below interface for subclasses to define what the video will look like. (The use of ThreadState and TimeState does make the functional abstraction a bit less pure, but it’s important for performance to not re‐do some calculations for every sub‐pixel.) Once a subclass gives a function that defines what the video looks like in theory, the scaffolding code handles anti‐aliasing, motion blur, and rendering to turn it into a finite video that a computer can display.
// Main class to generate a video (or still frame). Subclass this. Use
// ThreadState for any information local to a thread, and TimeState for
// anything local to a single point in time. (There could be multiple
// TimeStates per frame if temporal oversampling is used.)
template <typename ThreadState = NullState, typename TimeState = NullState>
class VideoGenerator : public VideoGeneratorInterface {
…
protected:
// Get the color value at a single point in space and time. (x,y) are spatial
// coordinates, with the smaller dimension in the range [-1,1]. For a 2:1
// aspect ratio, x would be in the range [-2,2] and y in [-1,1]; for 1:2, x
// would be in [-1,1] and y in [-2,2]. t is in seconds.
virtual Rgb PointValue(
const ThreadState* thread_state, const TimeState* time_state,
float x, float y, double t) = 0;
// Override this if the per-thread state shouldn't be null.
virtual ::std::unique_ptr<ThreadState> GetThreadState() {
return nullptr;
}
// Override this if the per-point-in-time state shouldn't be null.
virtual ::std::unique_ptr<TimeState> GetTimeState(
const ThreadState* thread_state, double t) {
return nullptr;
}
…
};The first video I made was directly inspired by the last still image I’d made with the technique, and used a very similar function. For each time value t, three dimensional Perlin noise provides a map from (x,y,t) to a value that I used as the elevation of the (x,y) point on a topographic map. The elevation values are then used to make contour lines with hue denoting the elevation of the line and lightness denoting how close each point is to its nearest contour line. The code is only 43 lines long including boilerplate, and produces this 12 hour long video of gently moving colorful curves:
Next, I played around with interference patterns similar to moiré patterns, to try to generate something even more abstract than an abstracted topographic map. This code uses a set of overlapping, moving blinds to generate patterns of light and dark. The blinds use Perlin noise to independently vary their size and rotation, and to move side to side. Separately, the hue for the entire screen varies over time. Warning: the end result might cause motion sickness in some people. I tried my best to avoid it, but I’m not sure how well I succeeded.
So far, I’m finding the results of functional video generation interesting, though I do think that more traditional computer animation is a lot more versatile.