two methods of composing functions, how different in efficiency?

Question

Hi,

Let f transform one value to another, then I'm writing a function that repeats the transformation n times.

I have come up with two different ways:

• One is the obvious way that literally applies the function n times, so repeat(f, 4) means x → f(f(f(f(x))))
• The other way is inspired from the fast method for powering, which means dividing the problem into two problems that are half as large whenever n is even. So repeat(f, 4) means x → g(g(x)) where g(x) = f(f(x))

At first I thought the second method wouldn't improve efficiency that much. At the end of the day, we would still need to apply f n times, wouldn't we? In the above example, g would still be translated into f o f without any further simplification, right?

However, when I tried out the methods, the latter method was noticeable faster.

;; computes the composite of two functions
(define (compose f g)
  (lambda (x) (f (g x))))

;; identify function
(define (id x) x)

;; repeats the application of a function, naive way
(define (repeat1 f n)
  (define (iter k acc)
    (if (= k 0)
        acc
        (iter (- k 1) (compose f acc))))
  (iter n id))

;; repeats the application of a function, divide n conquer way
(define (repeat2 f n)
  (define (iter f k acc)
    (cond ((= k 0) acc)
          ((even? k) (iter (compose f f) (/ k 2) acc))
          (else (iter f (- k 1) (compose f acc)))))
  (iter f n id))

;; increment function used for testing
(define (inc x) (+ x 1))

In fact, ((repeat2 inc 1000000) 0) was much faster than ((repeat1 inc 1000000) 0). My question is in what aspect was the second method more efficient than the first? Did re-using the same function object preserves storage and reduces the time spent for creating new objects?

After all, the application has to be repeated n times, or saying it another way, x→((x+1)+1) cannot be automatically reduced to x→(x+2), right?

I'm running on DrScheme 4.2.1.

Thank you very much.

Answer 1

You're right that both versions do the same number of calls to inc -- but there's more overhead than that in your code. Specifically, the first version creates N closures, whereas the second one creates only log(N) closures -- and if the closure creation is most of the work then you'll see a big difference in performance.

There are three things that you can use to see this in more details:

1. Use DrScheme's time special form to measure the speed. In addition to the time that it took to perform some computation, it will also tell you how much time was spent in GC. You will see that the first version is doing some GC work, while the second doesn't. (Well, it does, but it's so little, that it will probably not show.)

2. Your inc function is doing so little, that you're measuring only the looping overhead. For example, when I use this bad version:

   (define (slow-inc x)
     (define (plus1 x)
       (/ (if (< (random 10) 5)
            (* (+ x 1) 2)
            (+ (* x 2) 2))
          2))
     (- (plus1 (plus1 (plus1 x))) 2))
   

   the difference between the two uses drops from a factor of ~11 to 1.6.

3. Finally, try this version out:

   (define (repeat3 f n)
     (lambda (x)
       (define (iter n x)
         (if (zero? n) x (iter (sub1 n) (f x))))
       (iter n x)))
   

   It doesn't do any compositions, and it works in roughly the same speed as your second version.

Answer 2

The first method essentially applies the function n times, thus it is O(n). But the second method is not actually applying the function n times. Every time repeat2 is called it splits n by 2 whenever n is even. Thus much of the time the size of the problem is halved rather than merely decreasing by 1. This gives an overall runtime of O(log(n)).

As Martinho Fernandez suggested, the wikipedia article on exponentiation by squaring explains it very clearly.