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

Share this article:Share on FacebookShare on Google+Tweet about this on TwitterShare on RedditShare on StumbleUponEmail this to someone

Infinitely Aged Christmas Pudding

Astronaut reaching

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
  • 4 oz bread crumbs
  • 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.
Share this article:Share on FacebookShare on Google+Tweet about this on TwitterShare on RedditShare on StumbleUponEmail this to someone

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

Share this article:Share on FacebookShare on Google+Tweet about this on TwitterShare on RedditShare on StumbleUponEmail this to someone

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

Share this article:Share on FacebookShare on Google+Tweet about this on TwitterShare on RedditShare on StumbleUponEmail this to someone

How to pronounce hexadecimal

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.

Share this article:Share on FacebookShare on Google+Tweet about this on TwitterShare on RedditShare on StumbleUponEmail this to someone

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.

Share this article:Share on FacebookShare on Google+Tweet about this on TwitterShare on RedditShare on StumbleUponEmail this to someone

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.

Share this article:Share on FacebookShare on Google+Tweet about this on TwitterShare on RedditShare on StumbleUponEmail this to someone

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.

skynet

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.

Satellite altitudeWhat.

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

Share this article:Share on FacebookShare on Google+Tweet about this on TwitterShare on RedditShare on StumbleUponEmail this to someone

On Elon Musk’s Ridiculously Huge Satellite Fleet

On Friday, Elon Musk announced SpaceX’s intent to launch a fleet of over 4000 communications satellites, whose primary purpose is to provide a low-latency broadband internet to us Earthlings:

He’s drumming up interest among potential hires for SpaceX’s new satellite branch in Seattle for, fittingly, building satellites.

This is an interesting move. 4000 is a huge fleet— Musk says in the video that this is more than double the number of currently active satellites, but from this database, it looks to be actually more than triple that number.

Why?

It’s faster

Currently, to travel a long distance, a packet of data must be routed through thousands of miles of fiber optic cable. Because the fiber is made of glass and is refractive, the speed of light in the cable is about 60% of the speed of light in a vacuum— so this limits how quickly data can go from one place to another on Earth.

Musk plans to route data directly from satellite to satellite through the vacuum of space, bypassing the speed limit of fiber.

Another factor is the number of hops: as a packet makes its way around the internet, it makes pit stops at routing stations, which might hold the data in memory as it waits in line to be sent to the next stop. This takes time, and may happen several hundred times for a long distance communication. This can add up to a significant fraction of a second.

Musk plans to route long distance packets in just a few hops, reducing the delay between endpoints even further. This is possible because each satellite will be in view of many others— it’s possible they’ll transmit data by pointing lasers at each other. For data, it’s the difference between taking the backroads and taking the freeway.

Notably, the proposed fleet would be orbiting at around 1100 km; far lower than the altitude of current high speed internet satellites, which hang out in geostationary orbit. Current satellites 22,000 miles away, which demands a minimum round-trip signal time of about 1/4 second. In contrast, Musk’s satellites will orbit just 3 milliseconds from the surface.

Money

It seems there is opportunity here to enter a relatively sparse niche. Long distance communication is dominated by fiber, which is expensive to lay. Satellites are expensive too, but in a matter of months that cost will drop enormously— perhaps by an order of magnitude— when SpaceX succeeds in landing its reusable first stage rocket. Elon is in the unique position of knowing exactly how cheap space launches are about to become, and also has the ability to fully reap the benefits of cheap launches without any of the markup that he’ll be charging his competitors.

Musk says he intends to capture about 10% of consumer traffic, and 50% of the “long distance” traffic. This means the network will be focused on backhaul, routing large batches of data between endpoints for telcos and ISPs. It seems he hopes to attract backhaul customers by offering significantly (“order of magnitude”) improved latency over current capability.

10% of consumer traffic is a lot— There are about 2.5 billion subscribers on the internet (that will surely grow), and Musk is therefore hoping for about 250 million SpaceX internet users. That’s incredibly ambitious, although a comparatively small amount of infrastructure (as opposed to laying fiber for the same consumer base) will provide him easy access to the entire globe. If he succeeds, and we suppose a consumer cost of, say, a conservative $10 a month, that’s a total of 2.5 billion dollars of revenue per month. This would pay off a 15 billion dollar satellite network (Musk’s cost estimate) in just half a year. 10% of all internet subscriber traffic is pretty ludicrous, but if he’s overestimating by a factor of 10, it’s still looks to be easy money. This isn’t counting the backhaul traffic he intends to capture (whose revenue I don’t know how to estimate).

And money is the goal. Musk primarily wants something that will generate cash for his a future Mars colony venture; he seems to believe this will be a cash cow.

Will I get satellite internet on my phone anywhere on Earth?

Probably not; the radio frequencies SpaceX is likely to get their hands on don’t penetrate buildings. It’s more likely that homes and businesses will need to pay a few hundred dollars for a dish installation on the exterior of the building.

This is maybe something for Musk to worry about; it’s quite possible that in developed countries individual subscribers will soon stop paying for high speed internet at home, and start using their phones, almost in the same way that landlines were outmoded some years ago.

Overall, it appears that Musk is vying to become a major player in the telecom industry. New competitors are rare here, though he did manage to bust into the immensely expensive and entrenched space industry. We’ll soon see how he performs.

Share this article:Share on FacebookShare on Google+Tweet about this on TwitterShare on RedditShare on StumbleUponEmail this to someone