least_common_multiple.cpp File Reference

#include <cassert>
#include <iostream>

Include dependency graph for least_common_multiple.cpp:

Functions
unsigned int	gcd (unsigned int x, unsigned int y)
unsigned int	lcm (unsigned int x, unsigned int y)
void	tests ()
int	main ()

Detailed Description

Copyright 2020

Author

tjgurwara99

A basic implementation of LCM function

Function Documentation

gcd()

unsigned int gcd	(	unsigned int	x,
		unsigned int	y )

Function for finding greatest common divisor of two numbers. @params two integers x and y whose gcd we want to find.

Returns

greatest common divisor of x and y.

                                                 {
    if (x == 0) {
        return y;
    }
    if (y == 0) {
        return x;
    }
    if (x == y) {
        return x;
    }
    if (x > y) {
        // The following is valid because we have checked whether y == 0
 
        unsigned int temp = x / y;
        return gcd(y, x - temp * y);
    }
    // Again the following is valid because we have checked whether x == 0
 
    unsigned int temp = y / x;
    return gcd(x, y - temp * x);
}

Here is the call graph for this function:

lcm()

unsigned int lcm	(	unsigned int	x,
		unsigned int	y )

Function for finding the least common multiple of two numbers. @params integer x and y whose lcm we want to find.

Returns

lcm of x and y using the relation x * y = gcd(x, y) * lcm(x, y)

                                                 {
  return x / gcd(x, y) * y;
}

Here is the call graph for this function:

main()

int main

(

void

)

Main function

           {
    tests();
    return 0;
}

Here is the call graph for this function:

tests()

void tests

(

)

Function for testing the lcm() functions with some assert statements.

             {
    // First test on lcm(5,10) == 10
    assert(((void)"LCM of 5 and 10 is 10 but lcm function gives a different "
                  "result.\n",
            lcm(5, 10) == 10));
    std::cout << "First assertion passes: LCM of 5 and 10 is " << lcm(5, 10)
              << std::endl;
 
    // Second test on lcm(2,3) == 6 as 2 and 3 are coprime (prime in fact)
    assert(((void)"LCM of 2 and 3 is 6 but lcm function gives a different "
                  "result.\n",
            lcm(2, 3) == 6));
    std::cout << "Second assertion passes: LCM of 2 and 3 is " << lcm(2, 3)
              << std::endl;
 
    // Testing an integer overflow.
    // The algorithm should work as long as the result fits into integer.
    assert(((void)"LCM of 987654321 and 987654321 is 987654321 but lcm function"
                  " gives a different result.\n",
            lcm(987654321, 987654321) == 987654321));
    std::cout << "Third assertion passes: LCM of 987654321 and 987654321 is "
              << lcm(987654321, 987654321)
              << std::endl;
}

Here is the call graph for this function: