Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!yale!cmcl2!kramden.acf.nyu.edu!brnstnd From: brnstnd@kramden.acf.nyu.edu (Dan Bernstein) Newsgroups: comp.lang.misc Subject: Re: Array references cannot be made optimal Message-ID: <3289:Nov1323:05:4790@kramden.acf.nyu.edu> Date: 13 Nov 90 23:05:47 GMT References: <23904:Nov905:22:5290@kramden.acf.nyu.edu> <11839@life.ai.mit.edu> Organization: IR Lines: 104 There does not exist an algorithm that will convert an (optimal) array program into its optimal pointer form. That summarizes what I've said so far in this thread. What does it mean for real languages? It means that the programmer *must* be allowed to look at an array x from the vantage point of x[a], rather than x[0]. This array shifting doesn't have to look like C's pointer arithmetic, even if it is implemented that way in machine language, and even if it's doing no more than providing pointer arithmetic with a different syntax. It just has to be there. Once you have array shifting, finding the optimal pointer form is rather easy, as Jim has been saying. I don't know of any efficiency advantages of pointers in that case. In article <11839@life.ai.mit.edu> misha@ai.mit.edu writes: > "Finding an optimal assignment of registers to variables is difficult, > even with single-register values. Mathematically, the problem is > NP-complete." I am not talking about finding an optimal assignment of registers to variables, so even if I were to blindly believe this statement, I'd stick to my position. > "The order in which computations are performed can affect the > efficiency of the target code. [..] Picking a best order is > another difficult, NP-complete problem." (p 518). See above. Don't fall into the trap of misinterpreting AHU's statement. Only a very limited class of optimizations may be performed by computer. The general problem of finding the best way to compute something isn't just NP: it's undecidable. An example of a decidable problem: Find the fastest way to compute x^n, for a single exponent n. This is the simple addition chain problem. An example of a problem not yet proven either decidable or undecidable: Find the optimal way to compute x^n, for a given range of exponents n, under a certain computational model, where ``optimal'' means optimal in a weighted average of run time and program space. It's highly likely that a computer can't solve this, but you never know. If you see the difference between these two problems, you'll appreciate what AHU are saying. > |> Outline of proof: [ ... ] > The above is not a proof. It is not even close to a proof. How observant you are. I called it an ``outline'' for a reason. In the article before this, I went through an informal proof. > In fact, > I suspect you have the common misconception that the halting problem > consists of determining whether a particular program will ever halt > or not. In fact, I suspect you have not been on the net long enough to know any better. Or were you not reading comp.theory in January 1989? See my next article. > [ Timer description deleted due to irrelevance ]. > |> Q.E.D. > Right. I'm disgusted by your lack of appreciation for the value of constructive criticism in modern science. If you see something I've missed, point to it! (Or index it! :-) ) I just don't see how you plan to figure out whether you should keep a pointer to x[0] and use that to get x[1], or whether the opposite order is better. > |> Indeed. (As a matter of fact, it's quite feasible to solve the halting > |> problem in practice---the algorithm just depends on the program.) > If this statement was made with full knowledge of what the halting > problem is, it would have been a wonderful .sig quote. Feel free to put it in your .sig---after you understand what I say in my next article. > |> I simply don't understand where you and Mike are getting this ridiculous > |> assertions from. What problems are you fantasizing you've solved here? > |> Where are your purported proofs? > The louder you yell your mistakes, Dan, the more embarassing they become. But you haven't pointed out a single mistake! *You* just implied that it is not feasible to solve the halting problem in practice. As anyone who reads my next article will realize, you are wrong. There. I've now pointed out an error (or at least implied error) of yours. Can you make the effort to follow the same format if you really do see a mistake in what I post? Or are my suspicions correct, and you haven't, in fact, seen any error? > Especially since you are venturing out of the safe realm of opinion and > dealing with facts that can be proven mathematically. No shit. That's one of the things that you learn to do when you're trained as a mathematician. ---Dan