Archive for January, 2009

A Random Fact About Yourself

Monday, January 26th, 2009

I was tagged in a note on facebook, titled ‘25 random facts about myself’. You’re supposed to write “25 random things, facts, habits, or goals about you”, and tag 25 people, as well as the author of the note.  What does it mean to write a random fact about yourself?

Let’s figure out how many facts I could choose from. To simplify things,  let’s suppose my life occurs in one-second ‘frames’, and that my life is constant for the duration of that frame. In other words, lets assume time is divided into fixed-length quanta. As of the time of this posting, I am a little over 23.5 years old. That’s approximately 700 million seconds.   If a ’story’ about myself is a sequence of quanta, there are 2700 = 5.3 x 10210 possible stories about myself I could tell. For comparison, there are about calculated to be 1080 atoms in the universe. Even if I increase the size of the quantum to an hour, and limit stories to be descriptions of no more than 20 quanta, we have 7x1078 possible stories. That’s still a lot of stories.

Interestingly enough, if I used python’s random number generator,  the Mersenne Twister algorithm, I could actually implement a program to randomly select one of those stories, because it has a period of  219937-1. I thought about generating a truly random story, using a sweet bit of python code, but it probably wouldn’t be too interesting. It’d be really difficult to write anything about what I was doing at 4:00 on March 3, 1994, other than ‘I was 8 years old.’

Posted in Computer Science, Math, Observations | Comments

On GPS Navigation Unit Mapping Algorithms

Wednesday, January 21st, 2009

I currently live in Chapel Hill, North Carolina. I grew up, however,  in Cincinnati, Ohio and a couple of times a year I make the drive back there.  The best route takes me through West Virginia on I-77 to Charleston, but after that it’s really up in the air as to what the best way to get to Cincinnati is. I’ve experimented with a number of routes, and after consulting my GPS unit, Google Maps, and AAA, I think I’ve come up with the best possible route.  For those interested, it is OH-32 to US-35 to US-34 to I-64 to I-77 to I-74 to US-52 to US-421 to I-40 to NC-54.

Why was I able to find a better route than my GPS unit, into which probably went thousands of man-hours of labor? My guess is that the algorithm used by the GPS unit is not theoretically optimal.  The reason for this is simple: the country is  huge.   There are about 6 million miles of paved highway in the US. Assume we have 10 intersections for every paved mile of road (a very conservation assumption): then we have 60 million intersections. A graph with 60 million vertices has at least 60 million edges, but probably closer to 120 million if it’s connected at all (60 million edges would just be a straight line, which is obviously wrong.)  A very good shortest path algorithm running on a graph with E edges and V vertices takes runs in time roughly proportional to E * log V.  Plugging in 120 million for E and 60 million for V, we get a number of computational operations on the order of 2 billion.
I have a Garmin c340, but I couldn’t find data on its microprocessor. Therefore well assume we are using a Tom-Tom 720, which has a 400 Mhz microprocessor inside. This means it undergoes one clock tick approximately (1 MHz = 1048576 Hz) 400 million times a second.  Each operation probably takes on the order of 100 machine instructions. If we assume perfect pipelining in the microprocessor and 0 cache misses ever,  we get 1 instruction per tick. That’s 200 billion instructions, at 400 Million instructions per second, for 500 seconds processing time on our GPS unit . 8 minutes would be a long time to wait for a route, and that’s with a number of conservative assumptions.  Once you take memory latency into effect, you’re probably looking at 16-20 minutes to find a route.

Your little GPS unit inside your probably employs a heuristic that favors taking interstates over back roads, among others.  It almost definitely also uses the fact that the graph of the roads embedded on the surface of a sphere.  It sure would be interesting to figure out what kind of algorithms they use inside that little thing.  Google Maps is an entirely different story- they have much faster processors and can probably find paths in parallel. What sort of parallel algorithms for finding shortest paths exist? Could you cache frequently used route portions? How would that work ? Just something to think about.

Posted in Computer Science, Observations, Programming | Comments

On Martin Luther King Jr.

