Carter Allen

A Year in Space

2014-05-31T00:00:00-07:00

This time last year, I didn’t have a clue what I was doing. I knew that I would be moving to Los Angeles to attend the USC Viterbi School of Engineering, and that was about it. My major was listed as Electrical Engineering, but that was only because I thought my application reflected best on my abilities with electronics. I spent the summer fretting, wondering how long it would take everyone to notice that I hadn’t any idea what to do.

A week after arriving at USC, I attended an “Involvement Fair” where various student groups were recruiting new members. Perhaps it was fate, or perhaps it was the enormous carbon fiber rocket that drew me to talk to the representatives from the USC Rocket Propulsion Laboratory (USCRPL). Whatever the reason, I signed up for their newsletter and added their first meeting to my calendar.

I also signed up for Introduction to Astronautical Engineering, the 101 course in USC’s one-of-a-kind Astronautical Engineering department. All introductory engineering courses are interchangeable at USC, so I thought that it couldn’t hurt to try something a little different. ASTE 101 is taught by the inimitable Doctor Daniel Erwin, who is also the department chair. He sold me on the major in roughly one class period, and continued to be my favorite professor for the entire semester.

The first Rocket Lab meeting was exciting, and I loved the atmosphere of the group. I made myself give it a shot, and after a few days of working in the lab, I was absolutely hooked. I had found my people, and my calling. I was going to be a part of the first undergraduate group to send a rocket to space. After a whirlwind month in the lab, I was with the group in the desolate Black Rock Desert, preparing to launch our first space-shot rocket, Traveler.

Traveler didn’t reach space, but the experience was amazing. The first thing I did after getting back to campus (after taking a shower, of course) was declare my major as Astronautical Engineering. I committed to space.

Fast-forward to March, and I had applied for an internship at the private space startup Blue Origin. After a harrowing phone interview conducted the hour before a midterm (while I had a bad cold, to boot), I was offered a summer job. I’ll be working on avionics when I start there this coming week. But before we all left for the summer, the Rocket Lab had one more project to finish.

Traveler II, a rebuilt version of the original Traveler space shot, had been in-progress since October. The build was slowed by manufacturing difficulties, financial woes, and the need to move our entire lab space. In the end, we left the lab at 9:30 PM on Saturday, May 17th – roughly 24 hours after our planned departure time. We set up the vehicle in Black Rock, this time with an avionics system that I had been working on non-stop with my unfailing compatriots Adam Rising and Ian Heidenberger for months on end. After delaying the launch by a day to triple-check the wiring of the recovery (parachute) system, Traveler II took to the skies midday on Monday.

The rocket exploded after only two seconds of flight, which was certainly a disappointment for everyone. But even in the face of such terrible news, the team was optimistic. I didn’t see a single tear shed among us, though anyone would have been forgiven for falling apart after so many sleepless nights. Instead of wallowing in failure, discussions immediately turned to our next flight, how to improve our processes, and how to work better as a team. I’m truly honored to be a part of such a fantastic group of people.

Now it’s been almost a year since I last wrote on this site, and I thought it was about time for an update. It’s been a year of adventures, science, engineering, and space. And everyone has yet to notice that I still don’t have a clue what I’m doing.

The Poignant Purple Dot

2013-07-01T00:00:00-07:00

About a year ago, my older brother Austin moved out of our childhood home in Denver and headed to Los Angeles. At the last minute, we decided that I would drive out with him, at least as far as Las Vegas. My own classes were beginning soon in Denver, so I wouldn’t be able to go all the way to LA, but I would at least be able to spend a day and half of the two-day drive with him. I’m not exaggerating when I say the decision was last-minute: I decided to go with him about an hour before we left, and my packing consisted of throwing my iPad, a change of clothes, and a toothbrush into a small bag. Out the door we went, waving goodbye to our mother and our house. Though I would be returning less than two days later, we both knew that we were waving goodbye to the past 16 years of our life.

