Algorithms - JavaScript - 基礎概念 - 数学的な基礎(ユークリッド互除法(Euclidean Algorithm)、無理数、一般化)

The Art of Computer Programming
Volume 1
原著

開発環境

• macOS Sierra - Apple (OS)
• Emacs (Text Editor)
• JavaScript (プログラミング言語)
• Node.js, Safari(JavaScript エンジン)
• Learning JavaScript [邦訳](参考書籍)

The Art of Computer Programming　Volume 1 Fundamental Algorithms Third Edition 日本語版(Donald E. Knuth (著)、青木 孝 (著)、筧 一彦 (著)、鈴木 健一 (著)、長尾 高弘 (著)、有澤 誠 (その他)、和田 英一 (その他)、ドワンゴ)の第1章(基礎概念)、1.2(数学的な基礎)、演習問題12を取り組んでみる。

12. E2の除算(割り算)を減算(引き算)にする。

コード(Emacs)

HTML5

<pre id="output0"></pre>
m = <input id="mu0" type="number" step="1" value="12"> + <input id="mv0" type="number" step="1" value="-6">√2
<br>
n = <input id="nu0" type="number" step="1" value="20"> + <input id="nv0" type="number" step="1" value="-10">√2
<br>
<button id="run0">run</button>
<button id="clear0">clear</button>

<script src="sample12.js"></script>

JavaScript

let input_mu = document.querySelector('#mu0'),
    input_mv = document.querySelector('#mv0'),
    input_nu = document.querySelector('#nu0'),
    input_nv = document.querySelector('#nv0'),
    pre0 = document.querySelector('#output0'),
    btn0 = document.querySelector('#run0'),
    btn1 = document.querySelector('#clear0'),
    p = (x) => pre0.textContent += x + '\n',
    range = (start, end, step=1) => {
        let result = [];

        for (let i = start; i < end; i += step) {
            result.push(i);
        }
        return result;
    };

let Num = (u, v) => {
    let that = {},
        toString = () => `${u} + ${v}√2`,
        sub = (n) => Num(u - n.u, v - n.v),
        ge = (n) => u - n.u + (v - n.v) * Math.sqrt(2) >= 0,
        isZero = () => u + v * Math.sqrt(2) === 0;

    that.u = u;
    that.v = v;
    that.toString = toString;
    that.sub = sub;
    that.ge = ge;
    that.isZero = isZero;

    return that;
};

let gcd = (m, n) => {
    let r = m,
        q = 0;

    for (; r.ge(n);) {
        r = r.sub(n);
        q += 1;
    }        
    if (r.isZero()) {
        p(`${m} = ${q}(${n})`);
        p(n);
    } else {
        p(`${m} = ${q}(${n}) + (${r})`);
        setTimeout(() => gcd(n, r), 1000);
    }
};

let output = () => {
    let m = Num(parseInt(input_mu.value, 10), parseInt(input_mv.value, 10)),
        n = Num(parseInt(input_nu.value, 10), parseInt(input_nv.value, 10));

    gcd(m, n);
};

btn0.onclick = output;
btn1.onclick = () => pre0.textContent = '';

output();

m = + √2
n = + √2