[plt-scheme] recursion and efficiency?!

In data Wed, 21 Apr 2004 14:31:24 -0400, Richard C. Cobbe <cobbe at ccs.neu.edu> ha scritto:

> Right, but you'll have varying number of bignum operations, depending on
> the order in which you do the multiplications.  Of course, in this case,
> I'm not sure how much this matters.  I know 12! fits into a 32-bit
> integer and 13! doesn't, so you won't do that many multiplications
> before you overflow into bignum arithmetic even if you start with the
> smaller numbers and work up.  (You might not even be able to fit 12!
> into a PLT fixnum; I don't remember how large those are, and I'm too
> lazy to go look it up.)

Digression: if one's intent is not to benchmark, but really
one is interested in factorials, a faster way to compute
them is the following:

(define (fact n)
   (if (zero? n)
     1
     (mult 1 n)))

;; from excluded, to included
(define (mult from to)
    (case (- to from)
     (0 1)
     (1 to)
     (else
      (let ((middle (quotient (+ from to) 2)))
        (* (mult from middle) (mult middle to))))))

It is a well known trick, but if one doesn't know it yet
it is worth one's time to understand why it is faster doing
the multiplications in this order, rather than in
one ascending or descending sweep.

Recursive wins, after all!

Cheers
P.