Pulling up Find My Friends, I saw a purple dot for each stage of my life. My father’s dot, centered at our destination in Los Angeles, represented the time I had spent in LA with him over the years since my parents' divorce. The purple dot of my best friend George, centered in Denver, represented my life growing up at home. And of course, the overlapping purple and blue dots of my brother and I as we made our way across the country represented the transition into a new stage, beyond what either of the other dots stood for.

The first day of driving was relaxed and fun. We re-listened to old podcasts, rocked out to music that neither of us would ever be caught dead listening to in public, and had long discussions about life, the universe, and everything. Well, everything with one exception: the topic of Austin leaving was subconsciously off-limits for both of us. We made it as far as Green River, UT on the first day and settled in to a cheap motel for the night. With no WiFi and no functioning television, we decided to watch an episode of The Newsroom through the HBO GO app on our iPhones. We each sat in our own bed, and whenever one of our phones would stop to buffer, we’d call out to the other to pause. Going back-and-forth like that, we eventually finished the hour-long TV show after about two hours. I can’t remember anything about the show itself, but I can still remember the night itself. We finally went to sleep late at night, with several alarms set to begin the morning drive.

The next day was more of the same, at least for the first half. However, as we approached my final destination of Las Vegas, the conversation became more subdued. Long silences were far more common. We arrived in the city far too early for my flight, and after a brief visit to an expensive roller coaster, we decided to sit in a Starbucks for a while. The combination of power outlets, free WiFi, and air conditioning was extremely appealing. At this point, however, we had almost completely stopped talking. Both of us withdrew to our Apple devices for distraction, with only the occasional comment floating from one of us to the other. After we had burned through about an hour, it was time for us to leave the coffee shop for the airport.

We crammed ourselves back into the tightly-packed car, and headed toward the Las Vegas airport. The car pulled up to a nearly-deserted section of the parking area, and Austin and I both climbed out. Me, with my bag sparsely filled with a day’s supplies, and him with nothing but a forced smile. We hugged. And then after exchanging no words that I can remember, I walked away. He re-entered the car and drove off. When his car disappeared from my vision, I pulled out my phone and watched his purple dot continue its western trek, leaving my blue dot sitting still in the airport.

I had never felt so alone.

I sat crying in the terminal for what seemed like hours before my plane left. When I arrived back home, the house was uncharacteristically quiet. The door to my brother’s bedroom was closed. The chair in my room that he typically occupied was empty. And once again, I sat down and cried. I cried for the end of my childhood. I cried for the separation from my confidant and my defender. I cried for Austin.

The next week, when he had found an apartment and moved in, I opened up Find My Friends once again. I tapped his dot, and created a new marker for his current location. I typed “Home” into the box, and confirmed my change. Then, looking at my list of friends, I saw that everyone was home. I realized that “home” really is just a label put on a location, and that despite my sadness, I would move on. My dot would change homes, as would my brother’s, my dad’s, and my best friend’s. But at the end of the day, when I open up the app and I see a collection of purple dots, sparsely strewn across the country in no particular pattern, all I have to do is look down at the list and see the labels. The dots move, but everybody’s home.

Made on a Mac

2011-10-16T00:00:00-07:00

I’ve written a lot in the past about the various systems that have powered this blog. It’s gotten to the point now where the most popular topic on this site seems to be the site itself. However, I’ve made a major change to how it all works, and I think that it is important enough this time to justify yet another meta-post.

To quickly recap, this site began life as a WordPress blog. A while ago, I followed a trend and migrated from WP to a “baked” blog system called Jekyll. Jekyll was never really perfect, so I was in a continuous fight against it, monkey-patching whatever I could find to get the thing to work the way I wanted. In addition to that, Jekyll is written in Ruby, a language which I have never really liked. I know the syntax and I can write basic programs, but its lack of structure gets to me. Because of this, hacking on Jekyll was never really a pleasant experience, as I was always left questioning how something had ever worked in the first place, instead of actually fixing whatever the latest problem was.

