A function to sleep a 1000 years: explained

I encountered a code challenge that asked for a sleep function that sleeps a 1000 years. The current functions use an integer to declare the amount of seconds, but 232 is only around a 100 years long.

A smart guy posted this interesting line of C code:

i;f(){--i&&f(sleep(7));}

This works fairly correctly, surprisingly. Let’s look further into it!

First, we’ll dissect the code into more readable code:

i;
f() {
	--i && f(sleep(7));
}

The first line creates a signed integer, called i. According to the C99 standard, section 6.7.8.10, it will be initialized as 0:

If an object that has automatic storage duration is not initialized explicitly, its value is indeterminate. If an object that has static storage duration is not initialized explicitly, then:

— if it has pointer type, it is initialized to a null pointer;
— if it has arithmetic type, it is initialized to (positive or unsigned) zero;
— if it is an aggregate, every member is initialized (recursively) according to these rules;
— if it is a union, the first named member is initialized (recursively) according to these rules.

Section 6.7.1.2 tells us that we have to define a declaration specifier. Therefore, i would have to become int i. However, in C89, this was not yet a rule. This is what the rationale of C99 tells us about that:

A new feature of C99: In C89, all type specifiers could be omitted from the declaration specifiers in a declaration. In such a case int was implied. The Committee decided that the inherent danger of this feature outweighed its convenience, and so it was removed. The effect is to guarantee the production of a diagnostic that will catch an additional category of programming errors. After issuing the diagnostic, an implementation may choose to assume an implicit int and continue to translate the program in order to support existing source code that exploits this feature.

Now, we know that i would have been an int, if we use C89 rules. gcc will not give us an error if we try to do this, but just give us a warning:

warning: type defaults to ‘int’ in declaration of ‘i’ [-Wimplicit-int]

According to section 6.2.5.12, integers are arithmetic types. This, in combination with the second rule, makes that i will now be 0.

Then, the function f() is declared. This function takes no parameters and gets the default return type. This is also an int, because of the exact same rule as quoted above.

So, now we have an int called i and a function with return type int called f(). Let’s look at the contents of f()!

--i && f(sleep(7));

You have to understand that --i means that 1 will be substracted from i, before it is being evaluated. This means that we start with -1 in i.

The second part is actually more interesting. f() is called recursively, but with a parameter! Let’s look at another example that I wrote:

#include <stdio.h>

f() {
	printf("Bye world!\n");
}

int main(int argc, char const *argv[])
{
	f(printf("Hello world!\n"));
	return 0;
}

This actually outputs the following:

Hello world!
Bye world!

Apparently, we can still pass things to our function. They will be executed. If you want to avoid this, you will have to give void as the parameter type. So the following would not have worked:

f(void) {
	printf("Bye world!\n");
}

Now, we know why the recursive function works. So, when does it stop? According to the author, it stops at approximately a thousand years. He tells us it will run for around 952.69 years.

Let’s look at when the function technically stops. To start with this, you have to know that every number but 0, is true. Just looking at the function does not help a lot. There is not even a return value! For this, you have to be familiar with short-circuit operators. The following means that f(sleep(7))will only be executed, if --iis true. This is always the case, except for i == 0. This means that f(sleep(7)) will be run until i is 0:

--i && f(sleep(7));

So, when will i be 0? Well, i is a signed integer, which has a size of 32 bits. That means that i has a minimum value of -(2^31), which is -2147483648, and a maximum value of 2^31, thus 2147483648. We will go from -1 to -2147483648 and then we will flip to 2147483648. We will see 2^32 = 4294967296 values for i. -1though, because 0 is not an option. 0 would mean that f(sleep(7)) would not be run, and that’s the end of our f().

So, sleep(7) will be executed 4294967295 times. Let’s calculate the amount of years that this will run.

The amount of seconds: 4294967295 * 7 = 30064771065
The amount of hours: 30064771065 / 3600 = 8351325.3
The amount of days: 8351325.3 / 24 = 347971.9
The amount of years: 347971.9 / 365.25 = 952.7

So this code will indeed run for a thousand years, with a margin of ten percent.

With this, we have proven that this beautiful line of code is correct!

Published by

Robin Martijn

I am Robin Martijn, a developer and entrepreneur from the Netherlands. I was born in Rotterdam and now live in the quiet village of Brielle. I am involved in innovation developments in the field of healthcare and aviation technology. I am also chairman of the study association of the Computer Science and Engineering course in Rotterdam.

