Algorithms: Number Theory

function modular_inverse(int $a, int $modulus): int {
    alg_require((($modulus >= 2) && ($modulus <= 10000) && ($a >= 0) && ($a < $modulus)));
    $old_r = $modulus;
    $r = $a;
    $old_t = 0;
    $t = 1;
    $quotient = 0;
    $temp = 0;
    while (($r != 0)) {
        $quotient = intdiv($old_r, $r);
        $temp = alg_sub($old_r, alg_mul($quotient, $r));
        $old_r = $r;

    static int binary_gcd(int a, int b) {
        alg_require(((a >= 0) && (b >= 0)));
        if ((a == 0)) {
            return b;
        }
        if ((b == 0)) {
            return a;
        }
        int factor = 1;
        int temp = 0;
        while ((((a % 2) == 0) && ((b % 2) == 0))) {
            a = (a / 2);

function binary_gcd(a, b) {
    alg_require(Number.isInteger(a) && a >= -2147483648 && a <= 2147483647);
    alg_require(Number.isInteger(b) && b >= -2147483648 && b <= 2147483647);
    alg_require(((a >= 0) && (b >= 0)));
    if ((a == 0)) {
        return b;
    }
    if ((b == 0)) {
        return a;
    }
    let factor = 1;
    let temp = 0;

def binary_gcd(a: int, b: int) -> int:
    alg_require(type(a) is int and -2147483648 <= a <= 2147483647)
    alg_require(type(b) is int and -2147483648 <= b <= 2147483647)
    alg_require(a >= 0 and b >= 0)
    if a == 0:
        return b
    if b == 0:
        return a
    factor: int = 1
    temp: int = 0
    while a % 2 == 0 and b % 2 == 0:
        a = a // 2

int binary_gcd(int a, int b) {
    int alg_error = 0;
    int alg_result = INT_MIN;
    errno = 0;
    if (!(((a >= 0) && (b >= 0)))) { errno = EINVAL; alg_result = INT_MIN; goto alg_cleanup; }
    if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
    int alg_condition_1 = (a == 0);
    if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
    if (alg_condition_1) {
        alg_result = b;
        if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
        goto alg_cleanup;