Sum of Egyptian Fractions

A friend recently posed me the following question: for an integer n, how many pairs of positive integers (a,b) exist for which

\frac{1}{n} = \frac{1}{a} + \frac{1}{b}?

Call this number F(n). Here is my solution. We will count the number of positive integers a for which there exists a corresponding b.

First, note that a b exists if and only if the numerator of \frac{a-n}{an} cancels when the fraction is put into lowest terms, in other words, if and only if a-n\vert an.

 

Lemma 1: F(n) is equal to the number of integers a>n for which a-n \vert (a,n)^2, where (a,n) denotes the greatest common divisor of a and n.

To see this fact, write a = x(a,n) and b = y(a,n). Then (x-y) \vert x y (a,n). Since x and y are relatively prime, x-y is relatively prime to both x and y, so (x-y)\vert (a,n), or (a-n)\vert (a,n)^2.

 

Lemma 2: F(n) is equal to the number of integers a>n for which a-n \vert n^2.

We will show that this set of as and the set of as given by Lemma 1 are in bijection. First, if a-n\vert (a,n)^2, then clearly a-n\vert n^2 since (a,n) is a divisor of n.

Now suppose (a-n)\vert n^2. Then a-n is equal to a divisor d of n^2. We can write d=d_1d_2 where d_1\vert n and d_2 \vert n. Therefore both d_1 and d_2 divide the right-hand side and so divide a, so both are common divisors of a and n and so d_1\vert (a,n) and d_2 \vert (a,n). Therefore d_1d_2 \vert (a,n)^2.

Since for every divisor of n^2 we can solve for a unique a>n, we have

 

Answer: F(n) = d(n^2), where the divisor function d(x) counts the number of positive divisors of x. Note that this F counts unordered pairs. There are \frac{d(n^2)+1}{2} unique ordered pairs with a \leq b. For n=10^7, there are 225 pairs (113 ordered pairs).

d(n^2) can be computed naively in O(n) by finding n's prime factorization using trial division. Possibly there are faster algorithms.

 

Footnote: Like the divisor function, F is multiplicative: if (x,y) = 1, F(xy) = F(x)F(y). Maybe there's a way to see that directly and use it to derive a formula for F in an alternate way (by first finding a formula for F(n) when n is a prime power.)


Four TV Shows That Don't Suck

I'm listing here four TV shows I've enjoyed in the past and highly recommend, so that I can point people here when I'm asked for procrastination material. I'm avoiding the obvious popular picks everyone has already seen (so no Firefly, Arrested Development, The Wire, Dexter, South Park, etc.) and focusing instead on shows that are older or haven't gotten as much attention.

Babylon 5

Where to watch it: Tvlinks

Why you haven't watched it: It's a science fiction series set on a space station... that aired at the same time as Deep Space Nine.

What it's about and why it's awesome: I recommend Babylon 5 to people with the same trepidation as when setting up an eccentric friend on a blind date. The show has a lot of good qualities going for it that become evident if you stick with it -- I'll come right out and say that it's the best story I've ever seen told on TV, ever -- but first impressions matter, and your first impression of Babylon 5 won't be good.

There's no use beating around the bush: the first season is quite terrible. The acting is bad: only about half of the main cast can act, and this half does not include the captain, the main character.1 There are many filler episodes with bad writing: clichéd, stock science fiction plots on the one hand, and painfully clumsy, thinly-veiled allegories about contemporary issues on the other. (A child will die without a life-saving surgical procedure; the parents refuse consent for religious reasons. What should the doctor do? An interesting ethical dilemma, to be sure, and one that cannot be satisfactorily treated on an episode of a science fiction show.) And the less said about the CG, the better: slapping a low-res texture on a rotating cylinder may have been state of the art in the early nineties, but it's certainly not today.

If you stick with the show through its first season, though, these problems largely go away,2 and your payoff is a brilliantly intricate and polished story told over three seasons with much-improved production values. The reason: J. Michael Straczynski, the show's creator, outlined all five seasons of the story (later condensed to four seasons) in advance, and moreover starting in season two wrote the vast majority of the episode scripts himself.3 A result of this planning is that almost all episodes of the first season, even the terrible ones, contain some background event or off-the-cuff remark that seems insignificant filler at first but sets up a payoff several seasons later. (Any time a character makes any kind of prediction or prophecy: pay attention!) The attention to detail, consistency of characterization, and ambition of the plot and themes is almost novel-like. If you value good storytelling, this show's for you.

Notes: Danger! Watch seasons 1-4 only. JMS thought the show was going to be canceled after season 4, so squeezed all of his original story into these first four seasons. Season 5 was thus written as an afterthought (and it shows); moreover this last season introduces several new, annoying characters. Avoid. Lastly, though Babylon Five is the closest a TV show has come to being a visual novel, that novel is a meandering epic that could benefit from tightening and editing (think late Neil Stephenson.) Mediocre B-plots still show up regularly once the show has hit its stride.4

 

Great Teacher Onizuka

Where to watch it: Youtube

Why you haven't watched it: It's an anime not called "Cowboy Bebop."

