数学 - JavaScript - Scheme - ユークリッドの互除法(Euclidean algorithm, method of mutual division) - オイラーの贈物

オイラーの贈物
楽天ブックス Yahoo!

開発環境

• OS X El Capitan - Apple (OS)
• Emacs (Text Editor)
• JavaScript, Scheme(プログラミング言語)
• jQuery (Library)
• Safari(Web browser)
• kscheme(Scheme 処理系)

オイラーの贈物―人類の至宝eiπ=-1を学ぶ (吉田 武(著)、東海大学出版会)の第4部(附録(Appendix))、附録 A(発展的話題(Advanced topics))、A.1(ユークリッドの互除法)を取り組んでみる。

Euclidean algorithm

JavaScript で 書いていろいろな数字で試してたら、大きな数字で NaN になったから、Scheme でもコードを書いて試してみることに。JavaScript でも任意精度の整数が欲しくなってきたかも。。

コード(Emacs)

Scheme

(define euclidean-algorithm
  (lambda (m n)
    (define q (floor-quotient m n))
    (define r (floor-remainder m n))
    (if (= r 0)
        n
        (euclidean-algorithm n r))))

(define euclidean-algorithm-log
  (lambda (m n)
    (define q (floor-quotient m n))
    (define r (floor-remainder m n))
    (display m)
    (display " = ")
    (display q)
    (display " × ")
    (display n)
    (display " + ")
    (display r)
    (newline)
    (if (= r 0)
        n
        (euclidean-algorithm-log n r))))

(define method-of-mutual-division euclidean-algorithm)
(define method-of-mutual-division-log euclidean-algorithm-log)

HTML5/JavaScript

<script type="text/javascript" src="https://cdnjs.cloudflare.com/ajax/libs/jquery/3.0.0/jquery.min.js"></script>
<input id="m0" type="number" min="1" value="156" placeholder="156">
<input id="n0" type="number" min="1" value="65" placeholder="65">
<div id="result0"></div>
<script src="euclidean_algorithm.js"></script>

var euclidean_algorithm,
    display,
    calc,
    sum;

display = function (html) {
    $('#result0').append(html);
};

euclidean_algorithm = function (m, n) {
    var q = Math.floor(m / n),
        r = m % n;

    display(m + ' = ' + q + ' × ' + n + ' + ' + r + '<br>');
    if (r === 0) {
        display('gcd: ' + n + '<br>' + 'lcm: ' + (sum / n));
    } else {
        euclidean_algorithm(n, r);
    }
};

calc = function () {
    var m = parseInt($('#m0').val(), 10),
        n = parseInt($('#n0').val(), 10);

    $('#result0').html('');
    if (isNaN(m) || isNaN(n)) {
        $('#result0').append('NaN');
    } else {
        sum = m * n;
        euclidean_algorithm(m,n);
    }
};

$('#m0').keydown(calc);
$('#n0').keydown(calc);