CODEWITHSUNDEEP
schemelispsicp
volatile
volatile

Reputation: 949

Scheme : recursive process much faster than iterative

I am studying SICP and wrote two procedures to compute the sum of 1/n^2, the first generating a recursive process and the second generating an iterative process :

(define (sum-rec a b)
  (if (> a b)
      0
      (exact->inexact (+ (/ 1 (* a a)) (sum-rec (1+ a) b)))))

(define (sum-it a b)
  (define (sum_iter a tot)
    (if (> a b)
        tot
        (sum_iter (1+ a) (+ (/ 1 (* a a)) tot))))
  (exact->inexact (sum_iter a 0)))

I tested that both procedures give exactly the same results when called with small values of b, and that the result is approaching $pi^2/6$ as b gets larger, as expected.

But surprisingly, calling (sum-rec 1 250000) is almost instantaneous whereas calling (sum-it 1 250000) takes forever.

Is there an explanation for that?

Upvotes: 2

Views: 95

Answers (2)

user5920214
user5920214

Reputation:

You can reframe both of these versions so that they do exact or inexact arithmetic appropriately, simply by controlling what value they use for zero and relying on the contagion rules. These two are in Racket, which doesn't have 1+ by default but does have a nice syntax for optional arguments with defaults:

(define (sum-rec low high (zero 0.0))
  (let recurse ([i low])
    (if (> i high)
      zero
      (+ (/ 1 (* i i)) (recurse (+ i 1))))))

(define (sum-iter low high (zero 0.0))
  (let iterate ([i low] [accum zero])
    (if (> i high)
        accum
        (iterate (+ i 1) (+ (/ 1 (* i i)) accum)))))

The advantage of this is you can see the performance difference easily for both versions. The disadvantage is that you'd need a really smart compiler to be able to optimize the numerical operations here (I think, even if it knew low and high were machine integers, it would have to infer that zero is going to be some numerical type and generate copies of the function body for all the possible types).

Upvotes: 0

Óscar López
Óscar López

Reputation: 236004

As was mentioned in the comments, sum-it in its present form is adding numbers using exact arithmetic, which is slower than the inexact arithmetic being used in sum-rec. To do an equivalent comparison, this is how you should implement it:

(define (sum-it a b)
  (define (sum_iter a tot)
    (if (> a b)
        tot
        (sum_iter (1+ a) (+ (/ 1.0 (* a a)) tot))))
  (sum_iter a 0))

Notice that replacing the 1 with a 1.0 forces the interpreter to use inexact arithmetic. Now this will return immediately:

(sum-it 1 250000)
=> 1.6449300668562465

Upvotes: 5

Related Questions