17 thoughts on “A function to sleep a 1000 years: explained”

  1. Wrong, wrong and wrong.

    The C standard doesn’t specify that you must have enough stack memory even for a single function call. Much less of 2^32 recursive calls stacking the result of sleep and the return address. In practice, stack sizes are rather limited, and you will never be able to recurse more than a few tens of times.

    More over, sleep can be interrupted. And if one, why note O(n) times. Therefore instead of sleeping n*7 seconds, you might sleep only n*3 or any factor less than 7. You won’t reach the destination time this way.

    And finally, I would mention relativity. On small times, we don’t care if we sleep half the time or twice the time, because of relativity, because it’s already past, we’re just happy we haven’t crashed so far. But if you are to wait for 1000 years, you must take into account relativity, and define your duration in a more precise way. What to do if your frame is accelerated. What if a big mass comes close, or if its mass is greatly reduced. Is it 1000 years in the frame of the computer, or that of the user, etc.

    And since I mentioned crashes, you might want to deal with them, and resume waiting on restarts, and you wouldn’t want to restart waiting for 1000 years after having waited for 998 years and crashed.

    It is not a beautiful line of code, and it fails miserably in multiple ways to achieve its purpose. Bad.

    1. Hi Pascal. Thank you for your detailed explanation.

      I agree with you that this piece of code has a lot of limitations and problems. I am not going to tell you that you are wrong about this, because you are not, but you must understand that it is not the purpose of Code Golf to be useful in production or even in development.

      They do this code challenges because they like to explore the boundaries of programming languages. Their main objective is almost always to write an application or function that does the trick in the lowest amount of bytes possible.

      Also, you should read the opening post of this challenge. It explicitly mentions this:

      You don’t need to worry about wasting CPU power – it can be a busy-loop. Assume that nothing special happens while your program waits – no hardware errors or power failures, and the computer’s clock magically continues running (even when it’s on battery power).

      I do understand your issues with the code and I am of course glad to see that there are still programmers that actually care about things like efficiency and completeness, but that is not the goal of this challenge.

  2. Sounds good! Although probably we will run out of stack waay before that 🙂

    Also, is there any overhead in executing two functions 4294967295 times? Somewhere on stackoverflow someone mentioned 3 nanoseconds for calling a function. Times 4294967295 times 2 it will be just 25 seconds. Wow computers are fast!

    1. Hey Alex! That is an amazing question! The overhead of calling a function that many times is very small, as you already calculated.

      There is however another, bigger issue that you are partly addressing: stack overflow. Not the website, but the runtime error. Because we are running f() recursively, the stack will increase enormously.

  3. You quote the standard to mention that i will be initialized to 0, and I agree. However, signed integer overflow (and underflow) is undefined behavior. Thus the transition from i == INT_MIN to i == INT_MAX by subtracting one is undefined. So this line of code is in fact not correct.

    1. Hi George! That’s a very valid point. The C99 standard tells us this about that in section 6.5/5:

      If an exceptional condition occurs during the evaluation of an expression (that is, if the result is not mathematically defined or not in the range of representable values for its type), the behavior is undefined.

      Therefore, you are absolutely correct of course. This means that you depend on your compiler for this.

      This example was written for gcc which allows you to pass -fwrapv. This defines the behaviour of signed integer overflows to wrap.

      I am not entirely sure what the default behaviour of gcc is.

      1. Te default behavior of cc is to consider the behavior undefined and thus do “what the f**k he want”.

        In this exact exact example, gcc do what you expect, but if you change it just a little bit it becomes an infinite loop: https://godbolt.org/z/kTX0Dr

        I’d like to take the opportunity of this comment to warn every new C/C++ developers: be very careful about undefined behavior. Never assume the compiler will make something that makes sense. Never assume that because it works when you test, it’s fine. You should (must?) read the “What Every C Programmer Should Know About Undefined Behavior” blog posts series (http://blog.llvm.org/2011/05/what-every-c-programmer-should-know.html) before doing any production work in C/C++. ( Of course, for a fun thing like code golf, do what you want. )

  4. I don’t think anyone mentioned the more obvious problems: C and the realization of a C program in machine code are unlikely to be supported in any mainstream way in 1000 years from now, especially if your computer is updated regularly by a company like Microsoft.

    But, assuming you isolate your computer from damage from the Internet, it is further doubtful that you can obtain hardware that can run for any sizeable fraction of 100 years, much less 1000, due to component failures.

    Finally, even if you had reliable hardware, it is unlikely that its power source would last for 1000 years, given the reality that you would have to bury the computer very deep to protect it from damage.

    The only way to succeed would be very costly: to launch it into orbit with very thick and multiple forms of shielding to protect it from micrometeorites, weapons, collisions, EM pulses, and other forms of damage.

    1. Hey David! All valid points of course, but this challenge specifically mentioned to ignore all of these three points, as you can read in the opening post.

      Code Golf is about testing the limits of the programming languages and most of the times, the users try to use the least amount of bytes as possible.

  5. So, –i, will keep on subtracting 1 from it until it reaches -2147483648, then continues down to (2147483648-1), until it reaches 0?
    Right?

Leave a Reply

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