Monday, January 19th, 2009

Today is a Market Holiday, so I don’t have work. For those keeping score at home, I started working at a financial company this fall. It’s called Blue Capital, and it’s a really amazing place to work. They routinely face all kinds of interesting computer science problems that require solutions which are both elegant in theory and efficient in practice. I’m really happy there.

Anyways, back to the task at hand.  Today is Martin Luther King Jr. Day. MLK Jr. was a great civil rights leader who opened the eyes of his fellow countrymen to the injustices suffered by black Americans, particularly in the south.  Was he a great man? I think, undeniably the answer to this question is ‘yes’. However, there is a more interesting question – was he a good man? The answer to that question, I think, is ‘ probably not’.

Unfortunately, I don’t have sources for a lot of this information, which is why I prefaced my answer with ‘probably.’    Firstly, he is alleged by numerous sources to have cheated on his wife. The only real web sources I could find for this point (that weren’t from hate sites) were about.com, and the straight dope, two sites I believe to be (relatively) bias free, at least when it comes to overt racism. A lot of the allegations come from illegal FBI wiretapping of King, and can’t really be trusted, but some come from King’s lifelong friend Ralph Abernathy.

Secondly, King plagiarized significant portions of his doctoral thesis, academic papers, and speeches.

Why does any of this matter? What’s the point of dragging a revered historical figure through the mud?  My reasoning is that I think there’s an important distinction to be made between good men and great men. Great men are nice and well and all; they do change the world significantly, but great men also tend to suffer from narcissism and selfishness. Consider Albert Einstein – brilliant man who undeniably advanced the state of science, but also a jerk who cheated on his wife.

Why the fixation on adultery? Am I some kind of right-wing christian conservative? No, not hardly. A marriage is not just a simple contract between two people made for financial considerations – it’s a lifelong commitment with profound implications for children.  Cheating on your marriage partner is probably one of the worst things you can do to them. It’s an incredibly self-centered thing to do. Not only does it cause significant emotional harm to your spouse, it causes irreparable harm to any children in the marriage.  It is well documented that children do far better in stable family structures with two parents around.  (Personally I don’t think it matters what gender the parents are, as long as they love and are committed to each other, but that’s an entirely different argument.)   A little over two thirds of all black children born in America today are born to unwed mothers.  Those children do not have the same chance at success as children born into stable, two-parent families centered around a committed relationship between two adults. Any man who would cheat on his wife, betraying that bond of trust and hurting the future of his children, is not a good role model.

Is there institutionalized racism in the world today? Absolutely. Did Martin Luther King Junior do a lot of work to fight this racism?  Of course; That’s why he was a great man. However, there’s a solid difference between great men and good men. Great men do extraordinary things with their lives.  They’re good for the world. What we need, however, more than great men, is good men, men who do ordinary things extraordinarily well. Men who get up every morning to go to work, who pay their taxes and give back to their communities in the small ways that they can, and who set excellent examples for their children. Given the choice between being a great man with a flawed personal life, and a good man who never accomplishes anything ‘of note’ in the world at large, I will choose to be a good man any time. I should hope you feel the same way.

Posted in Observations, Philosophy, Politics | Comments

My New Years Resolution

Tuesday, January 6th, 2009

I’ve read that one way to ensure you accomplish your goals is by making them public and trying to get external support. That’s the point of this blog post. Ever since I first saw this video, I’ve wanted to be able to play the song. I can play most of it now, but the song makes extensive use of a technique called ’sweep picking’ that I have yet to figure out.  It’s a way of playing notes incredibly quickly – up to six notes, in rapid succession, with one stroke of the pick. It’s apparently a very difficult technique to learn. I thought about trying to rewrite the song to remove the sweep picking, but it just wouldn’t sound as cool.

I’d also like to get in shape this year, but I know people only have so much self control, and I’d rather expend all of that self control to get better at guitar. Therefore, for 2009, I resolve to learn sweep picking and learn to play all of ‘Canon Rock.’

Wish me Luck. I will post updates.

Posted in Music, Personal | Comments