Some interesting napkin math about SpaceX’s passenger ICBM

You might have heard that SpaceX is working on a giant rocket.

No, not that one that launched the car— that’s the Falcon Heavy.

They’re working on another one that’s significantly bigger, called the BFR, for Big Fuckin’ “Falcon” Rocket. It can carry more than twice as much payload as the Heavy.

It’s an ambitious project. It will be fully reusable, which will drastically cheapen the cost of putting objects and people into space (even beyond what SpaceX has achieved so far). Elon Musk is building it because he wants to send people to Mars, but the rocket has the potential to do a lot of other stuff too: According to Musk, not only will it will be able to deliver a payload “anywhere in the solar system”, it will also be able to take people from place to place on Earth.

Here’s the video he demoed last fall:

SpaceX’s vision is to offer rides to the other side of the planet in around 30 minutes. The rocket would take off from somewhere near a city, launch at sub-orbital speed into space, coast for a few tens of minutes, re-enter the atmosphere, fire its rockets and land at the destination city. Essentially, it would be an ICBM for passengers.

Elon Musk has claimed the an Earth-to-Earth BFR ticket should be around the same price as a commercial economy flight ticket, offering a faster, competitive alternative to air travel.

This boggled my mind, so I decided to do a whole heap of napkin math to answer the question: How crazy is this? Is it even crazy at all?

1. Is Elon Musk’s advertised price realistic?

For reference, we’ll peg the price of an economy international air travel ticket at around $1200 USD. Is it possible to bring the cost of a ride on an honest-to-god spaceship down to that level? Let’s figure it out. We’ll start by looking at Musk’s estimate for a ticket to ride the BFR to Mars, which is$500,000, and scale it for the different logistics of going to Earth instead. (He’s variously used estimates of a $200k or$500k Mars ticket at different times; it’s unclear where the price on latest scaled-back version of the BFR would fall). It’s not a given that this price estimate can be taken at face value, though we’ll see later that it is plausibly realistic. Since Musk’s estimate is the only cost figure from SpaceX about the BFR at this point, it’s the one I’ll use for this article.

A Mars trip is a multi-month journey, so in order to offer everyone living quarters, entertainment, amenities, and cargo space to carry equipment for living on Mars, the spaceship tops out at a maximum capacity of around 100 people. But for a 30 minute intercity trip, none of those amenities will be necessary, and that means we can fit a lot more people on board. The interior volume of the new BFR spaceship is comparable to an Airbus A380 (a little bigger, according to Musk), and the latter accommodates up to 800 people (though most configurations are around 500). So realistically, the intercity BFR could carry 5 to 10 times as many people as the Mars ship. We can therefore conservatively divide the price by 5, bringing us to $100,000 per ticket. The Mars journey is much longer, too. So much longer, in fact, that SpaceX will have to launch five more BFRs into low Earth orbit just to fuel up the passenger vehicle before it departs for interplanetary space. So to go to Mars, those 100 passengers are actually paying for at least 6 complete BFR launches from the surface of the Earth. The Earth-to-Earth trips won’t need those in-orbit refuel missions, so right away we can divide the price by another factor of 6. That brings the price down to about$16,000.

We also have to discount the cost of the fuel that those extra flights are carrying as cargo to the passenger vehicle (which would serve the purpose of fueling the journey toward Mars). We don’t need it, so after discarding the cost of the refuel flights themselves, we can expect to pay about half as much for fuel on an intercity trip. (One way to conclude this would be to observe that a Mars spaceship couldn’t carry more than another single full tank of fuel, after arriving fully empty in LEO). In aircraft, fuel is about 20% of the operational cost. If we reduce 20% of the cost by 50%, that’s only a 10% savings— so sadly we don’t get to knock off any more zeroes on fuel.

As an aside, currently rocket fuel makes up less than 1% of the operational cost of a launch— but that’s only because the rest of the money is spent by discarding the rocket! After rockets are fully reusable, the non-fuel costs could go way down. This is why it makes more sense to look to aviation for operational fuel costs than to “modern” rocketry.

Perhaps the biggest factor in ticket price is reusability, or the number of flights the rocket can make. An intercity rocket could do many, many more launches than an interplanetary one: The former could launch every day; perhaps multiple times per day, while the latter could realistically make only one round trip every 26 months, at every Hohman transfer window. In 10 years of life, that means a Mars ship could run only 5 flights, while an Earth-to-Earth rocket could run about 3650 flights in the same time period (at once a day)— another 730x improvement.

