From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.3 required=5.0 tests=BAYES_00,INVALID_MSGID autolearn=no autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: fc89c,97188312486d4578 X-Google-Attributes: gidfc89c,public X-Google-Thread: 109fba,baaf5f793d03d420 X-Google-Attributes: gid109fba,public X-Google-Thread: 1014db,6154de2e240de72a X-Google-Attributes: gid1014db,public X-Google-Thread: 103376,97188312486d4578 X-Google-Attributes: gid103376,public From: ok@goanna.cs.rmit.edu.au (Richard A. O'Keefe) Subject: Re: What's the best language to start with? [was: Re: Should I learn C or Pascal?] Date: 1996/08/14 Message-ID: <4urqam$r9u@goanna.cs.rmit.edu.au>#1/1 X-Deja-AN: 174727918 references: <31FBC584.4188@ivic.qc.ca> <01bb83f5$923391e0$87ee6fce@timpent.airshields.com> <4uah1k$b2o@solutions.solon.com> <01bb853b$ca4c8e00$87ee6fce@timpent.airshields.com> <4udb2o$7io@solutions.solon.com> <01bb8569$9910dca0$87ee6fce@timpent.airshields.com> organization: Comp Sci, RMIT, Melbourne, Australia newsgroups: comp.lang.c,comp.lang.c++,comp.unix.programmer,comp.lang.ada nntp-posting-user: ok Date: 1996-08-14T00:00:00+00:00 List-Id: Recursive gcd: int gcd(int x, int y) { if (y == 0) return x; return gcd(y, x%y); } Iterative gcd: int gcd(int x, int y) { int z; while (y != 0) z = y, y = x%y, x = z; return y; } Peter Seebach wrote that the compiler he uses would generate the equivalent of the iterative code from the recursive source. "Tim Behrendsen" asked incredulously >Which compiler is that? I would like to see the compiler that >unravels recursion into non-recursive algorithms. GCC 2.7.2 will do it. So will SPARCompiler C 4.0. (I mention those versions because they are the versions I have.) So will any even half-way decent Lisp or Scheme compiler. >It has *everthing* to do with algorithms. You showed me a recursive >algorithm, I rewrote it to be faster. The fact that in this case >it's only 10% is irrelevent Actually, it isn't irrelevant. The speed up is only a by a constant factor, and all it tells you is that you are using a compiler that does a really bad job of compiling function calls. Any effort spent speeding up this version of gcd is wasted, because GCD can be implemented to have the same cost as division. On a machine like a V7 SPARC, where there was no division instruction, a well-written formally recursive gcd could be as fast as a single x%y. >for another algorithm it could have >been much more (compare recursive v.s. non-recursive quicksort). >I consider a recursive solution to be a different algorithm than a >non-recursive one, although I realize that is arguably an >implementation issue. This is a lot like calling a procedure that uses an 'if (...) goto' a different *algorithm* from the same procedure expressed using 'while'. We have known since the 70s how to compile tail calls into jumps, and since the late 70s at least have had a substantial body of theory about how to automatically translate many uses of recursion into iteration at the implementation level. Turning tail calls into jumps is the very simplest of these techniques. (And yes, the loop thus uncovered can of course be unrolled, just like any other loop.) If you encounter any significant difference in speed between recursive and non-recursive quicksort, all that tells you is that it is time to change compilers. Come to that, if you really cared about speed you wouldn't be using quicksort anyway. >If I implemented Quicksort in APL, say (which has direct >manipulation of arrays in one operation), Given the grade-up primitive, I can't think why anybody would _want_ to implement quicksort in APL. >the student would >not see the movement, because they would just see the computer >doing the array "in one fell swoop", but wouldn't really >experience the fact that the computer doesn't really do it >that way in reality. Interestingly enough, the APL sorting primitive DOESN'T move the data at all. It returns a permutation vector. The APL idiom for sorting is X[.GradeUP X] where the necessary movement is quite visible. -- Fifty years of programming language research, and we end up with C++ ??? Richard A. O'Keefe; http://www.cs.rmit.edu.au/~ok; RMIT Comp.Sci.