How Many Tribbles?

Assuming I haven’t made a mistake in time zone calculations, this post should go online exactly 50 years after the intrepid crew of USS Enterprise appeared on American screens for the first time. Since then, the adventures of Starfleet officers have been depicted in six TV series and 13 movies. Even though newer Treks are in many ways better, The Original Series will be forever beloved for its unique charm. Here is the opening of The Man Trap, the exact episode that aired 50 years ago:

Anyway, this is a math blog, so I should write about the math of Star Trek. This is a broad topic, and I decided to only discuss one scene, which involves tribbles. Tribbles are funny little creatures famous for being infallible Klingon detectors and notorious for reproducing way too fast. Soon after Deep Space Station K-7 was infiltrated with them, Kirk discovered a population living in a grain storage tank:

Spock estimated that the tank contained 1,771,561 tribbles under the assumptions that a single tribble had entered the tank three day before and had been producing a litter of 10 every 12 hours since then. Knowing Spock, it is hard to imagine him solving such a simple problem incorrectly, but let’s confirm his result anyway.

When a tribble produces a litter of 10, the number of tribbles multiplies by 11 (10 for offsprings + 1 for original tribble). They had just enough time for 6 reproduction cycles, so we would expect to have 116 tribbles, which is exactly the number that Spock arrived at. Great!

If you want to learn more about the math of Star Trek, I recommend an excellent video by James Grime:

If you want to solve a Star Trek-themed cipher, go check it out.

Finally, if you want to celebrate the anniversary of Star Trek in another brilliant way,

Engage!

Posted in Uncategorized | Leave a comment

Cipher 12

After a very long break, Cipher 12 has finally been released.

Posted in Ciphers | Leave a comment

A Question Most People Get Wrong

A few days ago I created a Twitter thing called Geeky Polls. The first poll I posted was this one:

At first glance, this question may look like an obfuscated version of the liar paradox. However, it is not paradoxical, and you can answer correctly by choosing whichever option fewer people preferred.

When I made this poll, I expected that both answer choices will get roughly equal number of votes. Surprisingly, this turned out not to be the case: one of the options received 71% of votes. In case you haven’t voted yet, I will not disclose which option was more popular, since it would allow you to cheat.

But is this difference significant? Let’s find out. The poll attracted the attention of 70 people. The last time I checked, 71% of 70 was 50, so that’s how many people preferred the Popular Option. 20 people chose the Unpopular Option – what nice round numbers!

We can now start some kind of analysis. I will not use Bayesian approach because it is not suitable in this situation I know nothing about it, so let’s stick to good old frequentism. In this case, the p-value is the probability that 70 coin tosses will result in some side showing up at least 50 times. There are two ways to calculate it: smart one (do the math) and silly one (write a program). I will use the second approach.

Since you are probably tired of me posting Delphi apps, here is some nice and clean JS code:

var numTries = 100000;

var i, j, heads, skewed;

skewed = 0;
for (i = 0; i < numTries; i++) {
    heads = 0;
    for (j = 0; j < 70; j++) {
        if (random(0, 1) > 0.5) {
            heads++;
        }
    }
    if (heads <= 20 || heads >= 50) {
        skewed++;
    }
}

// As you can see, I multiplied the p-value by 10000
// Hence, any output less than 500 will indicate significance
println(10000 * skewed / numTries);

This code gives the result of 4.3, which is much less than 500. Significance proven! Well, technically, it’s not. Since the program is randomized, there is always a possibility that it will take an insignificant result and mark it as significant. It means that we should conduct a statistical analysis to determine the significance of the result coming out of significance-testing program… My head hurts. That’s why serious people always choose the mathematical approach.

Anyway, goodbye for now. If you would like to know what the correct answer to the question is, just vote yourself!

Posted in Uncategorized | Leave a comment

Epoch Article, Part 2

This is the second part of a two-part post about measuring time. Part one is here.

 

Last time we discussed our familiar calendar, and the conclusion was that it is really messy. Well, then we should maybe make a better one?

This idea is much less crazy than it sounds. Of course, it would be very hard, if not impossible, to persuade the entire world’s population to switch to a better calendar. But there is point in having a special calendar to be used by tech people in solving problems that are hard enough even without all these leap years.

In the simplest possible calendar, time is a single real number. This number indicates how many [time units] have elapsed since [reference date]. Easy, right? Well, as you have probably already guessed, the answer is “wrong”.

Julian date

The first people to adopt such calendar were astronomers. Their apparent lack of imagination resulted in the calendar being called Julian date. It is the number of days since noon GMT January 1, 4713 BC. Dealing with Julian date is simple; the only problem arises when one wants to convert between Julian and ordinary dates. This is done by using two extremely complex formulas, the more frightening of which is shown below:



