A JavaScript Extended Euclidian Algorithm Implementation

Below is an implementation of the Extended Euclidian Algorithm in JavaScript. It uses Michael Mclaughlin’s bignumber.js library to permit large inputs. Given two distinct and positive quantities \(A\) and \(B\), their greatest common divisor, the coefficients of Bézout’s identity and the positive Modular Multiplicative Inverse of \(A\) will be output (when they exist).

The quantities for \(A\) and \(B\) can be given in decimal or hexadecimal (by using a “0x” prefix). If the output base is specified as “Auto”, the output values will be in hexadecimal if either input is.

viewof astr = Inputs.text({label: "A", placeholder: "Enter a number", value: "5"})
viewof bstr = Inputs.text({label: "B", placeholder: "Enter a number", value: "11"})
viewof outputbase = Inputs.radio(["Auto", "Decimal", "Hexadecimal"], {label: "Output Base", value: "Auto"})

viewof gdcoutbox = Inputs.text({label: "Greatest Common Divisor", value: 'got nothin', disabled: true})
viewof bezoutbox = Inputs.text({label: "Bézout Equation", value: 'got nothin', disabled: true})
viewof mmioutbox = Inputs.text({label: "Modular Multiplicative Inverse of A (mod B)", value: 'got nothin', disabled: true})

function formatnum(bignum, base) {
    if (base === 10) {
        return bignum.toString();
    }
    let prefix = '';
    if (base === 16) {
        prefix = '0x';
    } else if (base === 2) {
        prefix = '0b';
    } else {
        throw new Error('iavalid base');
    }
    if (bignum.isLessThan(0)) {
        return '-' + prefix + bignum.negated().toString(base);
    }
    return prefix + bignum.toString(base);
}

function thing(gdcout, mmiout, bezoutout) {
    BigNumber.set({ DECIMAL_PLACES: 0, ROUNDING_MODE: BigNumber.ROUND_FLOOR })
    let base   = 10;
    let prefix = '';

    let usehex = false;

    if (outputbase == "Auto") {
        usehex = astr.startsWith('0x') || bstr.startsWith('0x');
    } else {
        usehex = (outputbase == "Hexadecimal");
    }
    if (usehex) {
        base = 16;
        prefix = '0x';
    } else {
        base = 10;
        prefix = '';
    }

    let aval = new BigNumber(astr, astr.startsWith('0x') ? 16 : 10);
    let bval = new BigNumber(bstr, bstr.startsWith('0x') ? 16 : 10);

    if (aval.isNaN() || bval.isNaN() || aval.isEqualTo(bval) || bval.isLessThanOrEqualTo(0) || aval.isLessThanOrEqualTo(0)) {
        gdcout.value = 'Dodgy input';
        gdcout.dispatchEvent(new Event("input", {bubbles: true}));
        mmiout.value = '';
        mmiout.dispatchEvent(new Event("input", {bubbles: true}));
        bezoutout.value = '';
        bezoutout.dispatchEvent(new Event("input", {bubbles: true}));
        return;
    }

    let old_r = aval;
    let r     = bval;
    let old_s = new BigNumber(1);
    let s     = new BigNumber(0);
    let old_t = new BigNumber(0);
    let t     = new BigNumber(1);
    while (!r.isZero()) {
        let q      = old_r.div(r);
        [old_r, r] = [r, old_r.minus(q.multipliedBy(r))];
        [old_s, s] = [s, old_s.minus(q.multipliedBy(s))];
        [old_t, t] = [t, old_t.minus(q.multipliedBy(t))];
    }

    gdcout.value = formatnum(old_r.absoluteValue(), base);
    gdcout.dispatchEvent(new Event("input", {bubbles: true}));

    bezoutout.value = formatnum(old_s, base) + ' A ' + (old_t.isLessThan(0) ? "-" : "+") + ' ' + formatnum(old_t.absoluteValue(), base) + ' B = ' + formatnum(old_r, base);
    bezoutout.dispatchEvent(new Event("input", {bubbles: true}));

    if (!old_r.absoluteValue().isEqualTo(1) || old_s.isZero() || old_t.isZero()) {
        mmiout.value = "No unique inverse";
    } else {
        var mmi = old_s;
        if (old_s.isLessThan(0)) {
            mmi = old_s.plus(bval);
        }
        console.assert(mmi.multipliedBy(aval).modulo(bval).isEqualTo(1));
        mmiout.value = formatnum(mmi, base) + ' A === 1 (mod B)';
    }
    mmiout.dispatchEvent(new Event("input", {bubbles: true}));
}

garbage = thing(viewof gdcoutbox, viewof mmioutbox, viewof bezoutbox);

No interesting story for this post. It is just a calculator. I wrote it because I periodically want to find the modulo multiplicative inverse of some number and most other online calculators I have found do not handle numbers greater than 32-bit. If you found it useful, star the bignumber.js repository - it made writing this tool an absolute breeze.