Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!wuarchive!usc!snorkelwacker.mit.edu!ai-lab!just-right!misha
From: misha@just-right.ai.mit.edu (Mike Bolotski)
Newsgroups: comp.lang.misc
Subject: Re: Array references cannot be made optimal
Message-ID: <11897@life.ai.mit.edu>
Date: 15 Nov 90 20:47:50 GMT
References: <13350:Nov1419:44:2790@kramden.acf.nyu.edu> <GESSEL.90Nov14165831@carthage.cs.swarthmore.edu> <5785:Nov1519:19:5390@kramden.acf.nyu.edu>
Sender: news@ai.mit.edu
Organization: MIT Artificial Intelligence Laboratory
Lines: 42

In article <5785:Nov1519:19:5390@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes:
>If you have a program with a set of variables that enter a loop at time
>t, and continue to loop in a cycle of length l, then the method outlined
>will run the program in twice the memory at one-third speed minus
>housekeeping, and detect the loop between t and t + l, i.e., during its
>first cycle.

That's fine, Dan. What if the cycle length is several millenia?

It's not hard to write a simple program that uses say, 256-bit
integers which accomplishes that.  Your "solution" is hardly practical.

And here's a quick test for your solution:

int foo(x)
int256 x;
{
  while (x != 1) 
    if (even(x))  x = x / 2;
        else x = x * 3 + 1;       
  return 1;
}

>the worst case it'll still detect the loop eventually, though I don't
>think these theoretical statements matter for the real world.

The real world being defined as your experience alone, is it?

>See, this is what I mean about computer scientists. The computational
>model I work with is realistic---it's just my mental picture of what can
>be coded on lots of real machines. As I said before, it's finite. It has

No need to apologize for your limitations, Dan.







Mike Bolotski          Artificial Intelligence Laboratory, MIT
misha@ai.mit.edu       Cambridge, MA