What it's about and why it's awesome: The titular Onizuka -- illiterate, perverted, and broke former leader of a bike gang -- applies for a job teaching high school, for the sole purpose of seducing high school girls. He gets assigned to a middle school class instead: a notoriously troubled one, whose students hate all teachers (for diverse reasons revealed throughout the show); he quickly discovers he has a conscience and a passion for teaching after all, and resolves to become the best teacher in Japan, solve all of his class's personal problems, and make school fun again.  Thanks to his stubbornness, cunning, physical indestructibility, and unwavering faith in his students, he wins the class over one by one, despite being the target of constant plots to get him fired, discredited, and/or killed by the other students as well as by faculty / the vice principle / PTA members / education critics5 who are alarmed by his unconventional teaching methods and lack of refinement.

Great Teacher Onizuka is at its heart a comedy, and like Onizuka himself never takes itself too seriously. This light touch keeps the show's handling of the expected middle school themes and arcs -- bullying, broken homes, social drama -- on the right side of the line separating heartwarming from Aesoporiffic, and at its best succeeds in being truly inspiring. Any show that can wring a drop of such praise from this heart of solid jade is worth a look.

Notes: The pacing of the show decreases significantly about halfway through, after the Urumi Kanzaki arc: it picks up again for the last few episodes, but in between is quite a bit of lower-quality (but by no means aggressively bad) filler that can be safely skipped.

 

Dr. Horrible's Sing Along Blog

Where to watch it: Youtube

Why you haven't watched it: Dr. Horrible's... Sing Along... Blog. Three parts to the title, three good reasons to suspect the entitled work probably sucks.

What it's about and why it's awesome: Ok, so not really a TV show -- more a three-episode musical miniseries, published direct-to-web during the writer's strike three years ago (but since it's so short, all the more reason you should go watch it, if you haven't already.)

Neil Patrick Harris plays the adorably incompetent wannabe villain Dr. Horrible. He aspires to (forcible) change the world by joining the Evil League of Evil and becoming a card-carrying supervillain. To do so he must prove himself to the League by successfully committing a high-profile crime; this is a rather tall order since 1) his inventions don't work, 2) he's not really evil at heart, and 3) his nemesis, hero-in-name-only Captain Hammer, always disrupts his schemes. And then Captain Hammer starts dating Dr. Horrible's crush...

I'm by no means a Joss Whedon fanboy: Firefly was brilliant, but I found Buffy and Angel thoroughly mediocre, and will invoke the Golden Rule and say nothing at all regarding Dollhouse. This musical, though, is Joss at his best: campy and quirky, funny and clever, but with a serious theme underlying it all. The writing is crisp and tight and the pace frenetic -- blink and you'll miss a joke, in a way reminiscent of Arrested Development. The story -- well, I'm a total sucker for this type of story.6 I can't say much without spoiling the ending, but pay close attention to how Dr. Horrible transforms over the course of the show; it's artfully done.

Veronica Mars

Where to watch it: Tvlinks

Why you haven't watched it: Yet another teen high school show.

What it's about and why it's awesome: Veronica, teenage daughter of a private investigator, helps her dad solve her best friend's murder. That's the season-long framing story; each episode focuses on Veronica solving a more self-contained mystery (who rigged the school elections, who stole the money at a poker game, why did a student join a cult -- that kind of thing) while slowly advancing the main plot. Think Nancy Drew but snarky, cynical, and played by Kirsten Bell.

The show is notable for pulling no punches with the mature themes it explores, and for its morally ambiguous view of the main characters and the world. The first episode alone includes teenage drinking and sex, class warfare, racism, date rape, and of course murder; and it doesn't get much lighter from there. Very few of the characters are portrayed in a purely sympathetic light -- Veronica's dad and her sidekick Wallace are the two that come closest -- nor does the show have many true villains. Veronica herself (setting aside the ethical flexibility that comes with the job of being a PI) doesn't hesitate to exact elaborate revenge on those who embarrass or slight her. The random students she agrees to help are invariable somehow responsible for the trouble they're in, or have their own agenda. Logan, jerkass (and hilarious) entitled rich kid and Veronica's main enemy at school, is shown to have a dysfunctional, abusive family and occasionally has his moments of heroism. And so on.

The mystery itself is quite well-constructed; the clues come slowly enough and have enough red herrings to invite mass viewer speculation, and by the end of the season the whole web holds together consistently, the killer is plausible but by no means obvious (always a difficult balance on a TV show, since the killer must be someone the audience has been introduced to over the course of the show, but draw too much attention to a random minor character and you give up the game...) The individual episode plots are more variable,  but even the lamer ones are worth watching for Veronica and Logan's snarky asides alone.

Notes: Danger! Watch the first season only. Individual second season episodes have their moments, but the season-long overarching mystery doesn't hang together nearly as well. I haven't watched the third season myself, but I have it on good authority that it's terrible.

Bonus section: Three shows everyone loves that actually suck

The Office: Dealing with these kinds of people in the real world is draining enough... I don't want to watch more of them on TV.

24: I don't have time to explain.

Lost: The anti-Babylon 5; an intellectual Ponzi scheme. It's not at all hard to write a mystery with a veneer of complexity and intricacy, after all: just keep making stuff up as you go along, with no clear idea of how the plot will eventually tie together consistently and resolve.7

 

  1. It does, fortunately, include the alien ambassadors Londo and G'kar, who across all four seasons have by far the most intricate and compelling character arcs. []
  2. Well, except for the CG. []
  3. Since it's never certain whether or not a TV series will be renewed each season, almost all other shows, even the better, arc-driven ones, are written season by season. And a single person writing all of the scripts is unheard of -- usually the creator is only personally involved in the most important episodes, with other scripts rotating between members of the writing staff and guest/freelance writers. []
  4. JMS has some kind of obsession with plots involving old flames, for instance. None of these are good. []
  5. Either these last two groups are waaaayyyy more powerful in Japan than in the United States, or there's heavy use of artistic license here... []
  6. People usually can't articulate what they really want, and those who do are usually dead wrong. Incidentally, "what do you want?" plays a central role in Babylon 5... []
  7. X-Files was an even more egregious example of this kind of writing, but doesn't have Lost's popularity. []

