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(1, 1);
Top Down
gcd1(1, 1);
Good non-recursion
gcd2(1, 1);
Good Recusion
gcd3(1, 1);

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/110.0.0.0 Safari/537.36

Browser/OS: Chrome 110 on Windows

View result in a separate tab

Test name	Executions per second
Bottom Up	7068526.0 Ops/sec
Top Down	6912901.0 Ops/sec
Good non-recursion	6613566.0 Ops/sec
Good Recusion	3212054.8 Ops/sec

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

LLMs can make mistakes. Check important info.

I'm ready to dive into the explanation.

**Benchmark Definition**

The benchmark measures the performance of four different implementations of the Greatest Common Divisor (GCD) function in JavaScript:

1. `gcd(a, b)` - Top-down recursive approach
2. `gcd1(a, b)` - Bottom-up iterative approach
3. `gcd2(a, b)` - Good non-recursion, iterative approach with a twist (more on this later)
4. `gcd3(a, b)` - Good recursion, iterative approach

**Options Compared**

The benchmark compares the performance of these four GCD implementations under different conditions:

* Top-down vs. Bottom-up approaches
* Recursive vs. Iterative approaches
* Non-recursion vs. Recursion approaches (for comparison)

**Pros and Cons of Each Approach**

1. **Top-Down Recursive Approach (`gcd(a, b)`)**:
	* Pros: Easy to implement, straightforward logic.
	* Cons: Can lead to high overhead due to recursive function calls.
2. **Bottom-Up Iterative Approach (`gcd1(a, b)`)**:
	* Pros: Reduces overhead by avoiding recursive function calls, can be more efficient.
	* Cons: May require more initial setup and complex logic.
3. **Good Non-Recursion (Iterative) Approach (`gcd2(a, b)`)**:
	* Pros: Can be more efficient than traditional iterative approaches due to clever use of mathematical properties.
	* Cons: Requires a deep understanding of the algorithm's inner workings.
4. **Good Recursion (Iterative) Approach (`gcd3(a, b)`)**:
	* Pros: Combines the benefits of recursion and iteration, can be more readable.
	* Cons: May still incur some overhead due to recursive function calls.

**Library and Special JS Feature**

The `TestName` field in each benchmark definition contains the implementation name. These implementations use various techniques to calculate the GCD:

* `gcd(a, b)` uses a simple top-down recursive approach with a base case of 1.
* `gcd1(a, b)` employs a bottom-up iterative approach using a fixed divisor starting from 2.
* `gcd2(a, b)` uses a clever trick to avoid recursion by swapping the input values in each iteration.
* `gcd3(a, b)` implements a recursive approach with an optimized base case.

**Other Considerations**

When analyzing these benchmarks, it's essential to consider factors like:

* Cache performance: Different implementations may cache results or have varying cache hit rates.
* Branch prediction and speculation: Some implementations might lead to more branch mispredictions than others.
* CPU architecture: The performance differences between the four implementations may vary depending on the specific CPU architecture.

**Alternatives**

If you're interested in exploring alternative GCD implementations, consider:

1. **Euclid's algorithm**: A well-known iterative approach that's often used in practice.
2. **Karatsuba's algorithm**: An optimized recursive approach for large numbers.
3. **Binary GCD**: An algorithm that uses binary arithmetic to calculate the GCD.

These alternatives might provide different trade-offs between performance, readability, and complexity.

Related benchmarks:

Compare GCD (version: 0)

Compare GCD

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

Created: 8 years ago by: Guest

Jump to the latest result

Bottom Up

Top Down

Good non-recursion

Good Recusion

Suite status: <idle, ready to run>

Experimental features:

Fastest: N/A

Slowest: N/A

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