Building Abstractions with Data - Introduction to Data Abstraction - Extended Exercise: Interval Arithmetic - width of an interval, addiction, multiplication, division

Structure and Interpretation of Computer Programs: JavaScript Edition
楽天ブックス

開発環境

Structure and Interpretation of Computer Programs: JavaScript Edition(Harold Abelson(著)、Gerald Jay Sussman(著)、Julie Sussman(著)、The MIT Press)のChapter 2(Building Abstractions with Data)、2.1(Introduction to Data Abstraction)、2.1.4(Extended Exercise: Interval Arithmetic)、Exercise 2.9の解答を求めてみる。

和について。

x1、x2を任意のintervalとする。

x1のwidthとx2のwidthの和。

(x1_upper-x1_lower) / 2 + (x2_upper-x2_lower) / 2
((x1_upper + x2_upper) - (x1_lower+x2_lower)) / 2

これはx1とx2の和のwidthと等しい。

積について。

x=[1, 3], y=[1, 5]

に対して、xのwidthは

(3-1)/2=1

yのwidthは

(5-1)/2=2

xのwidthとyのwidthの積は2。

xとyの積をzとすると、

z=[1, 15]

でzのwidthは

(15-1)/2=7

よって、widthの積と積のwidthは異なる。

除算について。

x、yは積の場合と同様とする。

x_width/y_width=1/2

x/y=[1, 3] * [1/5, 1]=[1/5, 3]

このwidthは

(3-1/5)/2=7/5

実際にプログラムを実行してみる。

コード

function pair(x, y) {
    return [x, y];
}
function head(z) {
    return z[0];
}
function tail(z) {
    return z[1];
}
function half(x) {
    return x / 2;
}
function make_interval(x, y) {
    return pair(x, y);
}
function upper_bound(interval) {
    return tail(interval);
}
function lower_bound(interval) {
    return head(interval);
}
function width_interval(interval) {
    return half(upper_bound(interval) - lower_bound(interval));
}
function add_interval(x, y) {
    return make_interval(
        lower_bound(x) + lower_bound(y),
        upper_bound(x) + upper_bound(y)
    )
}
function mul_interval(x, y) {
    const p1 = lower_bound(x) * lower_bound(y);
    const p2 = lower_bound(x) * upper_bound(y);
    const p3 = upper_bound(x) * lower_bound(y);
    const p4 = upper_bound(x) * upper_bound(y);
    return make_interval(
        Math.min(p1, p2, p3, p4),
        Math.max(p1, p2, p3, p4)
    );
}
function div_interval(x, y) {
    return mul_interval(
        x,
        make_interval(
            1 / upper_bound(y),
            1 / lower_bound(y)
        )
    )
}

const x = make_interval(1, 3);
const y = make_interval(1, 5);
const x_width = width_interval(x);
const y_width = width_interval(y);

console.log(`x = ${x}, y= ${y}`)
console.log(`x_width = ${x_width}, y_width = ${y_width}`);
console.log('addition');
console.log(`${x_width + y_width}, ${width_interval(add_interval(x, y))}`);
console.log('multiplication');
console.log(`${x_width * y_width}, ${width_interval(mul_interval(x, y))}`);
console.log('division');
console.log(`${x_width / y_width}, ${width_interval(div_interval(x, y))}`);

入出力結果(Terminal, Zsh)

% node answer2.9.js
x = 1,3, y= 1,5
x_width = 1, y_width = 2
addition
3, 3
multiplication
2, 7
division
0.5, 1.4
%