Vouga of Arabia

Last week was Eid al Adha (a.k.a. "Hajj break"), which for me meant only that there were less students around campus, and a lot of the facilities were shut down. I did get the opportunity, though, to take the bus into downtown Jeddah and do some shopping and sightseeing.

There are really only two places you can go outside of campus. The first is Thuwal, a fishing village right outside and visible from KAUST. The dining hall on campus is a typical cafeteria, serving generic international food;1 restaurants in Thuwal offer quite a different experience. To begin with, the dining area is segregated into different section, neither visible to the other: one for men, and the other for families. (In practice, a family is any group of people containing at least one woman; even groups of obviously different races don't raise any eyebrows. At least around here -- I've heard that in the more conservative regions of the country, near Riyadh, "family" might be interpreted more literally.) Secondly, the customary way of eating is on the floor, on a carpet, with no utensils. Over the past few years, though, the amount of business coming in from KAUST has encouraged restaurants to slowly invest in western concessions: they have a few tables and chairs they keep in the back, and a few sets of silverware, that they bring out as needed. Thirdly, at a seafood restaurant I visited a few weeks ago, the main course wasn't ordered off of the menu: instead, you first visit a fish market in a building next door, and pick out the fresh fish you would like to eat. Only after you've selected your dinner, haggled a bit over price, and informed the staff how you'd like the fish cooked, do you get seated and order drinks and sides off of a menu.

The second possible destination is Jeddah, the largest city in the area (population ~3 million) and about 45 minutes away from KAUST.2 A bus travels there and back once a day, which is lucky because I wouldn't want to drive even if I owned a car: lanes are strictly suggestions (and the shoulder of the road counts as a lane), driving over sidewalks and medians is the accepted way of taking shortcuts and U-turns, feral donkeys and camels wander onto the street, etc etc. Only in Boston have I seen crazier drivers (where, in addition to the ubiquitous double-parking, I've witnessed one clever guy's solution to one-way streets: drive at full speed in reverse.)

The bus makes three stops in Jeddah: the Mall of Arabia, Red Sea Mall, and downtown. I've never been to the first two (and I'm not particularly interested in doing so.) I was warned by a coworker: if you visit downtown Jeddah by yourself, take a map and a compass, and give yourself two hours to find your way back to the bus. I completely ignored him, of course, and got horribly lost. Jeddah's downtown is a vast labyrinth of twisty streets and alleys, with a scattering of larger shopping centers and hundreds of smaller stores selling incense, carpets, clothing (including abayas; I promised to pick one up for a friend), bars of gold, more different kinds of dates than I ever imagined existed, etc. The shopkeepers are all terrificly friendly. Haggling over everything is a little off-putting at first, but eventually you realize that you're arguing over what amounts to less than a buck or two.

The mosques at KAUST announce the five daily prayers, but unless you are unlucky enough to live directly under the minarets of the campus Grand Mosque the prayer times have no significant effect on daily life. Not so at all in Jeddah. When a prayer time begins, all customers are kicked out of stores and the stores close, for a not insubstantial amount of time. According to coworkers, one trick is to order take-out right before the prayer begins, and eat while waiting for it to end; of course, this strategy still requires knowing when the next prayer will begin, which changes daily. Another unique aspect of shopping in Jeddah is that stores tend to be clumped into groups offering identical wares: one block will be entirely devoted to carpets, the next to paint, etc. At first this arrangement didn't make any business sense to me: if you're opening a carpet store, why place yourself right next to your competitors? But it was explained to me that this system has established itself as a Nash equilibrium of sorts: customers looking for a carpet know to look (only) on the carpet store block, and a carpet vendor trying to set up shop elsewhere would only starve himself of customers.

  1. the one exception, of course, is the lack of pork: "bacon" here always means small bits of beef. []
  2. Mecca and Medina are also nearby, but strictly forbidden to non-Muslisms. []

The Most Irrational Number

What is the most irrational number? In a sense this is an ill-posed question: we can surely agree that a rational number cannot qualify as "most irrational," but beyond that we could well have very different ideas of what "more irrational" means. Is \sqrt[3]{2} more irrational than \sqrt{2}? Is a transcendental number like \pi more irrational than an algebraic number like \sqrt{2}?

One possible approach is to call a number more irrational if it is harder to approximate using a rational number. We can visualize geometrically how easy it is to approximate a given irrational number \xi: take the plane, and place a dot at every point (x,y) with integer coordinates, such as (0,0), (1,0), (3,4), (-8, 10) and so on. Such points are called lattice points. Placing a dot at every lattice point gives you a square grid of points (like if you take graph paper and draw a dot everywhere a horizontal and vertical line meet).

Now start at the origin, and draw a line of slope \xi. Since \xi is irrational this line will never hit a lattice point (otherwise the slope of the line, and hence \xi, would be rational). But the longer you make the line, the more near misses there will be where the line passes right by a lattice point. A line that very quickly comes very close to hitting a lattice point can be better approximated by a rational number than one that avoids coming near a lattice point for as long as possible.