At this point, we probably can’t simply divide the ticket price by 730 and dust our hands. Firstly, the ability to fly a rocket 3650 times without major refurbishment hasn’t been proven yet. SpaceX’s latest, most-reusable incarnation of the Falcon 9— the Block 5— is expected to fly only 10 times before overhaul. This is only a factor of 2 improvement over the schedule-constrained limitations of a Mars route. Airplanes, by contrast, can service about 60,000 flights before reaching the end of their life.

SpaceX would have to improve the rocket’s durability by two orders of magnitude to reach our estimate for a “modest spaceliner lifetime” of one flight a day for ten years. Right now, the primary limitation on rocket lifespan is heat shielding, which must endure temperatures of around 1600°C (3000°F). Few materials can survive this for very long, which means heat shielding burns away or becomes ruined after only a few uses. The BFR will likely need to use as-yet uninvented technology to avoid completely rebuilding the heat shield every 10 trips or so, and SpaceX might have to look at new solutions like liquid cooling.

There is a second reason why we can’t simply divide the price by reusability: Given that the Mars ship is only ever going carry 500 passengers in its entire life, buying a ticket to Mars is essentially like going in on purchasing an interplanetary spaceship with 499 other people: it’s going to be expensive. But getting a ride on a (durable) intercity rocket is like buying it with 2 million other people, and then paying for ground operations, fuel, staffing, maintenance, and other overhead for every flight. Suddenly the vehicle cost is unimportant and the operations costs are the ones that matter.

To precisely estimate the cost reduction, we’d have to know not just the reusability, but also what fraction of the ticket will go to flight and ground operations, and what fraction goes to vehicle cost. This is another thing for which good figures are scarce, so it is probably best to amortize the vehicle cost and look at what we have left over to work with. We’ll guess that the rocket itself costs as much as an Airbus A380 ($450 million), or three times the cost of a Falcon Heavy launch in expendable mode (also$450 million, with “three” being the ratio of the BFR’s mass to the Falcon Heavy’s).

If we allow that the BFR improves reusability by a factor of 10 over the Falcon 9 block 5 (resulting in 100 flights per vehicle), then about $9000 per ticket needs to be spent amortizing the initial vehicle cost— which is not enough to be competitive with air travel. However, if SpaceX makes it all the way to our hopeful 3650 flight cycles per vehicle, then this goes down to$250/ticket. Compare to the vehicle cost portion of an airline ticket, which is about $11. This seems like a big problem (still a factor of 20 too high), it’s not actually a big deal: Once the vehicle cost approaches$100 per ticket, the operations costs dominate the price. This means that a space ticket would cost about $200 more than an airline ticket, rather than 20 times more, if we assume that operations costs are about the same. For a$1200 international ticket, that’s probably OK. And that makes sense, because in the long term, we are basically running an airline, but with a much faster, differently-shaped aircraft.

So could Elon’s claim about the price of intercity rocket travel be legitimate? Yes, but only if SpaceX adds at least two more zeros to the number of flights a rocket can make.

2. Can it be made safe?

The importance of this question— and the difficulty of answering it positively— can’t be overstated.

Airplanes are extremely safe. There are around 36 million flights per year (that’s 100,000 per day), carrying over 3.5 billion passengers. On average, there are fewer than 1000 air-accident related deaths per year, worldwide. For any given passenger, that’s less than a 1 in a million chance of death per flight, and it’s improving— Even as passenger miles are soaring, air accident deaths are decreasing every year. The safety factor is great enough that (despite the common fear of flying) driving to the airport is more dangerous than stepping on the plane. Other things that are more dangerous than traveling in a commercial plane include drinking two glasses of wine, riding ten miles on a bike, or living for two days in New York in 1980. In fact, for longer flights, you are more likely to die from the extra cosmic radiation at high altitude than from an air accident on the same flight!

In short, buying a plane ticket effectively carries no risk to your life and limb. When you step on the plane, you can be virtually certain that you will step off again unharmed.