There is even a joke among programmers that no living person understands the meaning of these coefficients.

Stardate

USS Enterprise near Saturn

Up to this point, I successfully avoided speaking about fictional calendars. However, now I can’t resist writing a few words about Stardate.

Stardate is used by humans and other intelligent species in the Star Trek universe. It is always a single real number, but other than that, the format of Stardate varies wildly between different series and movies. Let’s first focus on Stardates in The Original Series.

The first episode starts with Kirk saying “Captain’s Log, Stardate 1513.1”. The most interesting question is whether this is a real date that can be converted to something else or just a random number. We could find the answer by browsing Wikipedia or Memory Alpha, but that’s not how mathematicians do it. Instead, let’s compare the number of digits in Stardate and ordinary date.

Stardate has 5 digits, that’s easy. Date in Gregorian calendar has two digits for day, but the first one doesn’t go all the way up to nine, so it’s like half a digit. Month is also two digits, but the first one doesn’t really count because it is usually zero. Using the same logic, we can say that the year has 3½ digits. In total, we have 6 digits. Therefore, Stardate either has very low precision or, more likely, it is made up. Memory Alpha confirms that Stardates were indeed chosen arbitrarily.

Note: If you are in high school learning logarithms, try doing your homework like this. Your Math teacher will love it.

Since I am writing this post only days after Star Trek Beyond came out, I should probably talk about Stardate as it appears in the newest Star Trek movies. There is not much to speak about, actually: the integer part is the year, and the fractional part is, quite counterintuitively, the number of days since the start of a year. For example, 2233.04 means the fourth day of 2233.

Unix time

Let’s get back to serious business. Single-number calendars are currently most widely used by computers. It would be great if all programmers agreed on one universal calendar, but they instead created a multitude of incompatible ones via the following scheme:

How standards proliferate

The only calendar that stands out from the rest is Unix time, used by all Unix-like operating systems. It uses the reference date (by the way, it is also called epoch) of January 1, 1970. The time increments by one every second, which is convenient, because it allows to drop the fractional part unless you need very high precision. Unix was not designed for such high precision, so it stored the time in a signed 32-bit integer.

Signed 32-bit integer can store a value between -231 and 231-1 inclusive. If you assign the highest possible number to a 32-bit variable and then try to increment it, one of two things will happen:

  1. You will get an error.
  2. The number will “wrap around”, and you will get -231. This option is much more likely than the first one.

In either case, it is obvious that everything will break when the Unix time overflows. But when will this happen?

A relatively useless chart

The chart above suggests that 231 seconds are just under one century, so the overflow should occur a bit before 2070. More precisely, it will happen at 03:14:07 UTC January 19, 2038.

Fortunately, most systems manufactured today use 64-bit integers, so they should avoid all problems… except they don’t. Not long ago it turned out that iPhone stored dates in an unsigned 64-bit integer, which can only manipulate numbers between 0 and 264-1. When the phone needed to deal with a date before 1970, it wrapped around and broke down.

There is of course more to Unix time than overflow and underflow errors. For example, every time a leap second is introduced, programmers have a massive headache.

Also, having a birthday on January 1, 1970 can probably be as bad as having surname Null.

Other systems

As I mentioned before, Unix time is not the only time standard used in computing. You can see a relatively complete list here.

Conclusion

Fortunately, most programming languages have a built-in date type, which takes care of more or less all issues that may arise. Use it; don’t try to make you own time libraries, because that way lies madness.

Live long and prosper.

Posted in Uncategorized | 1 Comment

Epoch Article, Part 1

This is the first part of a two-part post about measuring time. Part two is here.

 

In Physics class, we learn how to measure different things. We measure length, area, volume, velocity, force, energy, momentum, etc. using stone age tools and, in most complex cases, even primary school math. Then we express the values in SI units, perhaps with some prefix, or in different units entirely, in which case everyone is confused and outraged.

However, there is something we learn to measure long before we hear the word “physics”. This thing is time. As small children, we get a seemingly firm grasp of clocks and calendars, and then, when we grow up, we regard time as something simple and not even worth talking about.

In this article, I want to give a hint that dealing with time is actually extremely complicated, or at least much more complicated than high school Physics curriculum.

From second to day

A second is one of the base SI units. Like all other base units, it is defined in a bizarre and counterintuitive manner, namely as “the duration of 9,192,631,770 periods of the radiation corresponding to the transition between the two hyperfine levels of the ground state of the caesium-133 atom”. I will not comment on this definition, since I don’t really understand it myself.

Next, there is a minute, which is 60 seconds, right? Wrong. Since the Earth does not spin at a perfectly constant speed, sometimes it is neccessary to insert a leap second, which essentially makes an unlucky minute 61 seconds long. When a leap second is inserted, time goes like this:

