The never-ending finite loop

http://www.daemonology.net/blog/2010-08-02-neverending-finite-loop.html

by cperciva • 16 years ago

57 22 16 years ago

btilly2• 16 years ago

I think you can save 2 characters. Here is the original

  char i,x[99];for(x[98]=i=1;x[98];i++)i*=!++x[i];

Here is my improved version

  int i,x[99];for(x[98]=i=1;x[98];)i*=!++x[i++];

ToastOpt• 16 years ago

your "improved" version illegally modifies 'i' twice in the same statement; its results are undefined.

btilly2• 16 years ago

You are right. But there are two outcomes I think are likely. The ++ could happen either before or after the * . Under either outcome the loop is finite in theory but not practice.

The possibility that I consider unlikely, of course, is that I've broken some assumption that causes the compiler to optimize cause an entirely undefined third behavior (such as crashing). Then the outcome is undefined. That is the kind of implementation detail that code golf often brushes against. I'm not sure whether a solution that includes that possibility but which happens to work on, say, gcc is considered legal.

But that suggests the following unambiguous form:

    int i,x[99];for(x[98]=i=1;x[98];)i*=!++x[++i];

nburger2• 16 years ago

And you could save an additional character by changing the loop test to a+b form, i.e.:

int i,x[99];for(x[98]=i=1;x+98;)i*=!++x[i++];

The other array references are l-values.

gjm112• 16 years ago

That would need to be *(x+98), which is longer than x[98].

nollidge• 16 years ago

As someone points out in the comments, isn't this true of any NP-complete problem with large enough inputs? This isn't all that surprising then.

bdr• 16 years ago

You can write a finite-but-longer-than-the-universe loop using any non-constant problem with large enough inputs. There are classes harder than NP, so NP-completeness is not particularly relevant.

sukuriant• 16 years ago

As a side note, you're partly assuming in that statement that P != NP, which is yet to be determined in either direction.

sqrt17• 16 years ago

He's not. Any program code written today that solves an NP-hard problem without exploiting special properties of the input data will take exponential time. If we discover a smart way to do NP-hard problems in polynomial time, we'll have a better solution for the problem, but the old program code will stay the same.

If you want an analogy: sorting an array is clearly a task that can be solved in O(n log n) time, but if you write a bubble sort implementation (or any other O(n^2) algorithm), the program will still take O(n^2) time.

SamReidHughes6• 16 years ago

Here's a 43-character solution.

    for(int x[99]={1};!x[98];++*x)*x*=!++x[*x];

SamReidHughes6• 16 years ago

Aha! 42 characters!

    for(int x[99]={1};++x[++*x]?*x=1:!x[98];);

SamReidHughes6• 16 years ago

Aah! 40 characters!

    for(int x[99]={98};++x[*x]?*x=98:--*x;);

jpablo• 16 years ago

Not very interesting post. I could think of teens of problems out of the top of my head that are theoretically finite but there's no enough mass/energy in the universe for them to complete (like generating a program that solves chess).

His first example of "for (int i = 1; i > 0; i++);" Would be matched by some ugly trick like:

int i = 0; while (!i);

That's warranted to halt as the chances for a bit in i to be flipped by cosmic rays tends to be 1 over time.

gjm112• 16 years ago

The "first example" is merely a preliminary; it isn't an example of what he's actually trying to do. He's trying to write a very short program that (1) is valid C, (2) would terminate eventually on a system that perfectly implements C semantics and can run as long as it wants, but (3) would take so long to do so that no physically realisable system within the observable universe could enable it to run to completion.

You are of course welcome to find this uninteresting, but "I can think of lots of big complicated programs that would terminate but not do so for a very long time" and "In the real world, an infinite loop may terminate because of a hardware malfunction" don't seem to me like good reasons for finding it uninteresting.

tkeller• 16 years ago

I was kind of disappointed in this article. He starts off with "It's easy to write a loop which looks infinite but in fact completes quite quickly..." which makes it sound like he's going to write a loop that looks finite but in fact spins forever (maybe because of some trick like the integer overflow he uses at the beginning). That would have been interesting.

This is just trying to write a short program that'll run for a long time. Meh.

Andys• 16 years ago

How long would it take, exactly, to increment a uint128 until it overflows?

The never-ending finite loop

Related Stories