Manned rockets, on the other hand, have (generously) a 1% rate of failure. Now, under a certain light, that might be seen as impressively safe for “trying to ride an explosion into space”, but it’s a problem for commercial adoption. If SpaceX were to launch an Earth-to-Earth air-spaceline, with (very conservatively) one launch per day carrying 500 passengers per launch, at current rates there would be three Tenerife-scale disasters(1)the worst disaster in aviation history, by loss of life every year. This makes rocketry about 105 times more dangerous than aviation, and it’s clearly unacceptable.

So what does SpaceX have to do to make passenger rocket flights acceptably safe?

Why do rockets blow up?

On the face of things, a rocket is basically a giant pressurized tin can full of flammable liquid balancing on top of a giant explosion— so there’s one very obvious way that things can go wrong.

If we look more closely, there are millions of moving parts and sensors that keep that explosion at exactly the right amount explodey-ness, and the rocket balanced on top of it at exactly the right angle— so there are a million less-obvious ways that things can go wrong.

I took a look at an inventory of rocket failures since 2000 and tried to break them into major categories by cause. They roughly boil down to three major and three minor ones:

Guidance and control

Guidance, navigation, and control (“GNC”, in industry-lingo) is, in short, the computer brains of the rocket. These are the algorithms that figure out where the rocket is and how it’s moving, and decide where to steer it, which valves to open, when to throttle up and down the engines, when to (if necessary) self-destruct, and so on.

This process can go wrong if sensors send the wrong data, or if the computer misinterprets them, or if the software crashes, or if the situation evolves into something that wasn’t tested, among other things.

A spectacular example of this is the Russian rocket which promptly flipped itself upside down and careened into the ground, because the rotation sensors were installed upside down:

About 1/3 of the rocket failures in the list above were because of GNC issues.

Loss of thrust

If for some reason the engines shut down too early or don’t fire with full force, the rocket doesn’t make it to orbit. Fully another 1/3 of the cataloged failures named a loss of thrust in the cause.

SpaceX has done a decent job of building redundancy into its designs. In fact, an early CRS mission suffered a single engine failure, but the primary mission still made it safely to orbit. Musk has stated that the BFR will have two redundant engines for its re-entry burn, so even if one completely fails, another can be started up and the spacecraft safely landed. (This is important because the re-entry burn is what stops the rocket from crashing into the ocean at mach 22).

Redundancy is one way to reduce the risk of loss of thrust, but the situation will still have to improve significantly for a space-based “airline” which might eventually serve tens to hundreds of thousands of launches per year. At the current reliability rate for SpaceX’s Merlin engine (1 known failure among 9 engines × 56 flights), if SpaceX were running an airline with 50 routes and two flights per day, the likelihood of a two-engine failure happening at least once in a year would be around 12% (likely resulting in the total loss of the spacecraft and all its passengers).(2)If a given engine has a 0.2% chance of failing on any given launch, then the probability of both re-entry engines failing together is the square of this. There will be ~36,500 launches a year under our assumptions, we should expect 0.0022 of them to be dual engine failures. The probability that there will be no dual engine failures in a year is thus Poisson(k=0, lambda=0.0022 * 36,500), and the probability of at least one such failure is 1 minus that.

The above result is probably an underestimate, though, because it assumes that engine failures are independent events. In reality, the probability of an engine failing is higher if we know that some other engine has just failed— either because a common cause might affect both engines (like when there was not enough ignition fluid to start the retro-burn for the Falcon Heavy center core), or because one failure might directly cause others to fail (for example, by hurling shrapnel at them). The real risk, therefore, is likely higher than 12% per year under these assumptions.

Probably both significantly more redundancy (e.g., using the vacuum engines as backup) and better single-engine reliability will be needed.

Loss of thrust itself has a myriad of causes, not the least of which is…

“Plumbing”

Rockets are almost entirely pipes and tanks and pumps. While that might sound like the “easy part”, in fact things get slightly more difficult when the fluids you’re pumping around are variously at -350°F or +1500°F, both at well over 5,000 PSI:

Source: http://large.stanford.edu/courses/2011/ph240/nguyen1/docs/SSME_PRESENTATION.pdf

Valves love to freeze over and get stuck. Turbopumps love to seize. Pipe seals can burst or burn through and send searing hot rocket fuel all over the place. Pressure waves or turbulence can build up inside pipes and cause other parts to fail. Fast-moving fluids can cavitate and scour away even the hardest metals. Valves refuse to open for seemingly no good reason. Needless to say, when these things happen, you will not go to space today.

