Chapter 3.1.2 Exercise 3.5 Solution

[Zxun2]

Solution for Exercise 3.5

Noticed no solution is available for this exercise so I decided to contribute. Thanks!
Also, the solution seems to converge on the value 3. I wonder if this is intentional?

Link to exercise: https://sourceacademy.nus.edu.sg/sicpjs/3.1.2

function random(n) {
    return math_floor(math_random() * n);
}

function random_in_range(low, high) {
    const range = high - low;
    return low + random(range);
}

function square(x){
    return x*x;
}

function inside_circle(x, y, mid, rad){
    return (square(x - head(mid)) + 
        square(y - tail(mid))) <= square(rad);
}

function estimate_integral(pred, x1, x2, y1, y2, trials) {
    const area_rect = (x2 - x1) * (y2 - y1);
    // monte-carlo
    function monte(trials_remaining, trials_passed){
        // Generate random coord  
        const x_coord = random_in_range(x1, x2);
        const y_coord = random_in_range(y1, y2);
        
        return trials_remaining === 0
            ? ( trials_passed / trials)  * area_rect
            : pred(x_coord, y_coord, mid_point, radius_cir)
                ? monte(trials_remaining - 1, trials_passed + 1)
                : monte(trials_remaining - 1, trials_passed);
    }
    return monte(trials, 0) / square(radius_cir);
}

// test cases
const radius_cir = 3;
const mid_point = pair(3, 7);

estimate_integral(inside_circle, head(mid_point) - radius_cir, 
    head(mid_point) + radius_cir, tail(mid_point) - radius_cir, 
        tail(mid_point) + radius_cir, 10000);

[ngxingyu]

I believe pred should be a function taking in x and y and returning a boolean, and estimate_integral should return the area of the region instead of pi.

// SICP JS 3.1.2

const square = x => x * x;
function inside_circle(x, y, r) {
    return (x1, y1) => square(x1 - x) + square(y1 - y) <= square(r);
}

/* function estimate_integral(pred, x1, x2, y1, y2, trials) {
    const area_rect = (x2 - x1) * (y2 - y1);
    function monte(trials_remaining, trials_passed) {
        const x_coord = random_in_range(x1, x2);
        const y_coord = random_in_range(y1, y2);
        return trials_remaining === 0
               ? trials_passed / trials * area_rect
               : pred(x_coord, y_coord)
               ? monte(trials_remaining - 1, trials_passed + 1)
               : monte(trials_remaining - 1, trials_passed);
    }
    return monte(trials, 0);
} */
function estimate_integral(pred, x1, x2, y1, y2, trials) {
    const area_rect = (x2 - x1) * (y2 - y1);
    return monte_carlo(trials,
                       () => pred(random_in_range(x1, x2),
                                  random_in_range(y1, y2))) * area_rect;
}
const r = 10;
const x = 5;
const y = 7;
estimate_integral(inside_circle(x, y, r),
                  x - r,
                  x + r,
                  y - r,
                  y + r,
                  5000) / square(r);

[Zxun2]

Thanks, xing yu!

I believe pred should be a function taking in x and y and returning a boolean, and estimate_integral should return the area of the region instead of pi.

// SICP JS 3.1.2

const square = x => x * x;
function inside_circle(x, y, r) {
    return (x1, y1) => square(x1 - x) + square(y1 - y) <= square(r);
}

function estimate_integral(pred, x1, x2, y1, y2, trials) {
    const area_rect = (x2 - x1) * (y2 - y1);
    function monte(trials_remaining, trials_passed) {
        const x_coord = random_in_range(x1, x2);
        const y_coord = random_in_range(y1, y2);
        return trials_remaining === 0
               ? trials_passed / trials * area_rect
               : pred(x_coord, y_coord)
               ? monte(trials_remaining - 1, trials_passed + 1)
               : monte(trials_remaining - 1, trials_passed);
    }
    return monte(trials, 0);
}
const r = 10;
const x = 5;
const y = 7;
estimate_integral(inside_circle(x, y, r),
                  x - r,
                  x + r,
                  y - r,
                  y + r,
                  5000) / square(r);

[martin-henz]

And regarding the question why the result is approaching 3 instead of pi: You are using the wrong random function. What you used is probably this one:

function random(n) {
    return math_floor(math_random() * n);
}

which is given in one of the solutions in 1.2.6, which returns an integer. If you define random_in_range as given in the exercise, using the random function above:

function random_in_range(low, high) {
    const range = high - low;
    return low + random(range);
}

a call of random_in_range(-1, 1) for the unit circle will give you either -1 or 0. With that, you will get a convergence to 3.

[martin-henz]

So this is clearly a bug in this exercise: There is no function random in 1.2.6. It should instead say:

The following random_in_range function implements this in terms of the math_random function used in section 1.2.6, which returns a nonnegative number less than 1.

function random_in_range(low, high) { 
    const range = high - low;
    return low + math_random() * range;
}