Compute GCD in Bash with Input Validation

GCD Computation in Bash

What is GCD?

• GCD stands for Greatest Common Divisor.
• It is the largest positive integer that divides two numbers without leaving a remainder.
• For example:
  • GCD of 8 and 12 is 4
  • GCD of 14 and 49 is 7
• GCD is useful in simplifying fractions, cryptographic algorithms, and number theory.

Algorithms to Compute GCD

1. Euclidean Algorithm

• The most common and efficient method.
• Based on the principle that gcd(a, b) = gcd(b, a % b).
• Repeat until b becomes 0. At that point, a is the GCD.

2. Subtraction-Based Algorithm

• Keep subtracting the smaller number from the larger until both numbers are equal.
• That value is the GCD.
• Less efficient for large numbers compared to Euclidean method.

3. Binary GCD (Stein’s Algorithm)

• Uses bitwise operations instead of division.
• Efficient on systems where division/modulo is expensive.
• Based on properties of even/odd numbers:
  • If both numbers are even: gcd(a, b) = 2 * gcd(a/2, b/2)
  • If one is even: divide the even number by 2
  • If both are odd: gcd(a, b) = gcd((a - b)/2, b) if a > b

Overview

• Calculates the Greatest Common Divisor (GCD) of two numbers
• Ensures input arguments are positive integers
• Provides usage guidance when inputs are missing or invalid

Script Description

• Function gcd(): Implements the classic Euclidean algorithm using a loop and modulo operation.
• Argument Count Check: Ensures the user provides exactly 2 arguments. Otherwise, shows usage help and exits.
• Regex Validation: Checks if both inputs contain only digits using Bash regex.
• Range Check: Confirms both numbers are greater than zero.
• Function Call: Invokes the gcd function with the validated arguments and prints the result.

BASH Tool to Compute the GCD of given two integers

The following is the BASH script that takes 2 positive integers as the command line parameters, and the output the Greatest Common Divisor.

#!/bin/bash

## compute the GCD of given two numbers

gcd() {
    local a=$1
    local b=$2

    while [ $b -ne 0 ]; do
        local temp=$b
        b=$((a % b))
        a=$temp
    done

    echo $a
}

# Check if two arguments are provided
if [ $# -ne 2 ]; then
    echo "Usage: $0 <number1> <number2>"
    exit 1
fi

## check if both are positive integers
if ! [[ $1 =~ ^[0-9]+$ ]] || ! [[ $2 =~ ^[0-9]+$ ]]; then
    echo "Both arguments must be positive integers."
    exit 1
fi
if [ $1 -le 0 ] || [ $2 -le 0 ]; then
    echo "Both arguments must be greater than zero."
    exit 1
fi

# Call the gcd function with the provided arguments
result=$(gcd "$1" "$2")
echo $result

Input Validation Logic

1. Check the number of arguments passed
2. Use regex to confirm both are integers i.e. =~ ^[0-9]+$
3. Ensure both are greater than zero

Example Usage

The GCD of two co-prime numbers is 1.

Tip:

• Make the script executable with chmod +x gcd.sh
• Run it from the terminal: ./gcd.sh 12 30

BASH Programming/Shell

• Alarming on High Disk Usage using BASH, AWK, Crontab Job
• Compute GCD in Bash with Input Validation
• Why a Leading Space in Linux Shell Commands Can Matter?
• How to Get HTTP Response Code using cURL Command?
• Three Interesting/Fun BASH Commands
• One Interesting Linux Command (Steam Locomotive in BASH)
• Simple Bash Function to Repeat a Command N times with Retries
• How to Extract a Domain Name from a Full URL in BASH?
• BASH Function to Compute the Greatest Common Divisor and Least Common Multiples
• BASH Function to Get Memory Information via AWK
• BASH Function to Escape Parameters Argument
• BASH Function to Check if sudo Available
• Full Permutation Algorithm Implementation in BASH
• BASH Function to Install Docker
• A Simple BASH Function/Script to Run a Command in Background
• BASH Script to Compute the Average Ping to a Domain
• A Bash Process Controller to Start, Stop and Restart an Daemon Program
• Linux BASH shell - Echo This if you get angry
• Bash SHELL, Chess Board Printing

–EOF (The Ultimate Computing & Technology Blog) —