About 23% of the listed failures named something that might be called “plumbing” in the cause (with some overlap with the other issues).

Materials issues

Welds fail. Metal impurities weaken pressure tank walls. Rubber O-rings get unexpectedly stiff in cold morning temperatures. In short, the materials of the rocket don’t live up to standards, or behave in surprising ways in the extreme circumstances of being a rocket.

Materials issues have arguably been SpaceX’s biggest foe— both of their recent failures implicate material problems; the CRS-7 failure was due to an internal strut failing far below its design strength, and the Amos-6 launch pad failure was because of an unexpected interaction between supercooled oxygen and carbon fiber.

About 12% of the causes in the list were related to materials (though that might be more if we were to further follow the trail of the other failures).

Stage separation

As the rocket nears orbit, the orbiter and/or satellite must detach from the booster and continue on its journey. If that separation doesn’t happen correctly, the mission is basically over.

If the spacecraft uses pyrotechnic charges to separate, these could simply be duds and fail to ignite. Other things could go wrong, like a latch getting stuck, or the separation happening at the wrong time.

Elon has stated that SpaceX never uses pyrotechnic charges for stage separation, since the parts can’t be tested ahead of time on the ground. This eliminates one class of potential problem, but even then, SpaceX has had its brushes with this kind of failure: One of its earliest rocket launches partially failed due to an issue with stage separation, and the more recent Zuma mission also (apparently) failed on stage separation, though the latter wasn’t SpaceX’s fault— the stage separation hardware was designed and built by the client.

About 10% of the listed failures have something going wrong with stage separation.

One-off surprises

Human error— botched assembly, unexplained causes, or things which were too vague to categorize. Another ~12% of failures on the list fall here.

What does SpaceX have to contend with?

Loss of thrust, guidance and control, and stage separation issues have some hope of being mitigated with high redundancy and thorough testing/engineering. It would certainly not be easy, but it is plausible that these sorts of issues could be uncovered before actual flight by sufficiently diligent engineers.

Materials, “plumbing”, and “surprises” seem to me like more ominous problems. They lurk in the complexities between systems, in the gaps between disciplines, and in the interpersonal relationships of the builders and engineers. You don’t learn about them until you’ve built your entire rocket; you couldn’t anticipate them because they only showed up due to the specific way you put this one rocket together, or the materials that you chose, or the supplier that you’re working with, or the optimism of the company when you designed it. They are the unknown unknowns, and they can only be uncovered with experience.

SpaceX, as it is pushing further into the unknown, endures those risks perhaps more than any traditional rocket manufacturer. For example, they are experimenting with the use of supercooled oxygen and increased use of composite materials; relatively new innovations in rocketry. The Raptor engines on the BFR will be new (and not benefit from the years of flight-testing that have stabilized the Merlin), and are of a less common, more complicated variety.

These are all innovations that are necessary to move the industry into the future, and absolutely should be done. However, they are the enemy of consumer-level reliability. Many non-passenger flights will have to be made before the BFR could possibly be deemed safe for general transportation. Hopefully there is a way for SpaceX to make enough money building BFRs and selling launches and internet until that time.

Safety outlook

SpaceX’s current launch reliability is about 96%, which is pretty standard in the industry for unmanned missions. (SpaceX, to their credit, are doing a lot more innovation than their competitors at that rate). While they are learning lessons from the failures of the past, there are still new lessons waiting to be learned in the territory they are pushing into. The innovation is not going to let up for the development of BFR— in fact, it is likely to increase.

About 4 or 5 zeroes need to be knocked off the probability of failure in order for consumer travel to appear sane, and it’s not immediately clear yet how that could be done.

3. Noise

I’ve seen a lot of comments about the worry of sonic booms— this is a problem, but probably less than many people think, as the vehicle pretty much goes straight up and out of the atmosphere. While in transit over continents, there is no way for it to make a sonic boom.

What people do tend to underestimate is the just how loud a rocket launch is. The Saturn V and space shuttle launches were both about 205dB— the BFR, which is larger than both, will certainly not be quieter.

205dB, by the way, is over 3 million times louder than a commercial jet flying 100 feet over your head— something I can’t even wrap my head around. Supposedly this level of sound is enough to melt concrete near the launch pad.