We can construct concrete rational approximations of \xi: the simplest thing we can do, for instance, is simply take the floor: \lfloor \xi \rfloor. This splits \xi up into an integer part and a fractional part:

\xi = \lfloor \xi \rfloor + (\xi-\lfloor \xi \rfloor) = a_1 + r_1,

where a_1 is an integer and 0 < r_1 < 1. a_1 is a rational approximation of \xi (although quite a bad one.) \frac{1}{r_1} is a number greater than 1, so we can improve on this naive approximation by writing

\xi = a_1 + r_1 = a_1 + \frac{1}{\frac{1}{r_1}} = a_1 + \frac{1}{\lfloor \frac{1}{r_1} \rfloor + \left(\frac{1}{r_1} - \lfloor \frac{1}{r_1} \rfloor\right)} = a_1 + \frac{1}{a_2 + r_2},

where a_2 is a positive integer and r_2 again satisfies 0 < r_2 < 1. Forgetting about the r_2 gives a new rational approximation a_1 + \frac{1}{a_2}.

Now we can again write r_2 and \frac{1}{a_3 + r_3}, and then do the same thing with r_3, and so on over and over again until we have an infinite continued fraction

\xi = a_1 + \cfrac{1}{a_2 + \cfrac{1}{a_3 + \cfrac{1}{a_4 + \cfrac{1}{\ddots}}}}.

Truncating this continued fraction after a_n gives a rational number called the n-th convergent of the continued fraction. These convergents are increasingly better approximations of \xi. For example, here are the first few convergents when \xi = \pi:

\begin{align*}3 &= 3\\3+\frac{1}{7} &= \frac{22}{7} \approx 3.143\\3+\cfrac{1}{7+\cfrac{1}{15}} &= \frac{333}{106} \approx 3.14151\\3+\cfrac{1}{7+\cfrac{1}{15+\cfrac{1}{1}}} &= \frac{355}{113} \approx 3.1415929\\3+\cfrac{1}{7+\cfrac{1}{15+\cfrac{1}{1+\cfrac{1}{292}}}} &= \frac{103993}{33102} \approx 3.1415926530.\end{align*}

