計算機科学のブログ

Building Abstractions with Data - Introduction to Data Abstraction - Extended Exercise: Interval Arithmetic - signs of the endpoints

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.11解答を求めてみる。

コード

function display(x) {
    return console.log(x);
}
function error(x) {
    display(x);
    return -1;
}
function math_min(...args) {
    return Math.min(...args);
}
function math_max(...args) {
    return Math.max(...args);
}
function pair(x, y) {
    return [x, y];
}
function head(z) {
    return z[0];
}
function tail(z) {
    return z[1];
}
function make_interval(x, y) {
    return pair(x, y);
}
function lower_bound(interval) {
    return head(interval);
}
function upper_bound(interval) {
    return tail(interval);
}
function mul_interval(x, y) {
    const xl = lower_bound(x);
    const xu = upper_bound(x);
    const yl = lower_bound(y);
    const yu = upper_bound(y);
    if (xl < 0) {
        if (xu < 0) {
            if (yl < 0) {
                // [-, -], [-, -]
                if (yu < 0) {
                    return make_interval(xu * yu, xl * yl);
                }
                // [-, -], [-, +]
                return make_interval(xl * yu, xl * yl);
            }
            // [-, -], [+, +]
            return make_interval(xl * yu, xu * yl);
        }
        if (yl < 0) {
            // [-, +], [-, -]
            if (yu < 0) {
                return make_interval(xu * yl, xl * yl);
            }
            // [-, +], [-, +]
            const p1 = xl * yu;
            const p2 = xu * yl;
            const p3 = xl * yl;
            const p4 = xu * yu;
            return make_interval(
                math_min(p1, p2),
                math_max(p3, p4)
            )
        }
        // [-, +], [+, +]
        return make_interval(xl * yu, xu * yu);
    }
    if (yl < 0) {
        // [+, +], [-, -]
        if (yu < 0) {
            return make_interval(xu * yl, xl * yu);
        }
        // [+, +], [-, +]
        return make_interval(xu * yl, xu * yu);
    }
    // [+, +], [+, +]
    return make_interval(xl * yl, xu * yu);
}

const i1 = make_interval(-2, -1);
const i2 = make_interval(-1, 2);
const i3 = make_interval(1, 2);

display(mul_interval(i1, i1));
display(mul_interval(i1, i2));
display(mul_interval(i1, i3));
display(mul_interval(i2, i1));
display(mul_interval(i2, i2));
display(mul_interval(i2, i3));
display(mul_interval(i3, i1));
display(mul_interval(i3, i2));
display(mul_interval(i3, i3));

入出力結果(Terminal, Zsh)

% node answer2.11.js
[ 1, 4 ]
[ -4, 2 ]
[ -4, -1 ]
[ -4, 2 ]
[ -2, 4 ]
[ -2, 4 ]
[ -4, -1 ]
[ -2, 4 ]
[ 1, 4 ]
%