To fall under the FAA’s residential aircraft noise limit of 65dB, how far away would the BFR’s launch pad need to be from any development?

Sound attenuates with distance for two reasons: One, by the inverse square law, which arises from the fact that its energy is divided over the surface of a sphere of ever-increasing size as the sound travels away from its source. This works out to about -6dB of attenuation with every doubling of distance from the source.

The second factor is dissipation. The sound, which is a vibration, has to physically shake the air it travels through, which the air resists due to its viscosity. Over long distances, this resistance converts some of the acoustic energy to heat, and reduces the volume of the sound as it propagates. For reasonable weather conditions, this can amount to about -0.002dB for every meter of travel at around 500Hz (a frequency at which the rocket is near its loudest).

We also need to convert sound power level to sound pressure level (which another handy calculator will do for us). This gives us the loudness of the rocket if it were a point source and we were 1 meter away from it— for our 205dB rocket, this works out to 194dB of sound pressure. (This step is necessary so we can compute how the loudness changes with distance).

From these three facts we can set up an equation to see how many meters of distance we need to reduce the sound level to 65dB:

$$6 \log_2{x} + 0.002 x = 194 – 65$$

The result is that the launch pad has to be a minimum of 13 miles from anything.

And that explains the boat ride in the video at the beginning of this article: The only reasonable place to put a commercial launch pad within reach of a populated area is off the coast.

Right off the bat, this limits Earth-to-Earth space travel to cities which are near large bodies of water. Thankfully, this covers a lot of them, but it does pretty thoroughly exclude major cities on the interiors of continents.

It also complicates logistics quite a bit. For one, it adds travel time for the passengers (a minimum of 20 minutes on a high-speed ferry in each direction), and second, it mandates the construction of an entire launch complex on a floating platform. While SpaceX does have solid experience landing spaceships at sea, this could potentially be hugely difficult and expensive, and could eat into those formerly-appealing ticket prices. Ground crew would also have to vacate the launch platform because of the areforementioned concrete-melting loudness, and that could further lengthen the wait time for passengers and diminish the time advantage over air travel. This is probably not an idea-killing problem, but it does make things harder.

What can we learn?

Overall, this is a pretty exciting idea. Hopping from continent to continent through space in a matter of minutes seems right out of the future, and it’s tantalizingly close.

Safety is a huge unanswered question, though. Rockets are still very dangerous (and so far SpaceX’s are no exception); and the path to fixing this is not clear, nor has a concrete plan been put forward. If there’s a single giant hole in the idea of consumer Earth-to-Earth rocket travel, “safety” is probably it.

SpaceX will likely need many flights and design iterations to learn about how rocket parts wear and fail after a large number of flight cycles. There is no data about this now, and SpaceX will be the first to learn it. It will certainly take many tries to get things right.

Space is hard. Here’s hoping they can figure it out!

Footnotes   [ + ]

 1 ↑ the worst disaster in aviation history, by loss of life 2 ↑ If a given engine has a 0.2% chance of failing on any given launch, then the probability of both re-entry engines failing together is the square of this. There will be ~36,500 launches a year under our assumptions, we should expect 0.0022 of them to be dual engine failures. The probability that there will be no dual engine failures in a year is thus Poisson(k=0, lambda=0.0022 * 36,500), and the probability of at least one such failure is 1 minus that.

What Bitcoin Shows Us About How Money Works

There seems to be some longstanding confusion about Bitcoin. Not about how it works; there are plenty of articles which explain that quite lucidly— it is confusion about what Bitcoin represents, and what its role could be. I regularly hear these ideas repeated in seriousness:

• Bitcoin could one day supplant ordinary currency
• The decentralized / algorithmic nature of Bitcoin makes it safer than “normal” currency
• Bitcoin is like gold, and gold is good for counting wealth, therefore Bitcoin is good for counting wealth.

I originally penned this article nearly two years ago (before setting it aside). At that time, it seemed like Bitcoin was a passing fad— I believed then, as I believe now, that Bitcoin’s merit (or lack thereof) doesn’t stem from its popularity (or lack thereof), though the mood around Bitcoin has since entirely reversed.

