Benchmark: Compare GCD - MeasureThat.net

Script Preparation code:

function gcd(a, b){
  var divisor = 2, 
      greatestDivisor = 1;

  if (a < 2 || b < 2)
     return 1;
  
  while(a >= divisor && b >= divisor){
   if(a %divisor == 0 && b% divisor ==0){
      greatestDivisor = divisor;      
    }
   divisor++;
  }
  return greatestDivisor;
}

function gcd1(a,b){
    var divisor = a < b ? a : b;  	
    
    if(a < 2 || b < 2){
        return 1;
    }
    
    while(divisor > 0){
        if(a % divisor === 0 && b % divisor === 0){
            return divisor;
        }
        divisor--;
    }
}

function gcd2(a, b){
    var x;
    
    while(b !== 0){
        x = a % b;
        a = b;
        b = x;
    }
    
    return a;
}

function gcd3(a, b){
    if(b === 0)
        return a;
    return gcd3(b, a % b);
}

Tests:

Bottom Up
gcd(14, 21);
Top Down
gcd1(14, 21);
Good non-recursion
gcd2(14, 21);
Good Recusion
gcd3(14, 21);

Rendered benchmark preparation results:

Suite status: <idle, ready to run>

Previous results

Test case name	Result
Bottom Up
Top Down
Good non-recursion
Good Recusion

Fastest: N/A

Slowest: N/A

Latest run results:

Run details: (Test run date: one year ago)

User agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/131.0.0.0 Safari/537.36

Browser/OS: Chrome 131 on Windows

View result in a separate tab

Test name	Executions per second
Bottom Up	15883154.0 Ops/sec
Top Down	14345156.0 Ops/sec
Good non-recursion	38875168.0 Ops/sec
Good Recusion	22250468.0 Ops/sec

Autogenerated LLM Summary (model llama3.2:3b, generated one year ago):

LLMs can make mistakes. Check important info.

Measuring the performance of different approaches to calculating the Greatest Common Divisor (GCD) in JavaScript can be a valuable exercise.

**Benchmark Definition**

The benchmark definition consists of four functions:

1. `gcd(a, b)`: This is the original implementation of GCD using a simple loop.
2. `gcd1(a, b)`: This implementation uses a top-down approach with an initial divisor calculation and a while loop to iterate through divisors.
3. `gcd2(a, b)`: This is a non-recursive implementation using the Euclidean algorithm, which iteratively applies the property that `gcd(a, b) = gcd(b, a % b)`.
4. `gcd3(a, b)`: This implementation uses recursion to calculate GCD.

**Options Compared**

The benchmark compares four different approaches:

* **Bottom-Up**: The original implementation using a simple loop (`gcd(a, b)`).
* **Top Down**: The top-down approach with an initial divisor calculation and a while loop (`gcd1(a, b)`).
* **Good Non-Recursion**: A non-recursive implementation using the Euclidean algorithm (`gcd2(a, b)`).
* **Good Recursion**: An implementation using recursion to calculate GCD (`gcd3(a, b)`).

**Pros and Cons**

Here's a brief overview of the pros and cons of each approach:

1. `gcd(a, b)`: Simple and easy to understand, but may not be the most efficient due to the use of a loop.
	* Pros: Easy to implement, fast execution for small inputs.
	* Cons: Slow for large inputs due to the overhead of the loop.
2. `gcd1(a, b)`: Uses an initial divisor calculation and a while loop, which can be more efficient than the simple loop in `gcd(a, b)`.
	* Pros: May be faster than `gcd(a, b)` for larger inputs.
	* Cons: The initial divisor calculation may lead to unnecessary iterations.
3. `gcd2(a, b)`: A non-recursive implementation using the Euclidean algorithm, which is generally more efficient and reliable than recursive approaches.
	* Pros: Fast execution, reliable results, and avoids potential stack overflow issues.
	* Cons: May require additional arithmetic operations due to the iterative approach.
4. `gcd3(a, b)`: An implementation using recursion, which can be slower and less memory-efficient than non-recursive approaches.
	* Pros: Easy to understand and implement, but may not be suitable for large inputs.
	* Cons: Slow execution due to recursive calls, potential stack overflow issues.

**Library**

The benchmark uses the `Math` library, which provides the modulo (`%`) operator used in all implementations. No additional libraries are required beyond what's included with JavaScript.

**Special JS Features or Syntax**

There's no mention of special JavaScript features or syntax being used in this benchmark.

**Other Alternatives**

If you're interested in exploring alternative approaches to GCD calculations, here are a few options:

* **Iterative Approach using Bit Manipulation**: Implement the Euclidean algorithm using bit manipulation techniques, such as bitwise AND and XOR.
* **Memoization**: Use memoization to store results of previously computed GCDs for smaller inputs, which can significantly improve performance for repeated calls with similar inputs.
* **Parallelization**: Explore parallelizing the calculation of GCD across multiple CPU cores or threads using libraries like Web Workers or Node.js clusters.

Keep in mind that the choice of approach depends on the specific requirements and constraints of your use case.

Related benchmarks:

Compare GCD (version: 0)

Compare GCD

Comparing performance of: Bottom Up vs Top Down vs Good non-recursion vs Good Recusion

Created: 9 years ago by: Guest

Jump to the latest result

Bottom Up

Top Down

Good non-recursion

Good Recusion

Suite status: <idle, ready to run>

Fastest: N/A

Slowest: N/A

Autogenerated LLM Summary (model llama3.2:3b, generated one year ago):