Trev Harmon

  • Home
  • Business
  • HPC
  • Cloud
  • Big Data
You are here: Home / HPC / Santa, Pseudoscience and Supercomputers

December 15, 2014 by Trev Harmon Leave a Comment (REPOST)
December 8, 2014 at Santa, Pseudoscience and Supercomputers (ORIGINAL)

Santa, Pseudoscience and Supercomputers

Every year on Christmas Eve, Santa travels the globe delivering presents to children everywhere.

Santa is our culture’s only mythic figure truly believed in by a large percentage of the population. It’s a fact that most of the true believers are under eight years old, and that’s a pity.
~ Chris Van Allsburg

As we grow older and the ringing of the silver sleigh bells grow dim in our ears, we’re given to question whether or not Santa exists. Eventually, we come to the conclusion he can’t exist because his task is impossible, regardless of the attempted explanations. Or, is it?

Let’s look at some actual numbers.

Aside: While actual numerical numbers will be used, the mathematics may be a bit… suspect, shall we say.

The Traveling Santa Problem

Happy Christmas!

 

To begin with, there are a lot of people on the planet—roughly 7.3 billion to be not so exact.

That translates to lots of houses for Santa to visit. Now, before we go on much farther, I’d like to point out that again, the mathematics, assumptions, etc., used herein are suspect. Really, I’m mostly making educated guessed (i.e., making them up as I go along), though I’ll provide links to those interested in attempting to verify my conclusions (not that I’d spend time doing that, if I were you).

“So, just how many houses?” you may ask.

Ummm… let’s go with 1,333,316,210.

That number comes off of making some really poor assumptions about household data from different countries taken over more than a decade, which is not independently verifiable (See, I said it was suspect). Throwing these semi-related numbers into a spreadsheet, doing some calculations, and we get our magic number:

1,333,316,210 households
Aside: While some may say Santa doesn’t visit every house in the world, to them I say “bunkum and balderdash.” So there.

Now, all we have to do to work out Santa’s route is solve the age-old Traveling Salesman Problem. How hard can that really be? We’re HPC experts, and this is the type of problem we give undergraduates to give them heartburn.

Turns out… it’s hard.

If we were to check every possible path that Santa might take, we end up with 1,333,316,210! possible routes. And, yes, that is 1.3 billion factorial. If you’re not recalling factorial off the top of your head, it’s basically:

1,333,316,210! = 1 × 2 × 3 × 4 × ... × 1,333,316,208 × 1,333,316,209 × 1,333,316,210

That’s a big number.

I tried to get my computer to tell me what this number is. As you can guess, that didn’t go so well. It worked on the problem for a while, and then stopped. And, when I say it stopped, what I really meant was it crashed.

Luckily, it’s actually not necessary to get this number. The Held-Karp algorithm is capable of reducing that crazy, massive O() estimate to simply be:

O(n2 × 2n), where n is the number of nodes

That should be easier to calculate, right? (Easier only counts in cases where it’s possible).

O(1,333,316,2102 × 21,333,316,210)

1,333,316,2102 is pretty straightforward.

1,333,316,2102 = 1,777,732,115,848,764,100

However, as it turns out, 21,333,316,210 is a rather large number (not that 1.7 quadrillion is anything to sneeze at).

Unable to find a page conveniently listing the powers of two beyond 2222, I had to try other means. An online exponents calculator quickly, confidently and incorrectly informed me the answer was Infinity. While I give props to the coders for not having their application simply fall over crying, it wasn’t so helpful in my case.

Aside: It’s also not really surprising considering Wikipedia lists 257,885,161 as having over 17 million digits. I don’t think their UI was prepared to show that cleanly.

So, I wrote up a couple of test scripts, and then set a computer on the task of getting as far into the problem as possible over Thanksgiving week. Here’s as far as I got:

28,950,000 = 144,598,116,517 ... 284,563,639,918,527
Aside: Clearly, something has gone horribly wrong here, as the final digit is a 7, which is clearly not possible. My library must have broke somewhere along the line calculating this nearly 2.7 million digit number.

If you’re really interested, you can download the file containing the entire number.

Now, you may point out this result seems to have taken a long time to come up with an incorrect answer. Fair enough. My defense is:

  1. I have a slow workstation.
  2. I did a brute-force calculation because:
    • Laziness is one of the Three Great Virtues of a Programmer.
    • My workstation didn’t have anything to do over the holiday, and I didn’t want it to feel lonely.
    • The following chart doesn’t have a column for “Once in a Lifetime.”