Some of these convergents should look familiar. In fact, the convergents of the continued fraction of \xi satisfy several remarkable properties:

  • The convergents are the best possible rational approximations of \xi, in the sense that any other fraction with denominator less than or equal to that of the n-th convergent is a worse approximation of \xi.
  • The convergents alternate between overestimating and underestimating \xi, with \xi sandwiched between them.
  • Two successive convergents \frac{n_i}{d_i} and \frac{n_{i+1}}{d_{i+1}} bound \xi to within \frac{1}{d_i d_{i+1}}.
  • The a particular a_i in the continued fraction is large, the i-1-st convergent is a particularly good approximation of \xi. (This makes sense, since a_i large implies r_{i-1} small. This fact explains why 355/113 is such an accurate approximation of \pi for its denominator: the next value of a is quite large (292).
  • The larger the values of a_i on average, the faster the convergents converge to \xi.

The first and last properties give us a tool for answering our original question: the irrational number that can be least well approximated by rational numbers is the one whose convergents converge most slowly, i.e., the one whose a_i in its continued fraction are the smallest. a_i must be positive (except for the integer part a_1; we'll arbitrary set a_1=1), so the most irrational number x has continued fraction

x = 1 + \cfrac{1}{1+\cfrac{1}{1+\cfrac{1}{1+\cfrac{1}{1+\ddots}}}}.

We can even solve for x, using the "fractal expression trick." If the continued fraction above converges (which is plausible, and not hard to show) it must converge to a fixed point of the map

x = 1+\frac{1}{x}.

Solving for x gives the quadratic equation x^2 - x - 1=0, whose only positive root is \frac{1 + \sqrt{5}}{2} -- the golden ratio \phi!

 

So in this sense \phi is the most irrational number. If two notes have frequencies in the ratio of \phi, does this fact imply that their interval is the most dissonant possible?1  While in NYC I tried to find tuning forks I could modify to test this hypothesis -- but it doesn't seem like any music stores (at least none of the ones in Manhattan) sell them anymore. (I was surprised to discover that there's still quite a large market of them online, however -- many sites sell (grossly overpriced) tuning forks for use in some kind of "sound healing" quackery.)

  1. The tritone sounds dissonant on stringed instruments like the piano or guitar because the overtones interfere. Flutes and tuning forks are much better at damping high frequencies, so notes played on these tend to be much purer: if you form a tritone by playing two flutes or ringing two tuning forks the interval sounds quite consonant. []

Lessons Learned Volunteering on an Internet Project

Zelda Classic started out, in the dark forgotten days of DOS, as a clone of the very first Nintendo Zelda game, painstakingly reverse-engineered by a pair of high school students in Ohio. What set it apart from the numerous other ROMs and pirated copies of the game on the Internet was the "quest editor" bundled with it: using this simple graphical editor, fans of the game with no particular experience programming could quickly and easily create their very own game, with completely new levels and graphics, but the same Zelda look and feel.

Over time the game grew in popularity and functionality: the original creators moved on to other projects, but new programmers picked up where they left off and ported it to Windows, modernized some of the user interface, and added many, many new features to the quest editor. It became possible to create games with polish rivaling the official Zelda games on the Super Nintendo and Gameboy.

Zelda Classic was at its apogee around the time I first became involved with the project's development seven years ago; it had been featured on TechTV's show The Screen Savers, and in EGM magazine, and as a result more users than ever were playing the old fan-made "quests" and creating new ones. Zelda Classic was downloaded over a million times, and several hundred fan-made quests were submitted and "published" on the official site.

But whereas the fan community was thriving, development had stagnated. The last stable release was years old; newer betas had occasionally been publicly released, but these betas were notoriously buggy and widely avoided. Under the theory that fresh blood would hurry things along,1 a call went out for new developers. Devoting time to a project one good cease-and-desist letter away from being permanently shut down wasn't going to make me rich or famous, but it looked like a fun way to hone my coding skills. I signed on.

I wasn't Zelda Classic's original programmer, nor was I ever the lead programmer during the time I actively contributed to development. But I left a significant mark on the project and am proud my accomplishments: the C-like scripting language I added to the quest editor is one of its most ambitious and complex features; I led the team in number of bugs fixed; and I became webmaster of the code repository, official project site, and associated community forums.2 Most importantly, I experienced first-hand the challenges of working on and leading a large, popular, volunteer software project. Below are the three most important lessons I learned during this experience.

 1. The allure of Cool Things is irresistible.

When a programmers volunteers to work on a project, she does so because she is full of ideas about Cool Things that need to be added to the project, as soon as possible. This feeling is completely understandable: everyone who's used a tool for long enough accumulates a long list of ways the tool could be improved. Fixing bugs is boring, time-consuming, and thankless. Adding a new feature, on the other hand -- especially a Cool, flashy, long-requested one -- is fun, brings glory, and satisfies the basic human need to press hands into new sidewalks, to leave a mark that you can later point to and say, "I was there, I contributed to that!" If the new feature doesn't quite work right at first, or doesn't play well with the Cool Things that others added yesterday, well, there's plenty of time to fix that tomorrow, when/if the natives complain enough.

The problem only gets worse as times goes on, due to combinatorial explosion. In the original Legend of Zelda, for instance, there are bodies of water blocking the player's path, that can only be crossed in one of two ways: by using a stepladder, or riding a raft. Code is needed to make sure nothing breaks if the player tries to use the ladder while already riding the raft, and vice versa. Easy.

Now we add a new way to cross water: flippers that give you the ability to swim. There are four ways adding flippers might break the code: what happens if the player tries to use the raft or ladder while already swimming through the water? What if he tries to dive off of raft or ladder while wearing flippers? All of these possibilities must be taken into account.

Now we add a new item that lets the player jump short distances. The player can use this item to jump across narrow streams. He can also jump into lakes -- if he has the flippers, he'll dive in and start to swim; otherwise, he'll drown. Can the player jump into or across water if he's already standing on the ladder or raft? We have to write code to deal with that. What if the player tries to use the ladder or raft while in midair over water? Clearly that shouldn't be allowed. And wait -- what if he tries to jump while already in the water, swimming with the flippers?

Every new feature added exponentially increases the number of possible interactions, and thus the number of bugs, since some of these interactions are inevitably missed. Debugging starts to feel like a Sisyphean task, as the system becomes complex enough that a "fix" for one bug introduces a new bug somewhere else.

We tried several strategies to keep testing and debugging manageable: we recruited as many users as we could to perform beta testing; we decreased the time between releases of betas, to tighten the testing and feedback loop; we urged voluntary "feature freezes" where only changes to the code that fixed bugs, and added no new features, were allowed. These measures helped, but weren't enough: without managers or deadlines we simply didn't have the self-discipline to 1) carefully consider the long-term consequences of the changes we introduced; 2) adequately test our changes; or 3) force ourselves to slow down and ship something stable before moving on to the next Cool Thing.

There are several measures open-source projects have taken to solve this problem: mandatory review of every change by a second developer; more central leadership with one person ultimately responsible for deciding which features to include and reject; separate branches for experimental new features still being worked on, and for well-tested new features that will definitely be included in the next release; etc. I woudn't start any new project with as large a scope as Zelda Classic without thinking very seriously about how to reign in feature creep, keep developers on target, and ensure development sticks to a coherent long-term plan.

2. The user community is your most valuable resource.

I've been very impressed by the quality of the custom quests created by users with Zelda Classic -- as I mentioned before, many of these are larger, more polished, and more fun than even the official Nintendo games, and I can't imagine how many hours of time must have gone into crafting them. Equally impressive, though, was the amount of effort the community was willing to contribute to the project.3 Us programmers had barely enough time and resources to do the programming... from beta testing, to marketing, to helping new users work the program, to designing and maintaining the web site, many tasks crucial to the smooth running of the project were handled by fans of Zelda Classic who volunteered their talents, unsolicited.

