5 ms·
The never-ending finite loop
- btilly 16y agoI 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 16y agoyour "improved" version illegally modifies 'i' twice in the same statement; its results are undefined.
- btilly 16y agoYou 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];
- SamReidHughes 16y agoThat's still not unambiguous. Turn -Wall on and you'll be told the operation on 'i' may be undefined.
- jemfinch 16y ago> But there are two outcomes I think are likely. It's undefined behavior. Any outcome is likely. The compiler could halt your program immediately if it wanted to, and that's just as likely as either of the cases you offer.
- nburger 16y agoAnd 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.
- nollidge 16y agoAs 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 16y agoYou 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 16y agoAs a side note, you're partly assuming in that statement that P != NP, which is yet to be determined in either direction.
- sqrt17 16y agoHe'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.
- swolchok 16y agoRight conclusion, not the most direct argument. NP is a proper subset of EXPTIME; there are problems that must take exponential time to complete. Wikipedia says that asking whether a Turing-machine halts in k steps is EXPTIME-complete (you have to execute k steps and the input is of size log k), but if you're willing to fudge a bit and consider function problems, listing all paths in a graph (or something even simpler, like "list all n-bit binary numbers")is going to take exponential time in the worst case.
- SamReidHughes 16y ago
- SamReidHughes 16y agoHere's a 43-character solution. for(int x[99]={1};!x[98];++*x)*x*=!++x[*x];
- SamReidHughes 16y agoAha! 42 characters! for(int x[99]={1};++x[++*x]?*x=1:!x[98];);
- SamReidHughes 16y agoAah! 40 characters! for(int x[99]={98};++x[*x]?*x=98:--*x;);
- SamReidHughes 16y agoSigh. 39 characters! for(int x[99]={1};++x[*x]?*x=98:--*x;);
- jpablo 16y agoNot 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.
- gjm11 16y agoThe "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 16y agoI 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 16y agoHow long would it take, exactly, to increment a uint128 until it overflows?