Class GCD

java.lang.Object
topics.divideconquer.gcd.GCD
public class GCD extends Object

Greatest Common Divisor (GCD)

Demonstrates the massive performance gap between a naive linear search and the ancient, highly optimized Euclidean Algorithm (a pure Divide invalid input: '&' Conquer approach).

Author:
vicegd

  • Constructor Details

    • GCD

      public GCD()

  • Method Details

    • naiveGCD

      public long naiveGCD(long a, long b)

      Naive Algorithm

      Iterates linearly from 1 up to the smaller of the two numbers, checking every single integer to see if it divides both evenly.

      • Time Complexity: O(min(a, b))
      • Space Complexity: O(1)
      Parameters:
      a - First number
      b - Second number
      Returns:
      The Greatest Common Divisor

    • euclideanGCD

      public long euclideanGCD(long a, long b)

      Euclidean Algorithm

      A recursive Divide and Conquer approach. It relies on the mathematical principle that the GCD of two numbers also divides their difference (and specifically, their remainder).

      • Time Complexity: O(log(min(a, b))) - Exponentially faster than naive.
      • Space Complexity: O(log(min(a, b))) - Call stack depth.
      Parameters:
      a - First number
      b - Second number
      Returns:
      The Greatest Common Divisor