How fast can a computer count till 2⁶⁴?

I came across an interesting question on Reddit: How long would it take for the fastest computer today to count up to the unsigned 64-bit integer limit?

The answer given is

When you say “count” what do you mean? If it’s just to go through each number in sequence as quickly as possible it’d be pretty stupid fast. Probably less than a minute

This is wrong.

This x86 assembly code snippet counts from 0 to 2⁶⁴ − 1 on a register (rcx in this case):

; rcx (our counter) := 0
    mov rcx, 0          
; rax := 2^(64)-1 
    mov rax, 18_446_744_073_709_551_615    

;; Here is the counting loop
; We have a label called loop:
; Then we increment rcx
; Then we check if rcx < rax. 
; If it is we go back to our loop label.

loop: 
    inc rcx
    cmp rcx, rax
    jl loop     

The counting loop consists of three instructions, inc, cmp and jl. Each of these uses 1 cycle. The fastest consumer grade processor currently available runs at about 6.2GHz (6.2-billion cycles per second). Ignoring pipelining and branch prediction, here’s a back-of-the-envelope estimate of the time it would take for this code to execute:

• Total clock cycles = 3 * number of loops = 3 * 2⁶⁴ = 5.5e19.

• Number of seconds = total clock cycles divided by 6.2GHz = 5.5e19/6.2 * 109 ~= 8.9-billion seconds.

This is just shy of 283 years. Somewhat longer than “less than a minute”. But because of the fancy features of a modern CPU core, we can actually do considerably better than this. I tested it on my i7 which my operating system claims has a fastest clock rate of 5.2Ghz.

Instead of counting to 2⁶⁴ − 1, I set it to count to 2³⁶ − 1 and benchmarked it. The best I could get was 7.3 seconds. Projected to 2⁶⁴ − 1, this is over 60 years.

I then tried to optimize the code in various ways. The most successful was repeating the inc instruction 351 times inside the loop (2³⁶ − 1 is divisible by 351). The best time I could get was about 2.25 seconds. Projected to 2⁶⁴ − 1, that’s over 19 years. (Incidentally, repeating the inc command too many times, say millions, slows down execution considerably. I tried it.)

Making the optimistic assumption that the fastest CPU core in the world could do this in half the time, that’s close to 10 years to count from 0 to 2⁶⁴ − 1.

In practice, I suspect it would take considerably longer. CPU cores cannot run at their fastest clock speed for ten years. They break down. Electricity seldom runs without interruption for that long. The problems are many.

Of course, one could divide the work between many cores.

How long to count to 2¹²⁸?

Thoth, an alien, takes control of earth. She has obsessive compulsive disorder: whenever she takes over a planet, she needs all its language-capable beings to use all the computers available to count to 2¹²⁸. She has a massive inventory of super-computers, enough for all 10-billion humans on earth (this is in the future). Each super-computer has 20,000 cores, capable of incrementing a trillion times a second, far faster than any earthly computer.

Every human on earth has an ID from 0 to 10-billion - 1. Each human is responsible for ensuring their computer counts from 2¹²⁸ / 10-billion * ID to 2¹²⁸ / 10-billion * (ID + 1) - 1.

Even with this absolutely ginormous amount of computing power, far more than exists on earth today (or ever?), it would take over 50,000 years to complete the count.

What I find amazing about this is that if you take 128 bits, whose volume is a fraction of a cubic nanometre, there are more states they could be in than will ever be represented by all the computers on earth for the conceivable future. It is astounding how many ways even an insignificant amount of matter like this can be recombined. With 256 bits, the number of possible states approximates the number of atoms in the universe. With 512 bits, we’re vastly past that. My computer’s memory has about 8-billion bits. The number of possible states, 2^{8, 000, 000, 000} is well beyond astronomical.