Re: What's the best language to start with? [was: Re: Should I learn C or Pascal?]

[ok@goanna.cs.rmit.edu.au (Richard A. O'Keefe)]

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.