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.9 required=5.0 tests=BAYES_00 autolearn=ham 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: 103376,97188312486d4578 X-Google-Attributes: gid103376,public X-Google-Thread: 1014db,6154de2e240de72a X-Google-Attributes: gid1014db,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/15 Message-ID: <4uu97a$gpb@goanna.cs.rmit.edu.au> X-Deja-AN: 174639563 references: <31FBC584.4188@ivic.qc.ca> <01bb83ad$29c3cfa0$87ee6fce@timpent.airshields.com> <4u89c4$p7p@solutions.solon.com> <01bb83f5$923391e0$87ee6fce@timpent.airshields.com> <4uah1k$b2o@solutions.solon.com> <01bb853b$ca4c8e00$87ee6fce@timpent.airshields.com> <320b35a2.43769707@nntp.ix.netcom.com> <01bb8609$59339140$87ee6fce@timpent.airshields.com> <320bf032.7193774@nntp.ix.netcom.com> <01bb8802$a5ff3a60$32ee6fce@timhome2> <320f14e5.213196860@nntp.ix.netcom.com> <4uo4b8$ug0@excessus.demon.co.uk> 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-15T00:00:00+00:00 List-Id: mdw@excessus.demon.co.uk (Mark Wooding) writes: >Are we talking about implementing it the truly stupid way as a single >function, e.g., > (define (factorial n) > (if (zero? n) > 1 > (* n (factorial (- n 1))))) >or properly using another function which tail-recurses, e.g., >If the former, then please report for re-education; Ahem. (a) We have known at least since Burstall and Darlington's work in the 70s how to AUTOMATICALLY turn this kind of recursion into iteration. F(x) = if P(x) then T(x) else H(G(x), F(R(x))) under certain conditions on G and H. The only thing that prevents most Scheme compilers doing it is that they can't be sure that you won't assign something different to * or - at run time; a compiler that prevents you changing the primitives or that analyses the whole program and finds that you _don't_ change them could quite easily transform this function to iterative form. Doing it when H and G are user-defined is harder. (b) In a Scheme system supporting the full numeric tower; this will spend much more time chomping away at bignum arithmetic thanit will on its own procedure calls. To reduce that cost, you need to unroll, which can be done every bit as easily with the recursive form as the iterative: [substitute value of factorial] => (define (factorial n) (if (zero? n) 1 (* n ((lambda (n) (if (zero? n) 1 (* n (factorial (- n 1))) )) (- n 1)) ))) [Substitute actual parameter for formal in inner lambda] => (define (factorial n) (if (zero? n) 1 (* n (if (zero? (- n 1)) 1 (* (- n 1) (factorial (- (- n 1) 1)) )) ))) [Simplify arithmetic forms and distribute * over if] (define (factorial n) (if (= n 0) 1 (if (= n 1) 1 ; was (* n 1) but we know n=1 (* n (* (- n 1)) (factorial (- n 2)) )) )) [Reassociate multiplication to get (* (* fixnum fixnum) bignum) instead of (* fixnum (* fixnum bignum)); rewrite if as case for readability] => (define (factorial n) (case n ((0 1) 1) (else (* (* n (- n 1)) (factorial (- n 2)) )) )) Some measurements, using Gambit 2.2.2 on a Manintosh Centris 660AV. All times are in seconds to compute 100! recursive, naive: 0.21 sec recursive, unrolled: 0.11 sec iterative, naive: 0.25 sec (yes, SLOWER than the recursive one!) iterative, unrolled: 0.14 sec (yes, SLOWER than the recursive one!) The iterative versions were not tail recursifve; they used Scheme's direct equivalent of a while loop. For example, the iterative, naive version was (define (f3 n) (do ((f 1 (* i f)) (i n (- i 1))) ((<= i 1) f))) We see in this case that anyone who was sent for "re-education" learned something false: in this compiler on this machine, factorial coded as naive recursion is FASTER than factorial coded as a while loop. (Actually, the real reason is the order in which the multiplications are done. The recursive version does ((((1*2)*3)*4)* ... n) which keeps the intermediate values small as long as possible, while the iterative version does (1* ... *(n-2 * (n-1 * n))) which overflows into bignum arithmetic earlier.) We also see something I first noticed when testing some bignum code in C a couple of years back: replacing iteration by recursion or vice versa may save or cost you 10--20%, but unrolling the loop HALVES the work. It would be foolish indeed to spend your time turning recursion into iteration in order to buy a 10% speedup (or with this compiler on this machine, in order to by a 20% slowdown!) when you could have spent the same time unrolling to get a 50% reduction in time. The point at issue here is that the use of recursion instead of iteration is fully consistent with the "loop unrolling" compiler optimisation technique, no less so than iteration. Another point is that _scheduling the order in which operations are performed_ may have a bigger effect than the control framework defining that order. (The matrix product problem is a well known example of this; other examples include merging several lists, operating on several sets, &c). (I cannot perform this measurement in the current top-of-the-line Scheme compiler, Stalin, because Stalin doesn't support bignum arithmetic.) (c) What if you haven't got bignum arithmetic? Then turning recursion into iteration won't help with the major problem with factorial, which is that 13! = 6227020800 > 4294967295 == 2**32 - 1 > 2147483647 = 2**31 - 1 so trying to compute factorials in fixnum (C: int, Ada: Integer) arithmetic isn't going to get you very far. You can do exact integer addition, subtraction, comparison, and multiplication with IEEE doubles up to 2**53 - 1, which sounds like a lot, but 19! = 121645100408832000 > 9007199254740991 = 2**53 - 1 so even flonum (C: double, Ada: Long_Float) arithmetic won't get you very far with factorials. If you seriously want to compute factorials in a language without bignum arithmetic, what you _really_ want to compute is the gamma function, which requires completely different techniques and skills. What has this got to to with recursion -vs- iteration? Well, under a minute typing the naive recursive definition, followed by (let loop ((x (- (expt 2 31) 1)) (i 1)) (if (> (factorial i) x) i (loop x (+ i 1)))) let me find out how far I could compute factorials using C or Ada without a bignum package. Any time spent optimising the function for use (as opposed to optimising it for debate, which is what I've been doing) would have been wasted, because it doesn't matter _how_ you compute the function, the results are too big. What matters here, then, is how long it takes you to find this out. If the recursive definition gets *you* to *understanding* quicker, it's a winner. -- Australian citizen since 14 August 1996. *Now* I can vote the xxxs out! Richard A. O'Keefe; http://www.cs.rmit.edu.au/~ok; RMIT Comp.Sci.