Building Abstractions with Data - Introduction to Data Abstraction - Extended Exercise: Interval Arithmetic - intervals, small percentage tolerance, approximate percentage tolerance of the product

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

c1、c2を中心、ε1、ε2を誤差の誤差のパーセンテージとする二つの区間について、

x_c1 = [c1 - c1 * ε1, c1 + c1 * ε1]
y_c2 = [c2 - c2 * ε2, c2 + c2 * ε2]

とし、その積を考える。(簡略化のために全ての端点は正の数とする。)

x_c1 * y_c2
[(c1 - c1 * ε1)(c2 - c2 * ε2), (c1 + c1 * ε1)(c2 + c2 * ε2)]
[c1 * c2 - c1 * c2 * ε2 - c1 * c2 * ε1 + c1 * c2 * ε1 * ε2, c1 * c2 + c1 * c2 * ε2 + c1 * c2 * ε1 + c1 * c2 * ε1 * ε2]
[c1 * c2 (1 - ε1 - ε2 + ε1 * ε2), c1 * c2 (1 + ε1 + ε2 + ε1 * ε2)]

ε1とε2が十分に小さいとき、ε1 * ε2を0とすると、

[c1 * c2 (1 - ε1 - ε2), c1 * c2 (1 + ε1 + ε2)]
[c1 * c2 - c1 * c2 (ε1 + ε2), c1 * c2 + c1 * c2 (ε1 + ε2)]

よって2つの区間の積の誤差は、2つの区間の誤差の和で近似できる。

実際に確認。

コード

function math_abs(x) {
    return Math.abs(x);
}
function display(x) {
    return console.log(x);
}
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(i) {
    return head(i);
}
function upper_bound(i) {
    return tail(i);
}
function make_center_percent(c, p) {
    const w = math_abs(c) * p / 100;
    return make_interval(c - w, c + w);
}
function center(i) {
    return (lower_bound(i) + upper_bound(i)) / 2;
}
function percent(i) {
    const u = upper_bound(i);
    const m = center(i);
    return (u - m) / m * 100;
}
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 tx = 10;
const ty = 5;
const x = make_center_percent(2, tx);
const y = make_center_percent(3, ty);
const xy = mul_interval(x, y);

display(x);
display(y);
display(xy);
display(percent(xy));
display(tx + ty);

入出力結果(Terminal, Zsh)

% node answer2.13.js
[ 1.8, 2.2 ]
[ 2.85, 3.15 ]
[ 5.13, 6.930000000000001 ]
14.925373134328362
15
%