The corollary is that the user community is an Internet project's most valuable resource. The most ominous sign I see for the future of Zelda Classic is that this community has slowly dwindled over the last few years. The lack of a recent new version of the program is partly to blame, but there were several other preventable factors at play. Firstly, the official forums were repeatedly hacked and infected with malware, leading many users to abandon the forums and the project altogether. Secondly, as Zelda Classic grew in popularity, the community divided into two camps: friends of the original programmers, early adopters, and other users who had been around from the very beginning; and "newbies" who had only recently heard of Zelda Classic and decided to check it out. The former became vested contributors -- people who, by virtue of their having been around the longest, and having contributed most to the project, felt they were entitled to greater privileges, and fewer rules, than the new arrivals. The former resented the later for being on average younger and less mature, and asking many basic questions; the latter resented the former for being arrogant, rude, and cliquish. This friction grew until the community split, with most of the newer users migrating to their own, more welcoming community. The code itself didn't fork -- it couldn't, being closed-source -- but the code was hardly the project's most precious resource -- the users were.

Incidentally, vested contributors are a significant problem facing many collaborative efforts on the Internet -- Wikipedia and Stackoverflow and two such projects that spring to mind. For both of these projects I predict overindulgence of vested contributors as the most likely point of failure.4

3. You can't take back moves.

As you release new versions of software, there are two approaches you can take to deal with user data (in the case of Zelda Classic, user-made "quests") created with old versions of the program:

  • The Apple approach: You don't worry about backwards-compatibility. Each version of your software makes a clean break from previous ones. This is the case for different version of Apple's operating system: if you're lucky, the program you wrote for one big cat continues to work on the next one, but there's no guarantee it will do so. This approach is great for the programmers of Mac OS, as it gives them the freedom to start completely from scratch, learn from their mistakes, and redesign or ditch completely those features of the operating system that didn't work as well in practice as they'd hoped. It's not so great for the application programmers: the burden of making sure the application continues to work over time has been passed down to them.
  • The Microsoft approach: You try to keep your software as backwards-compatible as possible. Programs written for Windows XP or Vista (and, for sufficiently popular programs, even Windows 95 or DOS) continue to work on Windows 7. This situation is ideal for application developers: they write a program once, and Microsoft, not them, has to worry about it continuing to work in the future. It's also great for users of the program, since the program continues to work even if its developers go out of business, get hit by a bus, etc. But maintaining backwards-compatibility forces Microsoft to be very conservative about what it changes from version of Windows to another, and forces Microsoft to bloat its software with components that serve no purpose but tricking old programs into thinking they're still running on e.g. Windows XP, so that they continue to work correctly.

Zelda Classic chose the Microsoft approach long before I joined the project. It's the approach that's friendliest to end-users, and so is a natural choice for a free program entirely reliant on its user community for survival. But it's a choice that has cost us dearly in terms of program complexity.

Suppose you're using Zelda Classic to make your own quest, and you decide you want to make the player lose his sword midway through the game (he gets robbed by bandits, say.) You look through Zelda Classic's features, but see no way of taking away an item that you've already given to the player. You ask on the Internet if anyone has any suggestions -- and another user tells you that, although there is no official way of taking away the sword, there's a bug in the current version of Zelda Classic where if you try to give the player a second sword while he's holding his sword, a shield, and is facing left, the player loses both swords instead. "Perfect!," you think. You've found a creative way of working around the constraints imposed on you, and you can put that bandit scene into your game after all.

Years later, someone reports that giving players a second sword isn't working correctly in some cases. We investigate, find the bug, and fix it -- but now all kinds of old quests aren't working anymore; bandits are robbing players but the sword doesn't disappear. And we promised old quests would continue to work flawlessly in the future! "Oh come on," we might grumble. "What were you thinking?!? You're obviously exploiting undocumented, buggy behavior. How could you possibly think it's a good idea to rely on this bug?" But there's no telling how many other people also discovered and exploited the bug, and we don't want all of their quests to stop working, so we grit our teeth and modify our code: if a quest was created before a certain date, use the buggy sword addition code. Otherwise, use the new, correct sword addition code.

This situation happens all of the time: a sufficiently large group of users is infinitely ingenious and no more immune to the danger of Cool Things than the developers. If features can be combined in unintended ways to create a neat effect, they will find the combination and use it. They will find undocumented features used for internal testing. They will find bugs and exploit them.  And you will only find out after you make a seemingly-innocent change to the code and discover it breaks a bunch of old quests.

Another consequence of backward-compatibility is that every new feature you add becomes an indefinite commitment. If the feature is poorly thought out, it will hamstring you. Over time Zelda Classic has accumulated many such missteps -- options and settings that almost nobody ever uses, but that interact in complicated ways with the rest of the program, and are endless sources of bugs. For more experimental features, we tried telling users, "this new feature is strictly beta. We might take it out at any time; please don't create quests that rely on it." We even incorporated a popup window with that same message into the program itself. Users would rely on the feature anyway, with the best intentions: at first they just wanted to play around with it and test it. But as they invested more and more time into works in progress depending on the feature, they became increasingly reluctant to give it up.

Striking a balance between backwards-compatibility and freedom to revisit past mistakes is a challenge even Microsoft is struggling to solve, and there are no easy answers. But there are several things Zelda Classic could have done differently to partially tame the problem. Most importantly, and relating back to the first lesson, we could have been more conservative about which features we expose to the public. We could also have compromised a bit on backwards compatibility; if I were to start over from scratch, I would wrap Zelda Classic in a meta-program that detected what version a quest was created with, and downloaded that version of the quest player if needed, instead of trying to make the most recent version of the quest player compatible with all old quests.

 

  1. This is a classic blunder, almost as well-known as "never get involved in a land war in Asia" and "never go against a Sicilian when death is on the line." []
  2. A role I still hold, more by default than any abundance of spare time, or love of web work. []
  3. Perhaps I shouldn't be too surprised, since I too was "the community" before signing on as a programmer... []
  4. Though Wikipedia has quite a few other problems. []

