[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

optimising factorial

dorai@titan.rice.edu (Dorai Sitaram) writes:
(about optimising a recursive defintion of factorial)

>
> ....I wouldn't want the compiler to perform this
> optimization, for if you unwind the *-calls, you'll find the
> non-tail-rec version does (* n (* n-1 (* n-2 ... 1))), while the
> tail-rec one does (* 1 (* 2 (* 3 ... (* n 1)))).  The optimization
> hinges too much on the commutativity of * for my comfort.
>

This can be surprisingly important if at some point "big" integers
are created (e.g. factorial 1000). If you start the multiplication
 from the top down i.e. (* 1 (* 2 (* 3 ... (* n 1)))) then more big
integers are created than if it is done the other way,
    (* n (* n-1 (* n-2 ... 1)))

Unless your compiler is clever about re-using temporary results of
mutiplications etc, the former can spend significantly more time in
garbage collection.

Aaron Sloman,
School of Cognitive and Computing Sciences,
Univ of Sussex, Brighton, BN1 9QH, England
    EMAIL   aarons@cogs.sussex.ac.uk
            aarons%uk.ac.sussex.cogs@nsfnet-relay.ac.uk