My never-ending quest for perfection in Jekyll led me to string it together with several other Ruby programs, none of which I had any control over. My simple blog system had massive dependencies, and it finally broke when I upgraded to OS X Lion. That was the final straw: it was time for something better.

The problem was, there wasn’t anything better. No static blogging engine was even close to what I wanted: minimal, fast, and written in a language that I knew and liked. I’m sure that most readers will be able to guess what happened next.

If you want something done right…

I sat down and spent the next couple of days writing my own static blogging engine. The result is an extremely fast and very opinionated app that serves me quite well. This site is generated via compiled Objective-C code, running in a native Mac app. The app has a simple UI, and requires absolutely zero command-line usage. Say hello to Tribo:

The app takes a specially organized directory of files and transforms them into a functional site. The result is completely static and can be served up by whatever HTTP server you’d like. Posts are written in Markdown and templates are written in HTML with {{mustaches}} The entire system is extremely fast and uses completely native, compiled code. No VMs, no scripting languages, not even any fork()ing. This is one of the reasons that Tribo is so damn fast, but the biggest reason for its speed is that the app uses some amazing third-party libraries to do the most intensive parts of the process.

On the shoulders of cheetahs

The obvious bottleneck in Tribo is Markdown processing. Although it is a hell of a lot simpler to parse than HTML, Markdown is in no way a trivial language, and writing my own full-fledged parser is really out of my skill set. After trying out and doing basic benchmarks on several native Markdown engines, I settled on Sundown. Sundown parses all of the Markdown content on GitHub, and if they trust it, then I trust it too. In my limited testing it was significantly faster than the other choices, namely Discount and PEG-Markdown. It also had the friendliest C API of all the libraries, which made parsing the contents of an NSString as Markdown trivial:

To process the template files for the site, I used GRMustache. There wasn’t really a lot of competition here considering it is the only Objective-C Mustache engine, but it worked well. If you haven’t ever used Mustache templates before, the Post template for this site is a great example (I’ve omitted the code for the comments section, but it’s irrelevant for the example):

What I meant by “opinionated”

Earlier I described Tribo as “very opinionated,” and this will become immediately apparent to anyone other than me that tries to use it. The app expects folders to be named very specifically, to contain files that are formatted perfectly, and most of all, the app expects to be used by someone that understands it. Realistically, this means that most people won’t want to touch the thing. However, my good friend George is going to be using it for the next revision of his site, and he has really been enjoying developing with Tribo. There are lots of features of the app that I haven’t described that make it a pleasure to use (for me, at least) but that doesn’t mean that it is everyone’s cup of tea. However, if you are an Objective-C developer, consider how nice it would be to know exactly how your blogging software works. I can tell you right now: it sure as hell beats Ruby.

Tribo is open-source and can be found here. You can see how files have to be laid out by taking a look at the source code for this website.

Primality Testing and Factorization in C

2012-01-10T00:00:00-08:00

A couple days ago, I set to work on what seemed like a fairly straightforward project: I wanted to build a reasonably fast factorization program in plain C. I didn’t need it to be able to factor massive numbers, I just wanted to create it as an exercise. This seemingly basic concept led me into the strange world of number theory, a land I had never been formally introduced to, and ultimately resulted in me gaining quite a bit of knowledge.

The concept of factorization is very simple: every positive integer can be broken down into a unique set of prime factors. This is known in number theory as the fundamental theorem of arithmetic. Actually performing factorization on even mid-sized numbers is surprisingly difficult, and this difficulty is the basis for much of modern cryptography (namely RSA.) If integer factorization were trivial, then many encryption standards would be equally trivial to break. My goal for this project was absolutely not to produce a revolutionary algorithm for factorization. All I wanted to do was see if I could implement some of the simpler algorithms myself, and more importantly, if I could actually understand what those algorithms were doing.

Step 1: Primality Testing