Being on the Red Sea Does Have Its Advantages

The KAUST marina offers daily snorkeling and diving trips at very reasonable prices; Friday aka "Sunday"1 six of us took advantage of this and rented a yacht for a morning at the reef.

The trip from campus to the reef takes about 45 minutes, including a detour to and inspection by the nearest coast guard station. The boat was outfitted decadently, in typical Saudi style, and made this trip extremely pleasant: an air-conditioned indoor lounge area had at least three TVs (which we didn't use), a sounds system (that played mostly acoustic covers of Beatles songs -- odd but fitting), three fully furnished bedrooms for those wanting to nap, and a kitchen area well-stocked with sandwiches, salads, drinks, fruit, brownies, profiteroles, danishes, etc for brunch. The crew was very friendly, and shared stories of their own experiences moving to KAUST, and working at the marina the past two years.

The Red Sea has over a thousand miles of coral reefs, the only ones in the world unaffected by bleaching due to global warming -- the algae living there are temperature-insensitive, for reasons not understood.2 According to our captain many of these reefs aren't marked on GPS, for which reason, together with unpredictable currents, he avoids navigating at night. Every now and then I spotted a small island poking up out of the reef, dotted with a building and maybe a tree or two: private islands belonging to the King or princes, and strictly off-limits.

The water was beautiful turquoise, bath-temperature (slightly warmer, even), with almost no wind and good visibility. We were warned to watch out for strong currents, and a guide came snorkeling with us in case we had any problems, but despite being a poor swimmer I could navigate with very little effort. We saw an eel, several rays, a huge tuna, and countless other fish I couldn't begin to identify. No sharks, unfortunately. If we had brought spear-guns we could have taken the tuna home for dinner -- a popular Saudi pastime, apparently.

Despite glazing myself in a thick coat of SPF Infinity sunscreen I unsurprisingly still managed to burn myself to a crisp, especially my scalp -- if I'd been clever I would have remembered Barbados and grown out my hair before coming here. But oh well, so worth it.

  1. The Saudi weekend is Thursday-Friday, with Saturday and Sunday ordinary workdays. []
  2. At least as of five years ago. []

On Moral Proscription

When we were children our parents demanded that we adhere to a bevy of family rules. Some of these we see in retrospect as common sense, enacted to protect us from credible danger: don't play in the street. Don't get in the car with strangers. Hazards our younger selves, with their incomplete understanding of the world and adult life, could not competently evaluate or even conceptualize.

Others we now see as well-meaning but misguided attempts at protecting us from imagined dangers; "old wives' tales" conceived in the murky past and propagated from generation to generation, despite having been debunked: don't swim for 30 minutes after you eat. Don't go out in the rain or you'll catch a cold.

Still others were simply expedients for maintaining order and control in the house: no dessert until you've finished your chores.

If challenged, perhaps our parents offered patient rational explanations for why the rules were what they are; perhaps they were even willing to engage in extended arguments over whether or not they were in fact "not fair!" But at the end of the day they held the trumps, "because I said so" and "because that's the way it is," and we obeyed because we did not have the power or will to do otherwise, and for the most part we've turned out better for it.

But now we've grown up, as has our common sense, reason, and experience. We've chosen to reevaluate and reject many of the more arbitrary and restrictive prohibitions we once adhered to blindly: we cross the street when we judge it's safe; we accept the kindness of strangers. We weigh for ourselves the costs, benefits, and consequences of the choices we make. Doing so is difficult -- it's hard work, thinking, and so much easier to just let other people do it for you; and it's so painful when you weigh wrong, and hurt yourself or others -- but doing so is essential if we hope to engage the wider world and leave our mark upon it.

Thousands of years ago we were told, allegedly, not to murder or steal from each other, to never mix meat and cheese, and to stone our gays. Perhaps it's time the human race grew up?


Smells like... burning

"Life is but a beach chair"

It's almost November and at KAUST it stills feels like summer. How much like summer?

1) I can tell how bad the heat will be by how long it takes my glasses to defog after leaving a building. Less than five second means a nice balmy day, maybe even pleasant enough that a jog along the beach at sunset isn't out of the question. More than fifteen seconds and it was probably a mistake leaving the building in the first place.

2) The walk from my house to work takes about 15 minutes,1 in the early morning and late afternoon when the heat is still bearable. Both ways the sun is to my left, resulting in an asymmetric sunburn on my neck and ear from the walk to work alone.

