Monthly Archives: August 2016

No Man’s Sky birthday problem

Demo here. Code here.

My birthday is coming up in a couple days, so what better way to celebrate than by implementing a birthday problem calculator in JavaScript?

Don’t answer. I know the answer.

I actually started down this path after reading about how a pair of No Man’s Sky players have already found each other in-game, which was supposed to be nearly impossible. In fact, it’s happened a bunch. I suspect that the developers have underestimated a version of birthday problem. That’s the thing you might have heard about in elementary school, where a surprisingly small group of people will likely have a pair of individuals with the same birthday.

I’m not the only one to come to have this idea, as this comment by reddit user madbadanddangerous shows.

I’ve heard that there are about a billion planets a player can start out on (out of some quintillions of total planets). And the game has sold at least a couple hundred thousand copies, so let’s assume 150,000 players.

Aaaaand my calculator cannot handle those numbers. It just freezes, and I think it might be one of those heat death of the universe length calculations.

UPDATE: I added and approximating calculator. It’ll work for huge numbers.

Aside: factorials shouldn’t be terribly complex calculations, so I think the computer just gets bogged down with trying to handle massive numbers. If you have a fix to this problem, please submit a PR!

Check out this less accurate but actually functional calculator to get a sense of the probability. Going with 1,000,000,000 planets and 150,000 players yields a ~99.998% chance that at least 2 people will start on the same planet. Seems a little high, but that’s the math!

Technical Summary

This was a small project, so there’s not much of a postmortem! It took me maybe 3 or 4 hours to write, which is 2 hours more than I expected. Which sounds about right.

I find the probability with  1 - (d!/((d-n)!) * d^n) , where d is number of days, and n is number of people, from this Wolfram Mathworld article. Wikipedia indicates that there are some ways of approximating the value faster. I might try that.

Much of the time was spent setting up Math.js after realizing that even the standard case with 365 days overflows JS’s integer type. I am surprised to find that Math.js’s factorial function doesn’t cache its calculations, which means repeated calculations aren’t efficient.

Still, factorials shouldn’t have O(n!) time complexity or anything. I think the sluggishness comes from managing the huge numbers involved. A billion factorial is flipping huge.

Another chunk of the time was spent googling how to interact with the DOM without JQuery. Turns out it’s possible, who woulda thought?

Anyways, there you go. The Birthday Problem. No Man’s Sky. Hash collisions.

1 Comment

Filed under code, Uncategorized