Welcome to the final part of my backward crawl through time, showing you that the ideas of computation and complexity exist outside of those gadgets and devices you hold in your hand. This is a broad topic, so I’ve stuck to a theme, namely powers of two. Exponential growth has a bit of a hold on popular thought. Underestimating how fast such growth can occur is at the heart of “clever” tricks from tales such as the rice-on-a-chessboard con. Last week I gave an example of this fascination that was a bit older than you might have guessed.

This week I will talk about something much older: Your ancestors. *All of them.*

Most people know their parents, (I say this with apologies to those who don’t). Most people also know their grandparents. After that, things get a little hazy. Of course, I’m assuming both of my parents know who their grandparents were, so I could ask them. And if you are young enough, you could likely ask your grandparents the same question. So if you really really had to, with a little luck and effort, you could probably construct a full and complete binary tree (like the one from the Twenty Questions game) and build up a family tree stretching back to your great-great grandparents. How big is this tree? Well you have 2 parents, 4 grandparents (1g-parents), 8 great-grandparents (2g-parents) and 16 great-great-grandparents (3g-parents). Including yourself, the tree has 31 people in it. This is the familiar pattern we’ve been seeing; the powers of two and the cumulative sum of them, which is always one less than the /next/ power of two. Let’s say that tracking your ancestry back to all 16 of your 3g-parents was common practice. If you still had contact with your grandparents, you could ask them about their 3g-ancestry, and you could reach all the way back to your 5g-parents … all 64 of them. Imagine that if tracking that much ancestry was common practice, then you could ask your parents or grandparents for just that one or two extra levels, but you can see how this is getting to be a lot of book-keeping already, which should explain why genealogy still has legs as a hobby.

Tracking your ancestry is a computationally expensive task and I’ll bet you never thought of it that way. It has always been so, even long before we had any notion of such. Today your ancestry is, by and large, just one of several interests you might have, but it’s not really important on a global scale. However, for much of human history, political power and influence was pretty much directly connected to one’s ancestry. Our modern democratic sensibilities balk at this fact anyway, but the fact that the ancient and medieval world was ill-equipped to exhaustively chart a person’s ancestry much farther back than one or two centuries should lend an even greater sense of inefficiency and illegitimacy to the practice. Similarly, while it doesn’t excuse the sexism involved, the exponential difficulty of considering all of a person’s ancestry at least explains why most cultures would look for a shortcut such as putting emphasis on patrilinear ancestry, (if you think only the father matters, then each generation remains the same size).

The Bible, in it’s most boring moments, lists so-and-so begetting so-and-so begetting so-and-so, trying to legitimize figures by their relation to previous ones. The Sunni/Shia schism in Islam is essentially a dispute over ancestry. French, English and Spanish borders have been blurry at times thanks to who begat who. So in more ways than one, ancestry is an exponentially big deal.

Our modern sensibilities, the one’s that balk at power-by-ancestry, like to laugh at the royal families of yesteryear for their famous amounts of inbreeding. One of the most famous cases is poor Charles II of Spain. Among other things, a single woman, Joanna of Castille accounts for 2 of his 16 4g-mothers, 6 of his 32 5g-mothers and 6 of his 64 6g-mothers. It is easy for us to scoff at such foolishness, but how much better does the average person fare? If most people are, at best, only vaguely aware of some of their great and great-great-grandparents, our smugness might be misplaced.

For simplicity, let us assume that a generation is 25 years, so we have four generations per century. You go back 100 years and you have 16 living ancestors. You go back 200 years and you have 256. 300 years ago you had 4096 ancestors. That’s a lot of people, and at this point you might be willing to concede that, sure, a few of those 4,000 people might overlap. Let’s go back to Roman times, we’ll say 1 AD. That’s 20 centuries ago. Your 78g-parents are alive during this time. How big has your family tree grown at this point? Would believe that about 1.2 Septillion of 1.2 trillion-trillion ancestors. You might realize that this absolutely dwarfs today’s global population, much less the global population during Roman times, which might be estimated at about 300 million. That’s a *lot* of overlap, and it is very generous to assume that the entire world’s population went into producing each of us.

In fact, the point at which the count of living ancestors eclipses the global population would be around the year 1300. Which means that the most optimistic assessment of inbreeding would assume that each of us is a descendant of every historical figure born before 1300. Caesar, Charlemange, Genghis Khan, Muhammad. This seems rather doubtful. We may not be as poorly off as Charles II, but it’s reasonable to say that at some point we’re all a little bit inbred.

Looking to the future, this problem, (in as much as it is a problem), is basically unsolvable. With computers we could start charting the ancestry of every person alive today and born after. We might do okay for a while, but unless you think civilization is going to utterly collapse over the next 1000 years, it would eventually become impossible to track all of this information. This is arguably the oldest computational challenge facing humanity and we will never solve it. It is easy to treat computers like magic devices, but there is a hard truth in numbers and computation and math that makes many things impossible no matter what you say about Moore’s Law.