Euclid algorithm

Find the greatest common divisor.

by prometh

HTML

<p>Greatest common diviser between <input type="text" id="m"/> and <input type="text" id="n"/></p>

<button name="calculate">Calculate</button>
<button name="reset">Reset</button>

<pre id="results"></pre>

CSS

input[type=text] {
    width: 4em;
}

#results {
    border-top: 2px solid silver;
    padding-top: .5em;
}

JavaScript

function euclid(m,n) {
	var m2,r=1;
	
	// Ensure m>=n
	if (m < n) {
		m2 = m;
		m = n;
		n = m2;
	}
    
    // No floats allowed
    if (Math.floor(m) !== m || Math.floor(n) !== n) {
        throw new RangeError("Input must be an integer");
    }
	
	// Working with -1 any further will be messy and is always a predictable common divisor
    // THIS IS WRONG :: but keeping it to avoid my own future confusion
	//if (n == -1) return m*n;
	
	// Cannot work with other negatives and cannot divide by 0
	if (n <= 0) throw new RangeError("Input must be be greater than 0");
	
	while (r) {
		// Remainder
		r = Math.floor(m/n);
		if (r) r = m-n*r;
		
		// For next iteration
		if (r) {
			m = n;
			n = r;
		}
	}
	
	return n;
}


function render(m,n) {
    var result;
    
    try {
        result = euclid(m,n);
    } catch (error) {
        result = "ERROR";
    }
    
    var results = document.getElementById("results");
    results.innerHTML += "Greatest common divisor between "+m+" and "+n+" is "+result+"\n";
}


render(119,544);	// 17
render(3,2);		// 1
render(2,2);        // 2
render(3,0);		// err
render(3,-1);		// -3
render(3,-2);		// err
render(3,-6);		// err
render(2,2.5);		// err


document.querySelector("button[name=calculate]").addEventListener("click", function() {
    var m = document.getElementById("m");
    var n = document.getElementById("n");
    render( parseInt(m.value), parseInt(n.value) );
    m.value = "";
    n.value = "";
});


document.querySelector("button[name=reset]").addEventListener("click", function() {
    document.getElementById("m").value = "";
    document.getElementById("n").value = "";
    document.getElementById("results").innerHTML = "";
});