Although it may seem to only be tangentially related, the first step that I took in my quest for a factorization program was to write a straightforward function to test the primality of any integer. Testing primality isn’t nearly as easy as you might think, which is why a faster implementation would cache the results of all primality tests for later use.

Before we start writing code, let’s think about how to approach the problem. We are given a positive integer, and we need to know if has any factors other than 1 and itself. The almost universal first idea is to run through every number from 2 to n (where n is the number we are testing), and divide n by each number. If there is a remainder, move on to the next number. If it divides evenly, then n is not prime. The following function implements this most-basic solution:

For future comparison, I tested the number [2147483647][] with this function. It took 26.739 seconds to conclude that the number is, in fact, prime. I’ll refer to this solution as the brute-force method. It tests every possible factor, yes, but it also tests many impossible factors. For example, let’s take 17. We start at 2, and find that 17 divided by 2 leaves a remainder, so we move on to 3. Again, we find a remainder, and move on to 4. However, think for a moment: are there any numbers that are divisible by 4 but not by 2? No! 4 is a multiple of 2, meaning that if a given integer n isn’t divisible by 2, it isn’t divisible by any multiple of 2 either.

The obvious optimization here is to remove all multiples of 2, or in other words, only test odd numbers. Testing only odd numbers requires only a bit of additional code:

This might look a bit confusing at first, but it’s actually not too bad. All we’re doing is looping through half as many numbers as we did before, and then testing each value for i by doubling it and adding 1. In practice, this means that the function only tests odd numbers (because we start at 2; if we started the loop at 1, it would only test even numbers.) Predictably, this function performs significantly better when tested with the same number as before: it took 14.079 seconds to reach the same conclusion as the original brute-force method.

There are a few directions we can go from here. The idea of eliminating multiples of 2 can be generalized to eliminate even more numbers from testing (which is a great method of simply compiling a list of prime numbers; we’ll revisit this later), but this makes the code increasingly complex for smaller gains in performance. The bigger improvement we can make is by narrowing the range of numbers being tested.

Currently, the best function we have tests all odd numbers between 2 and n. We can make this range dramatically smaller by applying a bit of logic. All of the numbers we are going through in our loop are actually half of a pair of factors. Going back to the number 17, when we check the number 3, it is part of a pair. The other part of the pair is (17/3), or about 5.67. There’s an interesting rule that can be applied here: given a number n with factors c and d, either c or d is greater than the square root of n, and the other factor is less than the square root of n. You can research and test this rule, but trust me, it does hold true. We can use this rule to limit the range of our search to only the numbers less than the square root of n. Numbers above the square root have, in essence, already been tested, since we’ve already tested their corresponding factors below the square root. Here is a function that applies this optimization to our previous attempt:

It may not look like much, but guess what? This bad boy concludes that the same number we tested earlier is prime in 0.000640 seconds. That, my friends, is a significant improvement. To understand how we achieved this huge leap in performance, we need only consider how many numbers each algorithm needed to test. The original algorithm tested n - 2 numbers (remember, we excluded 1 and n itself. In the case of our test number, that means testing 2147483645 values. The second algorithm tested (n - 2)/2 numbers, meaning it had to test 1073741822 numbers. The final algorithm tests sqrt(n) - 2 values, giving it 46340 numbers to test.

There are many more optimizations that can made to this primality test. One important observation to make about this algorithm is that it lends itself to parallelization. Split up the range into chunks, and test each chunk simultaneously. If a factor is found in any chunk, stop the whole process and conclude that the number is not prime. If every chunk is completely searched and no factors are found, then congratulations, you’ve found a prime! I wrote a parallel implementation of the previous algorithm using Grand Central Dispatch, Apple’s block-based concurrency system. The function also includes a few other optimizations, which I’ll leave unexplained as an exercise to the reader.

The speed improvement that this algorithm offers is highly dependent on your chosen number of chunks, and whether the number is actually prime. For the rest of this article, I’ll be using the non-concurrent version of the algorithm, as it is fairly efficient while remaining simple.

Step 2: Factorization

Before I explain various factorization functions, I’d like to quickly go over why none of them have return values. The ideal factorization function would return an array of the prime factors of the number you gave it. However, because I am dealing with plain C, arrays must be allocated in fixed sizes. I would need to know ahead of time how many factors a number has, and that’s mathematically impossible. Because this was done as an exercise, I decided to simply have the factorization functions print factors as they found them. If you were to use these functions in a more realistic environment, you would probably have access to a pre-built mutable array system. A linked list would also solve this problem, but I opted to stick with the simpler solution for the sake of education.

The simplest way of factorization is also the slowest, and bears a resemblance to the brute-force method of primality checking. From 2 to n, check each if each number can divide evenly into n. If it can, check if it is prime. If the number is prime, then you’ve found one of the prime factors. Add it to your list and move on. If it isn’t prime, now try factoring the factor (recursively.) Eventually you’ll be left with all the prime factors. This process is known as trial division, and is trivial to implement in any language.

Trial division can be improved from its most basic form through the use of a list of known prime numbers, ranging from 2 to the square root of n. This removes the need for constant primality testing, and also drastically reduces the total number of numbers to test. The trick is efficiently generating the necessary list of primes. The simplest method of calculating a list of prime numbers, known as the Sieve of Eratosthenes is actually fairly efficient. For that reason, we’ll be using it as our algorithm of choice for calculating prime numbers.

The concept of a sieve is fairly simple. Imagine a calendar, with days numbered 1 through 31. Immediately cross off 1, as we always do when dealing with primes. We know that 2 is a prime number, so don’t cross it off. Now think back to our original optimization of the brute-force primality test: once you test a given factor, you can remove its multiples from the list of numbers to test. We can apply that concept here too, because any number that is a multiple of another number (other than 1, of course) is not prime. This means that we can start by crossing off every multiple of 2. After that, we move up to 3. 3 wasn’t crossed off before, meaning it is prime. The rule is that if a number is not crossed off when you reach it, that number is prime. Whenever a prime number is reached, you then cross off all the multiples of that number that lie ahead. Keep going like this until you reach the end of the calendar, and then look back. You now have a list of prime numbers.

The problem with implementing this in a computer program is that it requires an array as long as the square root of n, which can get to be pretty big if you’re dealing with large numbers. However, this is for the purposes of education, so that concern isn’t really necessary. If you are playing with the code in this article and the program runs out of memory, then you’re probably testing with a number that is too large for your computer to handle.

The following is an implementation of the trial division method which employs a basic prime number sieve:

The implementation is composed of 3 different functions, in addition to the primality test function from before. The main factorize() function takes a number n and allocates the necessary memory for a sieve to hold numbers from 2 to the square root of n. It then passes this memory to the fillPrimeSieve() function, which uses the algorithm I described before to mark all the non-prime numbers in the sieve with a 1, leaving prime numbers denoted as 0’s. Both n and the sieve are then passed to the factorizeWithTrialDivisionAndSieve() function, which factors n by testing each prime from the sieve. When it finds a prime factor, it divides n by the prime to find the other component factor. If this other factor is prime, then the last factor has been found and the function exits. If the other factor is not prime, then the function calls itself recursively to factor this new number. This recursion is the reason that these functions are split apart: if the algorithm was contained in one function, then the sieve would be re-filled every time the function recursed into itself, which would be a major performance hit.

This function is quite useful for even mid-sized numbers, but it begins to show its weaknesses when given a number where even the square root is large enough to cause memory issues. There are many more efficient algorithms that can be used, and this algorithm could be optimized further by caching a list of primes, as well as careful parallelization. The three most common other algorithms are Fermat’s factorization method, the quadratic sieve, and the general number field sieve. Unfortunately, the last two algorithms are beyond my math and programming capabilities, and Fermat’s method is not much more efficient than trial division.

I hope you’ve enjoyed this brief introduction into the world of primality testing and factorization, and that the code samples I’ve provided are useful, if only for education. You can view all of the code samples together in this Gist.

[2147483647]: http://en.wikipedia.org/wiki/2147483647 “Eighth Mersenne Prime”

The Great USB Key Conspiracy

2013-06-04T00:00:00-07:00

After being admitted to the University of Southern California, I began receiving quite a bit of mail from their various departments. The Viterbi School of Engineering, where I will be attending school next year, was the first to send me a USB key, which I promptly ignored. Assuming it was just a flash drive full of documents, I cast it aside like I had with almost every other piece of cardinal-and-gold paper that had arrived in my mailbox. Little did I know that the key was just the beginning of a vast conspiracy. What followed was the unraveling of a direct-mail tale of corruption and deceit, a story that exposed the seedy underbelly of USB-based correspondence.

It wasn’t until I received the second USB key, this time from the Student Health Center, that I became curious as to why they were sending USB keys instead of traditional correspondence. I plugged the key into my computer, and waited. After a momentary delay, I heard three “thunks” from my speakers (the quintessential “you can’t do that!” Macintosh sound), before my dock popped up, the Safari icon dimmed, Safari came to the front, the URL for the health services website was entered into the address bar one letter at a time, and the site was loaded.

While most people would simply cock their head momentarily before smiling and starting to use the website, my immediate reaction was a potent mixture of terror and morbid curiosity. Considering the lack of U3 and autorun.inf support on OS X (which is a Good Thing™), I couldn’t understand how the little USB stick was capable of controlling my computer in such a way.

I jumped over to Terminal, where I ran:

sudo fs_usage | grep "/dev"

That command quickly showed me that the mysterious USB key wasn’t being mounted as a volume at all. How, then, could it be manipulating my computer? I considered the facts. There is no way to run arbitrary code, without user intervention, from a USB device on OS X. Lacking such a vector, how would I go about opening a URL on an unknown computer?

The answer was hidden in the way that the key had navigated to the URL. If the device was capable of executing code, it would simply trigger OS X’s native URL loading system, which would open the webpage in the default browser without needing to manually switch apps and type the URL one character at a time. And that was the key. One character at a time.

The USB key was masquerading as a keyboard.

Once I knew what it was doing, the specifics became trivial. Control-Fn-F3 opens the dock with keyboard navigation enabled, entering “Safari” selects the browser, Command-L selects the address bar, and from there all that needs to be done is enter the URL.

Knowing how the USB key was performing its magic only led me to bigger questions. Who had designed it? Was the security community aware of the possibility of similar devices being weaponized? And perhaps most importantly, why would two different departments at USC choose to send these little devils instead of just writing the damn URL on a postcard?

Not knowing what else to do, I took apart the key. Prying open the metal casing was easy, albeit destructive, and inside was a very simple circuit board. Unfortunately, the interesting part of the board – the integrated circuit in the center – was encased in a hard epoxy shell. The practice of covering IC’s with epoxy is common in mass-production of inexpensive electronics, and meant that I couldn’t pull any part numbers off of the board. So that was a dead end.

At a loss, I turned to Google. To my surprise (given the conspiratorial nature of the entire situation), I found the answer rather quickly. The company, which will remain nameless for my own protection, sold products that clearly matched the key on my desk. Sadly, I found the website to be unsurprisingly devoid of details. With no links to buy keys (for comparison, of course), I was once again at a dead end. That is, until I clicked over to the company’s LinkedIn page. In what may be the most legitimate use of LinkedIn to date, I found my suspect. The fact that he was the founder of the company wasn’t what interested me. No, the important piece came under the “Education” section: he attended the University of Southern California.

That was when I realized that I had just blown the case wide open. USC’s use of the USB keys was nothing more than a carefully concealed conspiracy to funnel untold millions into the pockets of its alumni. With all of this information in hand, I decided to test out my theory on my father. After a lot of handwaving and a heavy dose of hyperbole, I sat back in my chair and waited for his response. After a beat, he shrugged, and replied:

“That’s capitalism.”