xkcd: Is It Worth the Time?
xkcd: Is It Worth the Time (#1205)

So, as I’m sure you all expected, we’re at another impasse. Clearly, if Santa is using a supercomputer to calculate his course, it’s well beyond our current capacity. I also strongly suspect if he were using the same technology as us, our satellites would notice the oasis at the North Pole caused by the heat dissipation.

Aside: And, no, I’m not going to blame Saint Nick for global warming, nor am I proposing any addition to the Hollow Earth theories.

Now, it is possible that instead of traditional HPC gear, Santa is sporting a super-advanced quantum computer to provide his route. As it happens, the Traveling Salesman problem maps well to quantum computing. In 2013, one of D-Wave‘s quantum computers performed on par with the IBM/DARPS Trial Subset, a 1.5 petaFlop system with 63,360 64-bit cores on this type of problem. Now, we’re still not in the range of being able to calculate the answer to Santa’s problem, but perhaps he has a quantum computer supporting several orders of magnitude more qubits than our current systems.

Taking everything into account, I’m going with “Santa has an advanced quantum computer” as my answer here.

But Still…

There’s still the problem of the travel. How can he possibly cover all of that distance? What about the time needed to place the presents?

Let’s look at those in turn.

The first thing to consider is how close households are to each other. Now, we could assume the Earth had all of the households evenly distributed on it. Of the Earth’s roughly 510.1 million km2, approximately 149 million km2 are land. Thus, we get:

149,000,000,000,000 m2 ÷ 1,333,316,210 households ≈ 111,751 m2/household

Interesting. In yet another unscientific step, let’s go ahead with this assumption. Granted, we are ignoring the ocean travel, but at this point there are so many bad assumptions it doesn’t really matter. Plus, because Santa will need to spiral down from the North Pole to the South Pole and then back up due to the differences in day lengths in the two hemispheres, he can minimize ocean travel by crossing between major continental groups at the South Pole.

That aside, let’s look at what the distance between households would then be. Home sizes vary around the world. In the developed world, average home sizes vary between 76–206 m2. In the rest of the world, the average size is even smaller.

Arbitrarily, we’ll choose 100 m2, which is a gross over-estimate that makes the math easier. Assuming the area per household and house footprint are both perfectly square, we get the followings:

√(111,751 m2) – √(100 m2) ≈ 324.3 m

So, on average, the households are 324.3 meters apart. So, now we can get total travel distance. We’ll assume he needs to get from and to his workshop, to which we’ll apply the same distance “rules” as above.

(1,333,316,210 – 1 + 2) households × 324.3 m ≈ 432,394,447 km

That’s nearly three times the distance between the Earth and the sun (roughly 2.89 times to be exact). We have our distance.

To calculate minimum speed, let’s temporarily assume Santa doesn’t spend any time at any of the domiciles, which is clearly bunk. At any given point in the year, the average length of the night taken over the entire globe is 12 hours.

432,394,447 km ÷ 12 hours ≈ 36,032,870.58 km/hr

That’s approximately 1/30th the speed of light for an absolute minimum speed. Clearly, it’s going to be faster than that, and I’d guess with stopover time, which we’ll calculate here in a minute, it’s likely to approach or exceed the speed of light, which is going to start causing all sorts of interesting relativity effects to start to come into play.

There’s another problem with this. This speed is going to have to be maintained through an atmosphere. We all love wishing on shooting stars, which are really only masses of space debris burning up as they crash through the atmosphere at frightening, yet comparably slow speeds to what we are discussing. Actually, they might as well be standing still compared to these speeds.

Now, one might think the problem is Santa and his sleigh are simply going to burn up, which they would at those speeds. But the real problem is far more dreadful. As the reindeer and sleigh started approaching those speeds the atmospheric atoms would no longer be able to get out of the way fast enough. The result would be the compression of the atoms to a point where fusion would start to occur releasing gamma radiation. In short, even if the sleigh could withstand this, Santa’s path would be a stream of thermonuclear explosions vaporizing everything he passed and effectively destroying the Earth.

xkcd: Los Alamos
xkcd: Los Alamos (#809)

As this doesn’t happen each Christmas Eve, Santa must have a different approach. Luckily, there is one, which we’ll discuss after we get a few more facts in hand.

Before we get there, we need to also know how much time Santa spends at each household. My best source on this question is the poem “A Visit from St. Nicholas” (or as it’s better known, “‘Twas the Night Before Christmas”) by Clement Clark Moore. Unfortunately, Clement did not use very scientific measures of time when describing the events he experienced. Instead he used the following, to which I’ve attached some reasonable approximations:

Measurement Approximation Justification
flash 2.3 seconds The full cycle time (charge and flash) of a Nikon SB-910 speedlight is approximately 2.3 seconds.
twinkling 3.5 seconds We’ll assume a twinkling of an eye is 10 times longer than a blink of an eye, which is approximately 300-400 milliseconds.
bound 0.9 seconds This is roughly the longest hang time recorded for Michael Jordan.
wink 0.35 seconds A wink is analogous to a blink of an eye, so 300-400 milliseconds.
nod 1 second Just making this one up…

 
This would suggest the entire encounter took a relatively short period of time.

2.3 s + 3.5 s + 0.9 s + 0.35 s + 1 s = 8.05 s

Assuming Clement recorded an average stop, we can calculate the entire time spent.

1,333,316,210 households × 8.05 s = 10,733,195,490.5 s

Hmmm… it appears we have another problem.

10,733,195,490.5 s = 340 years 41 days 19 hours 11 minutes 30.5 seconds

Yeah… and that’s without the travel time… this appears to be pushing us into the realms of magic despite everything I’m trying.

Any sufficiently advanced technology is indistinguishable from magic.
~ Clarke’s Third Law

So, let’s see what we can do here. We know Santa not only can travel at approaching-light speeds in-atmosphere without destroying all life and civilization, but also apparently has the ability to manipulate space-time.

My guess is his sleigh must be equipped with an Alcubierre drive.

Alcubierre Drive

For those unfamiliar, an Alcubierre drive provides the ability for faster-than-light travel in a rather interesting manner. It effectively forms a space-time fabric bubble, affectionately known as a warp bubble, around the ship (or sleigh, in our case). By contracting the space-time fabric in front of the bubble and contracting it behind, it causes the space-time fabric to effectively flow around the bubble at any desired speed, even faster-than-light. Technically, the bubble itself doesn’t ever move, so it doesn’t violate any of Einstein’s theories. In fact, it is consistent with his field equations. In other words, if one had the negative-energy and/or negative-matter required, such a drive is possible.

Additionally, the sleigh must be equipped with a device capable of localized temporal dilation would be required to deal with the “340 years in one night” paradox noted above. Otherwise, there’s no way for Santa to spend any time in any of the households. That means the sleigh is also capable of producing temporal instability in the space-time fabric, requiring power on the order of the Planck energy or roughly 1028 electron volts.

That’s some engine under the hood.

It also requires a Type III civilization.

But that means…

Apparently, Santa is an alien… a visitor from another realm…

Go figure… that explains so much.

MERRY CHRISTMAS!

HAPPY HOLIDAYS!


Sources for people who really do want to attempt verification:

  • Current World Population: http://www.worldometers.info/world-population/
  • Number of Households per Country: http://en.wikipedia.org/wiki/List_of_countries_by_number_of_households
  • Surface Area of the Earth: https://www.google.com/webhp?q=surface%20area%20of%20the%20earth#q=surface+area+of+the+earth
  • Surface Area of the Earth: http://www.universetoday.com/25756/surface-area-of-the-earth/
  • International House Sizes: http://www.demographia.com/db-intlhouse.htm
  • Distance Between Earth and Sun: https://www.google.com/webhp?q=distance%20earth%20to%20sun#q=distance+earth+to+sun

Images courtesy of:

  • Russian Space Santa – Steve Jurvetson – CC-BY-2.0
  • Los Alamos – xkcd – License
  • Is It Worth the Time? – xkcd – License
  • Warp Drive Diagram – BigRip Wiki – CC-BY-2.0

Filed Under: HPC Tagged With: Albert Einstein, Alcubierre drive, alien, Chris Van Allsburg, Christmas, Clarke's Third Law, Clement Clark Moore, D-Wave, Held-Karp algorithm, HPC, laziness, Los Alamos, mind experiment, Planck energy, presents, quantum computing, Santa, satire, silver bells, traveling salesman problem, Twas the Night Before Christmas, warp, xkcd

Leave a Reply Cancel reply

Your email address will not be published. Required fields are marked *

The Manifesto

Conscious Business Ethics

BusinessEthics300

Learn why it matters. Then sign it!

Get Updates!

Affiliate Disclosure

This site offers affiliate links to some online retailers such as Amazon.com in conjunction with hyper-linked books, movies, music and other such items. IF you click on these links and subsequently make a purchase, I will receive a small percentage of the transaction price

Twitter: trev_harmon

  • RT @saysthefox: I think everyone could use a lighthearted/happy story right now so here goes: At the beginning of the pandemic I went thro… 09:17:21 AM December 12, 2020 ReplyRetweetFavorite
  • #DoGoodRecklessly https://t.co/EjpxC0Mess 08:13:43 AM December 12, 2020 ReplyRetweetFavorite
  • 😁 https://t.co/bjYurTuVq0 10:20:50 PM December 11, 2020 ReplyRetweetFavorite
  • Even with all the craziness in the world, there’s much to be grateful for. Gratitude is good for the soul. I… https://t.co/CClHtRzMg1 11:02:29 PM November 26, 2020 ReplyRetweetFavorite
@trev_harmon

Writer, software architect, educator, blogger, photographer, would-be designer, and a believer in the power of simplicity and human-based design.

Other Blogs

Trev Harmon can also be read at:

  • Dream.Learn.Discover
    Primary Author -- This blog is about seeing the good in the world. With all the bad, evil and destruction, there are many, many people who are creating good in their sphere of influence. Some of these spheres are large and some are small. There is a time allotted to each one of us. It is with this time some decide to do remarkable things, though they may not believe them to be remarkable at the time.
  • Adaptive Computing
    Contributor -- The world of high-performance, cloud and supercomputing is opening the way for many new and exciting discoveries. As we push our quest for knowledge forward, technology will play a key role in supplementing our ability to learn and discover.

Copyright © 2021 · Executive Pro Theme on Genesis Framework · WordPress · Log in