The Bash Programming Tutorial: Compute the GCD (Greatest Common Divisor)

bash-shellshock

BASH script programming is powerful. However, the syntax is a lot different than the other modern programming languages e.g. C/C++, Java, Python, Javascript. Practice makes perfect: through coding exercises. This tutorial will present you a bash script that computes the GCD (Greatest Common Divisor) via the iterative approach.

The following is the BASH source code for computing the GCD between two integers.

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

#!/bin/bash
 
function max() {
        if [[ $1 > $2 ]] ; then
                return $1
        else
                return $2
        fi
}
 
function min() {
        if [[ $1 < $2 ]] ; then
                return $1
        else
                return $2
        fi
}
 
function gcd() {
        max $1 $2
        local a=$?
        min $1 $2
        local b=$?
        local t
        while [[ $b > 0 ]] ; do
                let t=a
                let a=b
                let b=t%b
        done
        return $a
}
 
if [[ "$1" =~ ^([0-9])+$ ]] && [[ "$2" =~ ^([0-9])+$ ]] ; then
        gcd $1 $2
        echo $?
else
        echo GCD Usage $0 integer1 integer2
fi

#!/bin/bash

function max() {
        if [[ $1 > $2 ]] ; then
                return $1
        else
                return $2
        fi
}

function min() {
        if [[ $1 < $2 ]] ; then
                return $1
        else
                return $2
        fi
}

function gcd() {
        max $1 $2
        local a=$?
        min $1 $2
        local b=$?
        local t
        while [[ $b > 0 ]] ; do
                let t=a
                let a=b
                let b=t%b
        done
        return $a
}

if [[ "$1" =~ ^([0-9])+$ ]] && [[ "$2" =~ ^([0-9])+$ ]] ; then
        gcd $1 $2
        echo $?
else
        echo GCD Usage $0 integer1 integer2
fi

To run the script, save the above script using your favorite text editor e.g. vi/vim/emacs, as e.g. gcd then chmod +x gcd to grant your script executable permission. Then:

1
2
3
4

$ gcd
GCD Usage gcd integer1 integer2
$ gcd 21 28
7

$ gcd
GCD Usage gcd integer1 integer2
$ gcd 21 28
7

Let’s take a look at the above bash script. The command line parameters can be referenced using the below syntax:

• $0 – the script filename itself in this case gcd
• $1 – the first command line parameter
• $2 – the second command line parameter

The BASH supports regex pattern testing via double square brackets and the =~ syntax. For example, the following code snippet test if the input is an integer:

1

[[ "$1" =~ ^([0-9])+$ ]]

[[ "$1" =~ ^([0-9])+$ ]]

And we can use the && to do the logical AND operator on two conditions (the two numbers need to be positive integers):

1

[[ "$1" =~ ^([0-9])+$ ]] && [[ "$2" =~ ^([0-9])+$ ]]

[[ "$1" =~ ^([0-9])+$ ]] && [[ "$2" =~ ^([0-9])+$ ]]

To invoke a function in BASH, we can use the following syntax:

1

function_name parameter1 parameter2 ...

function_name parameter1 parameter2 ...

For example:

1

gcd 21 27

gcd 21 27

And the return value of the function can be accessed immediately after the function call, via the syntax/variable “$?”

Inside the function, you can access the parameters passed in using $1, $2, $3 .. for the first, second and the third parameter respectively and so on. The return value can be returned via the return statement in BASH. And the local variables need to be declared with keyword local. For example:

1
2
3
4
5
6
7
8
9

function test() {
   local myvar = $1
   return $1
}
 
# Pass a string "Hello" to the function test.
test "Hello"
# prints Hello
echo $?

function test() {
   local myvar = $1
   return $1
}

# Pass a string "Hello" to the function test.
test "Hello"
# prints Hello
echo $?

The let is a BASH inbuilt keyword that evaluates the arithmetic expressions, similar to double parentheses:

1
2

(( expr ))
let expr

(( expr ))
let expr

And finally, this is the GCD implementation using BASH programming:

1
2
3
4
5
6
7
8
9
10
11
12
13

function gcd() {
        max $1 $2
        local a=$?
        min $1 $2
        local b=$?
        local t
        while [[ $b > 0 ]] ; do
                let t=a
                let a=b
                let b=t%b
        done
        return $a
}

function gcd() {
        max $1 $2
        local a=$?
        min $1 $2
        local b=$?
        local t
        while [[ $b > 0 ]] ; do
                let t=a
                let a=b
                let b=t%b
        done
        return $a
}

See also: BASH Function to Compute the Greatest Common Divisor and Least Common Multiples

–EOF (The Ultimate Computing & Technology Blog) —