Bitcoin advocates back then would have dismissed Bitcoin’s slide in popularity as proof of its invalidity, though today they’d probably be just as likely to point to its popularity as evidence of its success. I want to cast aside whether Bitcoin is Hot Right Now, as well as questions about implementation details (like the size and existence of transaction fees, the scalability of the blockchain, or transaction delays), and ask whether the fundamental idea is sound. In particular, I think the assertions listed above reveal some really interesting things about the way money actually functions, and what kind of value Bitcoin actually offers. So let’s dive in.

How Bitcoin works

You don’t need to know a whole lot about Bitcoin to understand its basic premise: You have an artificially scarce resource, which in this case happens to be very large numbers with a special mathematical property. That property is what makes the numbers rare, and thus computationally time-intensive to find. As time progresses, the property is designed to become more and more stringent, so new Bitcoin numbers become increasingly difficult to create. The total number of bitcoins in circulation is fixed ahead of time by the algorithm, regardless of how many people are using Bitcoin; and eventually no more bitcoins will be found. Bitcoins cannot be faked, because anyone can verify whether the mathematical property actually holds or not.

Ownership of bitcoins (or parts of them) can be transferred easily, because a large network of computers keeps track of who gave what to whom. There are more technical details which ensure the security of the whole system, but they’re not important to this discussion. What is important is that it is commonly said that this scarcity is what gives Bitcoin its value. And there are some problems with that.

Is Bitcoin like gold?

People often say Bitcoin is like gold and highlight the fact that, like gold, it’s valuable because it’s scarce, and because other people believe it’s valuable.

12 trail runs under 10 miles in SF and the East Bay

I can’t overemphasize the rewards of starting a running club. About a year ago, I started one nearly by accident— a routine of solo running morphed into a weekly social event. Every Saturday or Sunday five or six of us gather in the mid morning, run five to ten miles, and then have brunch together afterwards. The way I see it, this is a quadruple refill for the soul; a combination of four things that have immense positive impact on your mood:

• You’re getting exercise
• You’re being social
• You’re outside getting sunshine and nature
• You’re accomplishing something

The delicious food (and, frequently, drinks) at the end of it don’t hurt either.

With that plug out of the way, I offer below a catalog of twelve routes we’ve found over the last year. Continue reading

Infinitely Aged Christmas Pudding

While somewhat difficult to make, this recipe for extra-long aged Christmas pudding is rich in flavor!

• 1 lb raisins, currants, chopped apples, prunes
• 1 oz candied peel
• 4 tbsp brandy
• 2 oz flour
• 1 oz chopped almonds
• 2 solar masses dark matter
• 1 3/4 Yottajoules of negative energy
• 1/8 Earth-mass of lead (or other heavy elements) for radiation shielding. If you can find a small moon, it may be best to hollow out the core.
• 1 Penrose drive-capable spacecraft
• Provisions for 6 trillion years of space travel
• 1 handgun loaded with two bullets
1. Stoke the oven with the dark matter, set it to “closed timelike curve”, then turn it on and allow it to preheat. If anything strange happens at this point, don’t worry about it. It’s fine.
2. Mix the fruits, peel, and other stuff into a bowl or whatever.
3. Once the oven is preheated, retreat to a safe distance of about 1.5 AU. Apply the negative energy.
4. Wait for the gamma radiation to die down, emerge from your shield-moon, and board the ship. Don’t forget your provisions and gun!
5. Boost toward the gaping black hole where your oven used to be.
6. Approach the ergosphere, taking care to maintain infinitesimal separation from the closed timelike curve. When you’re close enough, chuck the pudding into it. Be careful not to run into any of the infinite copies of yourself now orbiting nearby.
7. Draw your gun and fire on the copy of yourself in the orbit just below you. The copy in the orbit just above you should be doing the same.
8. Your infinity of guns and infinity of bullets should take care of the infinity of self-copies. With any luck, you’ll be the guy at the top. Good job!
9. Descend toward the event horizon, and nab the pudding on your way down. Check that it’s an eigenstate of the universal wavefunction, and that the fruit has firmed up well. Insert a toothpick; it should come out clean of any protons, which will have completely decayed after a literal eternity trapped in a repeating loop.
10. Pass through the singularity and emerge from the pre-heated oven with the pudding. Draw your gun again and fire on your past self, who will have just switched the oven on.
11. Serve and enjoy. There will be no need to ignite the pudding, as it will probably already be on fire from all the proton decay.

Second Order FizzBuzz

