For whatever we lose(like a you or a me)
it's always ourselves we find in the sea
(from an e.e. cummings poem that autoplays in my head every time I picture the ocean, i.e. ~10,000× while coding this)
Despite being terrible at it, I find graphics programming pretty fun.
Building realistic 3D environments in real time blends physics and computer science—graphics programmers have to satisfy two conflicting objectives:
to simulate reality as accurately as possible,
while using fewer than 16 or 33 milliseconds to process each frame.
Modeling the ocean is a good example of a situation where tradeoffs are required.
Fluid dynamics is based around the Navier-Stokes equations, which are a set of nonlinear partial differential equations that describe the flow of viscous fluids.
Fully solving these equations numerically provides an exact model of the ocean,
but is computationally infeasible.
Instead, I tried to simulate an ocean scene using this approach:
1. Generate realistic water surface height fields to model waves, using empirical knowledge of ocean phenomena.
2. Account for optical processes acting on ocean water: reflection and refraction from a water surface, the color filtering behavior of ocean water, and maybe more-complex effects like caustics and godrays.
3. Render a realistic sky gradient using known properties of atmospheric scattering.
4. Think about computational-resource cost versus quality gained and simplify where possible.
Results so far (underwhelming but workable) (click):
Jamie xx’s new album In Colour is finally out, and it’s so good.
Do you ever get that feeling,
when you’re up at 2 am and almost alone,
of being enveloped in something with maybe someone,
of melancholy becoming euphoric?
This album feels like that.
It’s dense and fleshed out, not downbeat and cryptic like the xx past — but still lonely, and lovely. Listen with good headphones.
Because I loved this album and its cover so much, I built a totally unsanctioned album-themed beat-detecting visualizer here:
(If the presets are unsatisfactory, drag and drop your own audio file onto the page.)
Scheming humans have always faced a basic problem: how can we communicate securely in the presence of adversaries?
Since ancient times, the art of secret communication, or cryptography, has been crucial for governments and the military.
But today cryptography affects us all.
As messages are increasingly transmitted through public channels, cryptography prevents malicious interceptors from using our information against us.
The evolution of cryptography can be split into two eras by the invention of asymmetric ciphers in the 1970s.
Historically, encrypting and decrypting a message had been symmetric processes — that is, unscrambling the message required knowing the key that had been used to scramble it.
This begat the problem of key distribution: before sending a secret message, the sender would have to take great precautions to transport her encryption key safely to the recipient.
In asymmetric cryptography, the keys used to encrypt and to decrypt a message are different.
This means that the recipient can make his encryption key public, as long as he keeps his decryption key private.
What we need for an asymmetric-cryptography protocol to work is a trapdoor one-way function.
This is the mathematical equivalent of a physical lock: easy to process in one direction (snapping the lock closed), but hard to undo (opening the lock), unless we have a special secret (the key).
In RSA – the first public-key cryptosystem, and still the most popular – the trapdoor function exploits mathematical features of modular exponentiation, prime numbers, and integer factorization.
Let’s throw together a toy implementation in Scala.
Helpful math functions
A number is prime if it has exactly two divisors: 1 and itself. Sometimes it’s useful to have a list of small primes, so we need a Sieve of Eratosthenes:
What we really want, though, is large primes – ones higher than 2500.
To get a prime that large, we can’t sieve up from 1; instead, we find a prime by taking a random number, checking if it’s probably prime, and repeating if necessary.
The primality test of choice in real systems is Miller-Rabin, but we’ll use Solovay-Strassen to keep things simple:
Finally, the main reason we’re interested in primes is so we can do calculations modulo our prime. To do this, we need the Extended Euclidean algorithm:
The RSA system
An asymmetric encryption system has two parts: a public key and a private key.
In theory, encrypting a message with the public key can only be reversed by decrypting with the private key.
In RSA, we encrypt a message by computing msge mod n, using the publicly-known information n and e.
This is the crux of RSA’s security: modular exponentiation is easy to do, but exceedingly hard to undo.
To make it possible to retrieve the message from the ciphertext, we build a trapdoor into our encryption routine by making n the product of two large primes p and q (which we keep private).
We can then reconstruct the message using a calculated decryption exponent d.
To choose the right decryption exponent, we first need a value φ based on n’s factorization such that xφ(p, q) = 1. Luckily, Euler’s totient function gives us just this:
As long as we choose our public exponent e so that it doesn’t share a common factor with the totient φ, we can decrypt using the inverse of e mod φ:
Encryption and decryption are now trivial:
(In reality, RSA is never used to encrypt messages — for n to be large enough to encode any reasonable length of message, the computing resources required for even the “easy” process of encryption are prohibitively high. Instead, RSA is used to safely deliver symmetric keys, which can then be used with block or stream ciphers to encrypt and decrypt large messages.)
Depending on your level of geekiness, you may have heard Apple’s announcement today that a team of mutantprogrammingvirtuosos has been working—in secret, for years—on a new language that will replace Objective-C as the lingua franca of the iPhone, iPad, and Mac – plus presumably whatever Apple televisual, home-automating, and/or wearable products are to come. Thecircleis—atlast—complete.
The language is called Swift—and, if you’re interested, Apple has released a 500-page ebook detailing the language to let developers get started today.
Technically, Swift has some nice characteristics:
Like C, C++, and Objective-C, Swift compiles down to native code—there’s no VM or interpreter slowing things down at run time. Coupled with some serious compiler optimization, this should make Swift performant enough for any size of application.
Unlike Objective-C, Swift code is proven safe at compile time—that is, no compiled code can cause an access violation at run time (unless we explicitly mark our code as unsafe).
It has first-class functions.
Functions can be nested within other functions, passed as arguments to other functions, and stored as values.
It has closures.
Along with the code for a function, Swift stores the relevant parts of the environment that was current when the function was created. (This makes higher-order functions like sort and fold possible and powerful.)
It supports both immutable values and variables.
Languages usually choose one or the other, but Swift has both—just type let for immutable values and var for (mutable) variables.
Swift is statically-typed, but types can be inferred.
If the type-checker can tell what type the value/variable should be, we don’t have to write it.
And types can be generic.
Functions and methods are automatically generalized by the type-checker, so our functions can be used across compatible parameter types—without manually writing overloads, and without resorting to id and using casts everywhere.
Swift gives us namespaces, with its module system.
Memory is managed automatically, and without pointers.
Like Objective-C post-ARC, Swift uses compiler magic to track and deallocate instances as needed. We don’t need to explicitly specify strong vs. weak references any more, or use * for reference types. This makes iOS programming more accessible (pro/con), though not as easy as with garbage collection. And since ARC happens at compile time, there’s no performance hit at run time.
Swift has tuples (or product types). We can group multiple values into one compound data type, without using container classes/structs.
It has very-special enums (or sum types).
A Swift enum contains a value of one of various specified types.
We can use these like plain C integer enums if we like, but Swift enums go further: Swift lets each enum type carry data.
It has pattern-matching to go with tuples and enums.
Values can be matched against patterns to decompose them concisely.
And much more: lazy properties, property observers, class/struct extensions, buffed-up structs, option types, function currying, type aliasing, and more. And Swift manages to do all this while maintaining smooth interoperability with Objective-C classes.
(For an admittedly-trivial demo of some of these features, here’s code for Minesweeper in Swift.)
With ideas drawn (in Chris Lattner’s words) from Haskell, Rust, C#, Ruby, Python, and the last twenty years of PL research and practice, Swift looks like a language even programming-languages nerds should find pleasing. It delivers what everyone wants from a language: an elegant way to interface with software.
More important than Swift’s elegance, though, is its context. Programming languages rise and fall not on language quality but on more-practical factors: which libraries and tools are available, what the industry standard is, and what’s most likely to get you a job. Swift is the first place all these factors converge: a highly relevant platform, a sole platform owner with the will to impose a standard, a human-friendly toolset, and a newly-modern language.
Have you ever wanted to start programming on iOS? Today’s the day.
Mancala is a traditional African two-player board game with many different variations. One variant of mancala, called Kalah, has a long history in AI research – see e.g. Silver 1961 (pdf), Bell 1968, Slagle and Dixon 1969 (pdf), and Irving et al 2000 (pdf).
Prolog is a logic programming language devised by Alain Colmerauer and his colleagues in the early 1970s. The idea behind the language is that you feed the computer a set of facts and rules, then ask the computer to use those constraints to answer questions about things you want to know.
For today’s practice, I tried to implement a program to play mancala in Prolog – specifically the version of mancala I learned as a kid, which has three seeds per hole (game rules are here). To solve the game, we can generate a tree of possible moves for each state and use minimax with alpha-beta pruning to find the optimal one. The code is here.
Your goal is to earn points by arranging pillows into piles of the same color. You earn 100 points whenever you make a pile of three same-colored pillows. You can only move the topmost pillow in each stack. To move a pillow, touch the stack it’s in, then touch the stack you’d like to move it to. New pillows are added at an increasing rate as the game level increases, and the game ends when any stack reaches the top of the screen.
Let’s try to implement the FFT in F#. First, here’s the naive DFT algorithm (a direct translation to code of the definition):
This gives an exact answer, but with poor performance – this has O(N2) time complexity. To improve performance, we first reduce problem scope by assuming that the number of input terms is an integral power of 2, letting us use the radix-2 DIT divide-and-conquer algorithm. This splits the DFT into two DFTs – a DFT of the even-numbered and a DFT of the odd-numbered terms:
This is fast – O(n log n) – but only handles signals with lengths of integral powers of 2. To use the radix-2 algorithm for a signal of arbitrary length, we need to increase length to the next smallest power of 2. We can’t zero-pad the signal itself, but if we express the transform as a convolution then pad the convolution we’ll get an exact answer. (My hour’s up, but if you’re interested the convolution algorithm is explained here.)
In the equation
where x, y, and n are positive integers, what is the least value of n where the number of distinct solutions (i.e. solutions where x, y does not recur as y, x) exceeds 1000?
Since x, y, and n are positive integers, we know that x and y must each be greater than n. Thus, we can rewrite (1) as
where a and b are again positive integers.
Doing some algebra, we get:
This means that each distinct pair of divisors of n2 represents a distinct solution to (1). Thus, if we can find the number of divisors that n2 has, we’ll know that half that number (well, actually divisors(n2) + 1 / 2 because one of the divisor pairs – n * n = n2 – won’t be doubled) is the number of solutions to (1).
Now we just need an algorithm to find the number of divisors of a given integer m. An easy way to do this would be to enumerate each of the numbers up to sqrt(m) and count each number that divides m evenly as a divisor. Since we’re going to use this algorithm many times, though, this brute force approach won’t work.
Instead, we’ll use the divisor function. This tells us that we can obtain the number of divisors of m from its prime factorization. Specifically, the number of divisors of m is the product over all distinct prime factors of the power of the prime factor, plus 1. (That is, if we can write
then we have
.) Think of it this way: each distinct divisor of m is some distinct combination of m’s prime factors, and each prime factor can appear 0, 1, …, or si times, so multiplying through for each of the prime factors we get (7).)
Now we just need an algorithm to factor a number into primes.
We can use a (pseudo-)sieve of Eratosthenes to generate a seed list of potential primes:
We use the list of primes to obtain the prime factorization:
Factoring n2 still takes some time, though, as n2 grows much more quickly than n.
Luckily, we can factor n instead. From (6) we can see that
so with the same combinatorics that gave us (7) we have
Now, finally, we can find the solution using (9):
And obtain the solution using an (empirically-determined-to-be) appropriate max prime seed:
This gives us a final answer of 180,180.
Meant to have a crack at #110 today also, but this problem took an embarassingly long time to solve.