KAUST has a cinema that shows a selection of two movies each week: one worth the ridiculously cheap $3 admission, and the other a Bollywood film, or chick flick, or just plain terrible. This week the former was Rise of Planet of the Apes -- a surprisingly good movie, in fact, despite being a (terribly named) sequel and having a simplistic and predictable framing plot. (Scientist at Evil Corp develops a cure for Alzheimer's; when this cure turns out to increase the intelligence of healthy patients, Evil Corp sees only the profits and ignores safety to hurry the project along; Apocalyptic Consequences ensue, etc etc.) The expressiveness of the ape faces is particularly impressive, and the CG used to accomplish this enhancement is almost seamless.

What I'll remember most about the experience, however, is that about three quarters of the way through the movie the picture suddenly stopped. The same frame stayed projected on the screen for over a minute, than slowly became browner, then completely black in the center, then white. It took me a while to realize that the film must have melted, then burned way, inside the projector! At least that's what I assume must have happened -- there were no announcements or anything. I left the theater to look for someone in charge, or a way into the projector room, to no avail; after an awkwardly long wait during which I seriously considered just leaving and watching the ending on Youtube, the film started up again about 10 minutes into the next scene.

  1. There's also a bus that stops near my house every 15 minutes, but come on, I'm little inclined to propagate the "lazy American" stereotype. []

Plucking coefficients from power series

Suppose you have a power series

f(x) = a_0 + a_1 x + a_2 x^2 + \ldots + a_i x^i + \ldots

and want a formula for the sum of coefficients \sum_k a_k. That's easy: just evaluate f at 1.

What if you want the sum of only the even coefficients? Again, it's obvious how to do this:

\frac{f(1) + f(-1)}{2} = a_0 + a_1 \frac{1-1}{2} + a_2 \frac{1+1}{2} + \ldots = a_0 + a_2 + a_4 + \ldots.

What may not be obvious is that similar formulas exist for plucking out the sum of every n-th coefficient (starting with a_0) for any n. The formula is simply

\frac{\sum_{j=1}^n f(\xi_{j,n})}{n} = \sum_k a_{kn},

where \xi_{j,n} are the n-th roots of unity, or complex roots of the polynomial x^n-1. The name comes from the fact that raising an n-th root of unity to the n-th power gives 1 (the unit). An explicit formula for the j-th n-th root of unity is given by deMoivre's Theorem: e^{2\pi i j/n}. When n=1, 1 is the only first root of unity and we get the first formula for the sum of all coefficients. The second roots of unity are 1 and -1, and we get the second formula for every second coefficient. The fourth roots of unity are also well-known: 1, -1, i and -i (it is easy to see that raising any of these to the fourth power gives 1). Thus

\frac{f(1) + f(-1) + f(i) + f(-i)}{4} = a_0 + a_4 + a_8 + \ldots,

and so on for any n.

Why does the formula work? If we expand the right-hand side we get that

\frac{\sum_{j=1}^n f(\xi_{j,n})}{n} = \sum_k \frac{a_k}{n} \sum_{j=1}^n \xi_{j,n}^k.

When k is a multiple of n, the term in the right sum simplifies to a_k, because if k = cn then \xi_{j,n}^k = (\xi_{j,n}^n)^c = 1^c = 1.

It turns out that whenever k is not a multiple of n, the sum of the k-th powers of the n-th roots of unity is 0:

\sum_{j=1}^n \xi_{j,n}^k = 0,

which explains why all of the other terms in the right sum above are zero. When k=1 (and n\neq 1) the roots of unity form a regular n-gon in the complex plane, so it is intuitive why the sum of the first powers of the roots of unity (the average of the vertices of the n-gon) is zero. But what about higher powers?

Using the deMoivre formula we have

\sum_{j=1}^n \xi_{j,n}^k = \sum_{j=1}^n (e^{2\pi i j/n})^k = \sum_{j=1}^n (e^{2\pi i k/n})^j.

By switching the exponents around we've turned the sum into a geometric series; this series sums to

\sum_{j=1}^n (e^{2\pi i k/n})^j = \frac{ (e^{2\pi i k/n})^n - 1}{e^{2\pi i k/n} -1} = \frac{1-1}{e^{2\pi i k/n}-1};

when k is not a multiple of n, the denominator doesn't vanish and so the sum is zero.


It kinda feels like Houston again

 "I will go in this way, and find my own way out"

I went jogging at 10 PM, long after sunset, yet still I felt like I was working out in a sauna. The heat itself isn't all bad -- I'd estimate the temperature at night to be in the mid-80s -- but it's the humidity that's the killer. I sweat like a pig in the best of circumstances, and here I can barely go a mile without facing twin threats of blindness and dehydration.

The track itself is pristine1 and, like everything else at KAUST, criminally underused. This has been my strongest first impression: the campus has tons of facilities, from beaches to gyms (with indoor climbing walls and a bowling alley, in addition to the usual fitness equipment) to food courts to a golf course to a movie theater,2 but everywhere I go I run across maybe a dozen other people. Even walking to work it seems like I see more facilities people than students. According to a pamphlet I read while waiting to get my ID card there are 800 students on campus, and presumably that number will double by the time KAUST has been open a full four years, but right now it still feels eerily empty. Walking through my neighborhood I can almost imagine myself in a movie, scavenging a Houston suburb after the zombie apocalypse.

My house here is a ludicrous two-story affair, with the first floor alone easily as large as my (2-person) apartment in New York. I'm barely using half of the furniture in the bedroom, leaving the bedroom annex, library, and living room completely empty. The quality of the apartment does not quite match the quantity, however: it's obvious the place was built in great haste, and if you look closely you can see little defects everywhere like sloppy paint jobs, doorstops pointing the wrong way, curtain drawstrings that don't fully work, etc. Still, given that my NYC apartment has the hot and cold knobs in the shower reversed, a bathroom that only locks from the outside, no curtains whatsoever, and an occasional rodent problem, I'm hardly going to complain.

  1. I'm tempted to go running along the sea at some point, but the beach area is unlit at night and running during the day is not going to happen. []
  2. currently showing only two movies, Green Lantern and No Strings Attached (sounds like a chick flick), so I think I'll pass. []