2
\$\begingroup\$

From SICP

The sum procedure is only the simplest of a vast number of similar abstractions that can be captured as higher-order procedures. Write an analagous procedure called product that returns the product of the values of a function at points over a given range.

...

"Also use product to compute approximations to pi using the formula
pi/4 = 2*4*4*6*6*8*.../3*3*5*5*7*7*...

Here is a procedure called product:

(define (product term a next b)
  (if (> a b)
      1
      (* (term a) (product term (next a) next b))))

I have made two solutions:

Here is the first solution. This one navigates through the series by a period of 2 (E.G. if n is 1, it will evaluate 2*4/3*3). I did this because I wanted to find a pattern from the series and what I got was 2*4 and 4*6 and 6*8, and the denominators 3*3 and 5*5 and 7*7.

(define (pi-product2 n)
    (define (inc x) (+ x 1))
    (define (numer-term x)
      (* (* 2.0 x)
         (+ (* 2.0 x)
            2.0)))
    (define (denom-term x)
      (square (+
               (* 2.0 x)
               1.0)))
    (define (term x)
      (/ (numer-term x) (denom-term x)))
    (product term 1.0 inc n))

Here is my second solution. I just recently thought of how to evaluate them by each term (E.G. if n is 1, it will evaluate 2/3).

  (define (pi-product n)
    (define (inc x) (+ x 1))
    (define (term x)
      (if (even? x)
          (/ (+ x 2.0) (+ x 1.0))
          (/ (+ x 1.0) (+ x 2.0))))
    (product term 1.0 inc n))
  • Is my first solution still a correct representation of the formula even if it evaluates two terms on each approximation? Or is it the first solution with the correct representation?
  • I would think my first solution, though very ugly, is at least as twice as fast as the second solution. Is that right? Is the performance difference huge?

Whitch of my two solution is better? How can I improve them?

\$\endgroup\$
  • 1
    \$\begingroup\$ What makes you think the first is at least twice as fast as the second? Have you tested? Also, the answer to the first question seems easy enough to answer by running a few values and comparing the results. \$\endgroup\$ – Nathan Davis Dec 1 '16 at 18:58
1
\$\begingroup\$

Is my first solution still a correct representation of the formula even if it evaluates two terms on each approximation? Or is it the first solution with the correct representation?

Although both solutions may be mathematically equivalent in theory, they are vastly different in practice. The first uses floating-point constants, which leads to inexact math. The second one uses exact math.

How can I improve them?

In general, you should avoid using recursion directly when there are higher-level abstractions that fit. For example, here are some ways you could restructure your code around streams:

  • Generate one stream for terms in the numerator and one stream for terms in the denominator. Then use stream-map to divide successive terms. Take the first n terms of the result, and reduce with +.
  • Produce a stream of successive approximations of \$π\$. There are several ways to do this. For example, you could use cons-stream, but it would also be possible (if you define a few auxiliary functions) to tweak the strategy outlined in the preceding point. Then take the nth item of this stream.
\$\endgroup\$
  • \$\begingroup\$ What happens if I remove all the floating-point constants and convert them to integers? Would both solutions be the same? Are they any different? By the way, I converting both my solutions to floating points before your answer appeared... \$\endgroup\$ – morbidCode Dec 2 '16 at 2:34
  • \$\begingroup\$ I would avoid float point math in this case. Floating-point numbers are limited in precision, and arithmetic operations on them are inexact. If you're using floating-point, you'd be better off just finding the closest floating point number to \$π\$ and defining pi to be than constant. But if you use rational numbers, you can find \$π\$ to arbitrary precision. \$\endgroup\$ – Nathan Davis Dec 9 '16 at 23:31
  • \$\begingroup\$ so assuming I remove all the floating points and convert them to rational numbers. Will my two solutions be any different? \$\endgroup\$ – morbidCode Dec 10 '16 at 3:59
  • \$\begingroup\$ I don't know. You could try them and compare the results you get. \$\endgroup\$ – Nathan Davis Dec 10 '16 at 4:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.