… 23:59:58 23:59:59 23:59:60 00:00:00 00:00:01 …

To make things worse, leap seconds are added at irregular intervals.

60 minutes make an hour, and 24 hours make a day, and here we don’t encounter any difficulties… although, wait, we do. But let’s put them in the next section.

Time zones

Since the Sun rises and sets at different time depending on the longtitude, people created time zones. We could have just divided the Earth into 24 equal slices and call them time zones UTC-12 to UTC+11 or UTC-11 to UTC+12 if you prefer. It is a great idea, except everybody disliked it. Small countries didn’t want to be split between two time zones and so on. As a result, the map of time zones became surprisingly complex.

Map of time zones

There is one more strange thing about this map: time zones are not just weirdly shaped, there are also too many of them. Let’s look at the list. There are 39 time zones, some of which seem really redundant, like UTC+12:45.

In addition, time zones are not constant. Countries change them every now and then. For example, Samoa once decided to hop to the other side of the International Date Line and therefore skipped an entire day.

And then there is West Bank, where Israeli and Palestinian people live in accordance with different time zones…

DST

What’s next? In many countries, time is shifted one hour forward in spring and one hour backward in autumn, so that people’s waking hours are better aligned with the day / night cycle. There are lots of problems with this.

Firstly, countries shift clocks on different days. Secondly, countries in the Southern hemisphere have spring and autumn at the wrong time, so they enable DST when everybody else disables it. And thirdly, there are countries that think there is not enough confusion as is, so they add even more problems.

Russia, in which I happen to live, is one such country. Before every spring and autumn, some important guys toss a coin call random() ask the god of time measurement do the evaluation of possible economic gains and decide whether we should shift clocks. What I don’t understand is why they are getting a different answer every time. Makers of computers and smartphones tried to keep up, but apparently gave up on it. My iPhone is currently one hour ahead of real time.

From day to year

Let’s move to longer periods of time. A month can have 28 to 31 days, and the distribution of long and short months seems pretty random. Or at least it’s close enough to random that most people have trouble remembering it.

A stick man from xkcd tries to figure out how long October is

Actually, there is some logic behind this distribution, but it is a topic for a different article. Anyway, compared to what I covered in the previous sections, this is a minor annoyance. The big problem comes when you get to February, which becomes one day longer in leap years.

Leap years exist because the year does not have an integer number of days. It is very close to 365¼ days, and that’s why about one in four years is leap. Unfortunately, the number of days in a year is slightly different from 365¼, and therefore the Julian calendar, where exactly every fourth year was leap, didn’t work out well. People switched to Gregorian calendar, which has the following rules for deciding what years should be leap:

  • A year divisible by 4 is leap.
  • Well, unless it’s also divisible by 100, in which case it’s not leap.
  • But if the year is also divisible by 400, it will be leap.

So far, this is not too difficult to remember and/or implement in an app. There is one issue, though: remember how I said that we switched to a refined calendar? Of course, every country did this at a different time, and some countries did it in really weird ways.

And beyond

Years seem to be the easiest thing about dealing with time. Sure, there was no year 0, but it was long ago, and it doesn’t take more than a couple lines of code to implement anyway. Except this, years have no surprises for us, right? Wrong.

In the 20th century, people thought that the year 2000 is unimaginably far away and not worth thinking about. Hence, many systems stored only the last 2 digits of the year. As 2000 approached, programmers had to change all their code to accept four-digit years. As it always happens with this sort of thing, redoing took much more effort than making everything normal in the first place would. Also, some people apparently forgot to fix it at all.

Sign displaying year 1900

Some guys propose that we go one step further and switch to five-digit years right away. If I will be still maintaining this blog 8000 years later, I will surely write a follow-up post explaining if they were right or not.

One thing to consider

Did you know that our calendar isn’t the only one? Just imagine that we multiply all the problems presented here by the number of calendars used in the world. I must say that my imagination is not even nearly good enough for this.

Tom Scott’s video

Tom Scott once made a video about the same subject, so if you want to learn more, or just like to watch videos embedded in blog posts, here it is:

 

This was part one. Part two has a lot of interesting stuff about Julian date, Stardate, and Unix time. Check it out!

Posted in Uncategorized | 1 Comment

Origami

From now on, I will post photos of my origami models in a special area of my blog. This area is located here. I started things off with a relatively simple yet interesting model, Net of a Tesseract.

When I post new models, I will not put announcements like this one on the front page of my blog. If you would like to see the models, you will have to occasionally visit the origami page.

Posted in Site-related | Leave a comment

Cipher 11

Cipher 11 has been released.

Posted in Ciphers | Leave a comment