2

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?

Improve this question
2
  • 6
    The two are not equivalent – sum_iter uses exact arithmetic; sum-rec doesn't. Commented Aug 18, 2019 at 11:30
  • which means that there will be lots of calculations with bignums, which is expensive Commented Aug 19, 2019 at 13:40

2 Answers 2

Reset to default
5

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
Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

0

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).

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.