The FizzBuzz problem requires the construction of a well-known list of interleaved numbers and nonsense words. The list has been studied extensively, and recent work at CERN has constrained its utility to less than 10-16 of a mosquito’s left nut. In modern times, the task of its production is typically relegated to computer programs. It is an open question why some institutions continue to use FizzBuzz as a test of programming ability, given universal knowledge of the test and the wide availability of solutions on Google and StackOverflow.

Programs that solve FizzBuzz are typically constructed by hand in an ad-hoc manner, often by inexperienced computer scientists, and entail a hazard of boredom-induced mortality. Below is presented an algorithmic solution to the second-order problem of generating such programs. In general, we define a class of nth-order FizzBuzz problems which require the production of a program which solves the (n-1)th-order FizzBuzz problem.

We use a variation on the stacksort algorithm due to Munroe (2013) and first implemented by Koberger (2013), which mimics a technique commonly employed in the wild. Here, the Continue reading

How a Kalman filter works, in pictures

I have to tell you about the Kalman filter, because what it does is pretty damn amazing.

Surprisingly few software engineers and scientists seem to know about it, and that makes me sad because it is such a general and powerful tool for combining information in the presence of uncertainty. At times its ability to extract accurate information seems almost magical— and if it sounds like I’m talking this up too much, then take a look at this previously posted video where I demonstrate a Kalman filter figuring out the orientation of a free-floating body by looking at its velocity. Totally neat!

What is it?

You can use a Kalman filter in any place where you have uncertain information about some dynamic system, and you can make an educated guess about what the system is going to do next. Even if messy reality comes along and interferes with the clean motion you guessed about, the Kalman filter will often do a very good job of figuring out what actually happened. And it can take advantage of correlations between crazy phenomena that you maybe wouldn’t have thought to exploit!

Kalman filters are ideal for systems which are continuously changing. They have the Continue reading

This bit from HBO’s Silicon Valley cracked me up:

Some kid is pitching his revolutionary startup idea to entrepreneur Elrich Bachman:

Kid: Here it is: Bit… soup. It’s like alphabet soup, BUT… it’s ones and zeros instead of letters.
Bachman: {silence}
Kid: ‘Cause it’s binary? You know, binary’s just ones and zeroes.
Bachman: Yeah, I know what binary is. Jesus Christ, I memorized the hexadecimal times tables when I was fourteen writing machine code. Okay? Ask me what nine times F is. It’s fleventy-five. I don’t need you to tell me what binary is.

We infer that “fleventy-five” is a hexadecimal number, commonly used in coding; presumably it’s 0xF5 (which is not 0x9 times 0xF, as it happens). But instead of saying “eff-five” for the byte 0xF5, Bachman has come up with some kind of novel system for the English-ification of hex digits.

He’s on to something. We have ordinary English words for decimal numbers, with names based on the digits and their place-value. “Seventy” is the word for two-digit chunks starting with the digit seven, for example. It might appear in the number “seventy-three”, or “five hundred seventy-one thousand”; both numbers with a 7 digit in an appropriate place. “Fleventy”, then, would be the number for two-digit chunks starting with F.

Hex only adds more kinds of digits (the symbols A through F). Could we follow Bachman’s lead and add more number-names for the extra digit symbols, and pronounce hex just like a decimal number? Could we have a system that attains the unwieldiness and syllable count of spoken English numbers, with all the respectable seriousness of saying the word “fleventy”?

I’m glad you asked. This has never been done before(1)probably, but fear not; here are the official new number-words for hexadecimal. You may start using them immediately:

Hex Place value  Word
0xA0 “Atta”
0xB0 “Bibbity”
0xC0 “City”
0xD0 “Dickety”
0xE0 “Ebbity”
0xF0 “Fleventy”

I think it would help to solidify this with some examples:

0xB3 “bibbity-three”
0xF5 “fleventy-five”
0xE4 “ebbity-four”
0xA7 “atta-seven”
0xC5 “city-five”
0xDB “dickety-bee”

Higher place values

But really, we must go further. What about numbers larger than a byte? We have the words “hundred” and “thousand” for decimal place values higher than ten, so why not something for hex place values higher than 0x10? Say, for multiples of 0x100?

For this, I propose “bitey”.

Resulting in:

0xDAF1 “dickety-A bitey fleventy-one”
0xE137 “ebbity-one bitey thirty-seven”
0xA0C9 “atta-bitey city-nine”
0xBBBB “bibbity-bee bitey bibbity-bee”

Naturally, we could make yet larger numbers by devising some names for larger place values, and combine them with intermediate values, in the same way that we compose decimal numbers like “thirty thousand” or “six hundred fifty one million”. As in English, place value names could be dropped if you’re feeling brief. We’ll also need hex-digit words for the “teens”.

Try it

I’ll leave you to explore the new naming system with this toy:

Say place values

How we’ve conversed about hex without a system like this is beyond me. You’re welcome.

Footnotes   [ + ]

 1 ↑ probably

Improving IMU attitude estimates with velocity data

This was last week’s project: Building a Kalman filter-based IMU.

IMUs (inertial measurement units) are clever little devices which try to estimate an object’s absolute orientation (and sometimes its position) by examining the forces on the object.

Hobby drone and computer input IMUs generally look at acceleration data (which informs where “down” is), compass data (which points toward north in 3D space), and rate gyro data (which tells the axis and speed of spin). “Down” and “north” in combination can give a pretty accurate constraint on orientation, but unfortunately if there are any lateral forces (wind; turning), they will get mixed in with “down” and distort the estimate. Kalman filters use matrix math to make good use of the gyro data to correct for this. However, a constantly-accelerating drone could still be fooled about where down is.

I’ve tried here to find out whether we can try to model the drone’s translation and take this into account when estimating the orientation. It turns out that even relatively poor and infrequent data about velocity can constrain acceleration— and thus “down”— quite well. The difference in the quality of the estimate is plainly visible.

This is all done by mathematically simulating a 3D moving object using ordinary dynamics and battering it with Gaussian random forces, and then predicting what data a noisy sensor might return. A predictor algorithm using a Kalman filter (which has no knowledge about the original state) attempts to recover the true state to the best of its ability. The truth is rendered white here, and the estimate in red.

At the end you can see the same algorithm running on actual sensors. The real thing doesn’t use GPS yet, but the prediction is still pretty decent! (There is not that much sustained acceleration to throw it off in this video).

I’ve done some other cool things with the code which perhaps I’ll write up in the future: Among them are a process noise model based on Gaussian random walks, and a nice extension of it to quaternions (which has dramatic impact on the quality of the estimate!) I also make use of automatic differentiation, which makes a linearized extended Kalman filter (EKF) particularly easy and robust to implement.

I spent about 15 minutes staring at this

What’s wrong with this code:

959  // we don't have a lot of entropy to work with here :\
960  RtPoint2 random_pt( deterministic_float( node->center_luminance, rnd1, (uint32_t)(1280498143 * rnd0) ),
961                      deterministic_float( data_pt->p,             rnd1, (uint32_t)(3584308421 * rnd0) ) );


The compiler error:

foo.cpp:961:100: error: expected ';' before ')' token


Where’s the mismatching paren?

Answer (highlight to view): The “:\” smiley face extends its comment to the next line. My syntax highlighter didn’t pick this up.

There’s probably an underhanded c competition entry in here.

EDIT: It’s occurred to me that, based on the compiler error message, the compiler would have preferred I make a winky smiley face instead.

Some physics about covering the Earth with Internet

Before I read that Elon Musk’s insanely-huge satellite fleet was to orbit at around 1100 kilometers above the Earth, I did some back-of-the-envelope math to figure out what satellite altitude would be necessary to carpet the planet with coverage. From this came an interesting little exercise in hypothetical logistics.

First, figuring the minimum altitude of a 4,000 station constellation: We can use a formula for the fraction of the Earth visible from a point:

$$A = \frac{1}{2} \left( 1 – \frac{R_e}{R_e + h} \right)$$

…where $$R_e$$ is the radius of Earth, $$h$$ is the altitude of the observer, and $$A$$ is a fraction of the Earth’s surface area. We can divide up the Earth into 4000 pieces and solve for h to know how high a satellite must be to see its portion of the Earth. When we do this, we get…

1.98 miles high.

What.

If you want to blanket the entire planet with internet coverage, and you’ve got 4000 things to do it with, those things only need to be floating about 2 miles off the ground!

Obviously nobody’s putting satellites in two-mile orbits. And we’d like some redundant coverage, so let’s demand that every point on Earth be covered by at least three stations and try again. What do we get? Continue reading