algorithm-archive/contents/euclidean_algorithm/code/bash/euclid.bash at main · algorithm-archivists/algorithm-archive · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#!/usr/bin/env bash
abs() {
    local ret=$1
    if (( ret < 0 )); then
        ((ret *= -1))
    fi
    printf "%s" "$ret"
}

euclid_mod() {
    local a
    local b
    a=$(abs "$1")
    b=$(abs "$2")

    while (( b != 0 )); do
        ((tmp = b))
        ((b = a % b))
        ((a = tmp))
    done
    printf "%s" "$a"
}

euclid_sub() {
    local a
    local b
    a=$(abs "$1")
    b=$(abs "$2")

    while (( a != b )); do
        if (( a > b )); then
            ((a -= b))
        else
            ((b -= a))
        fi
    done
    printf "%s" "$a"
}

result=$(euclid_mod $((64 * 67)) $((64 * 81)))
echo -e "[#]\nModulus-based euclidean algorithm result:\n$result"
result=$(euclid_sub $((128 * 12)) $((128 * 77)))
echo -e "[#]\nSubtraction-based euclidean algorithm result:\n$result"