Assembly Language Program: Least
Common Multiple (LCM)
Objective
This assignment details an assembly language program designed to compute
the Least Common Multiple (LCM) of two given numbers. The program
leverages the fundamental relationship between the LCM and Greatest
Common Divisor (GCD) of two numbers.
Program Code
The following is the assembly language code provided for computing the
LCM:mult $t0, $t1 # Product = $t0 * $t1
mflo $t3 # Store product in $t3
gcd_loop:
beq $t1, $zero, gcd_done # If $t1 is zero, GCD is in $t0
div $t0, $t1 # $t0 / $t1 (quotient in $t0, remainder in $t1)
mfhi $t2 # Move remainder to $t2
move $t0, $t1 # New $t0 = old $t1
move $t1, $t2 # New $t1 = remainder
j gcd_loop # Loop until $t1 is zero
gcd_done:
# $t0 now holds GCD
div $t3, $t0 # Product / GCD
mflo $t4 # Store quotient (LCM) in $t4
j lcm_done
lcm_done:
# $t4 holds final LCM
Principles of Calculation
The program calculates the LCM of two numbers by first computing their
product and their Greatest Common Divisor (GCD). The core principle relied
upon is the mathematical relationship:
LCM(A, B) = (A * B) / GCD(A, B)Where A and B are the two numbers for
which the LCM is to be computed.
1. Product Calculation
The first step in the program is to compute the product of the two input
numbers. In the provided code, it's assumed that the two numbers are initially
stored in registers $t0 and $t1.
● mult $t0, $t1: This instruction performs the multiplication of the
values in $t0 and $t1. The result of the multiplication is stored in two
special-purpose registers: HI (for the high-order bits) and LO (for the
low-order bits).
● mflo $t3: This instruction moves the low-order 32 bits of the
multiplication result (from the LO register) into register $t3. For typical
integer products, this will contain the full product.
2. Greatest Common Divisor (GCD) Calculation (Euclidean
Algorithm)
The program then proceeds to calculate the GCD of the two numbers using the
Euclidean algorithm, an efficient method for computing the GCD. The algorithm
is based on the principle that the GCD of two numbers does not change if the
larger number is replaced by its difference with the smaller number. This
process is repeated until one of the numbers becomes zero, at which point the
other number is the GCD.
The gcd_loop section of the code implements this algorithm:
● beq $t1, $zero, gcd_done: This is the termination condition for the
loop. If the value in $t1 becomes zero, it means the GCD has been found
and is now stored in $t0. The program then branches to gcd_done.
● div $t0, $t1: This instruction performs integer division of $t0 by $t1.
The quotient is stored in the LO register, and the remainder is stored in
the HI register.
● mfhi $t2: This instruction moves the remainder of the division (from the
HI register) into temporary register $t2.
● move $t0, $t1: The value of $t1 (the previous divisor) is moved into
$t0. This effectively replaces the larger number with the smaller number
for the next iteration.
● move $t1, $t2: The remainder (previously stored in $t2) is moved into
$t1. This replaces the smaller number with the remainder.
● j gcd_loop: This instruction jumps back to the beginning of the
gcd_loop to continue the iterative process.
Upon exiting the gcd_loop, the register $t0 will contain the GCD of the original
two numbers.
3. Least Common Multiple (LCM) Calculation
Once the product and the GCD are known, the final step is to calculate the LCM
using the derived formula:
● div $t3, $t0: This instruction performs the division of the product
(stored in $t3) by the GCD (stored in $t0).
● mflo $t4: The low-order 32 bits of the division result (the quotient,
which represents the LCM) are moved from the LO register into $t4.
● j lcm_done: This instruction jumps to the lcm_done label, signifying the
completion of the LCM calculation. At this point, register $t4 holds the
final LCM.
Conclusion
This assembly language program effectively computes the LCM of two
numbers by systematically applying the principles of multiplication and the
Euclidean algorithm for GCD calculation. The clear separation of concerns
(product, GCD, and final LCM calculation) within the code contributes to its
readability and maintainability. This approach provides a robust and efficient
solution for determining the LCM in an assembly language environment.
