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

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

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

LLMs can make mistakes. Check important info.

Let's dive into explaining what is tested in the provided benchmark and comparing different approaches.

**Benchmark Definition**

The benchmark definition represents a JavaScript function that calculates the Greatest Common Divisor (GCD) of two numbers, `a` and `b`. The GCD is the largest positive integer that divides both `a` and `b` without leaving a remainder. There are three implementations of the GCD algorithm:

1.  **Bottom Up**: This implementation uses a while loop to iterate from 2 to `min(a, b)` (where `min(a, b)` is the smaller of the two numbers) and checks if both `a` and `b` can be divided by the current divisor without leaving a remainder. If they can, it updates the greatest common divisor.
2.  **Top Down**: This implementation uses a recursive function that takes the smaller number as its base case and recursively calls itself with the remainder of `a` divided by the smaller number. The process repeats until the remainder is zero, at which point it returns the last non-zero remainder.
3.  **Good Non-Recursion**: This implementation uses a while loop similar to the Bottom Up approach but avoids using the modulo operator (`%`) instead directly checks if both numbers can be divided by the current divisor without leaving a remainder. If they can, it updates the greatest common divisor.
4.  **Good Recursion**: This implementation is similar to Top Down, but with an iterative approach instead of recursive function calls.

**Options Comparison**

Here's a comparison of different approaches:

*   **Bottom Up vs. Good Non-Recursion:** Both implementations use a while loop and avoid recursion, making them more efficient in terms of memory usage compared to the other two options. The difference lies in how they handle division; `goodNonRecursion` checks directly if both numbers can be divided by the divisor without using the modulo operator, whereas `bottomUp` uses the `%` operator.
*   **Top Down vs. Good Recursion:** Both implementations use recursion, but Top Down is typically less efficient because it involves function call overhead and potential stack overflows for large inputs. Good Recursion implements the same algorithm in an iterative fashion to avoid these issues.
*   **Efficiency:**

*   **Bottom Up** and **Good Non-Recursion**: These implementations are generally faster since they directly perform division checks without using recursion, which has overhead.
    *   **Top Down** and **Good Recursion**: While both avoid recursion in their iterative versions, the original recursive approach is usually slower due to additional function call overhead.

**Libraries Used**

In this benchmark, there isn't a specific library used for the GCD calculations. The implementations are standalone JavaScript functions.

**Special Features/Syntax**

*   **Modulo Operator (`%`):** The `%` operator is used in two of the implementations (Bottom Up and Good Non-Recursion) to calculate remainders during division, which helps determine the greatest common divisor.
*   **Recursive Function Calls:** Recursive function calls are used in Top Down and Good Recursion implementations. While recursive approaches can be elegant, they often come with additional overhead due to function call operations.

**Other Alternatives**

If you're looking for alternative GCD algorithms or JavaScript implementations:

*   **Euclidean Algorithm Variants:** There are variations of the Euclidean algorithm that might offer performance advantages in certain cases. These could involve different optimizations like loop optimization techniques.
*   **C++/Native Code:** Implementing GCD calculation using a native language (like C++) can be faster than JavaScript due to its lower-level memory management and execution efficiency.

In summary, when it comes to calculating the Greatest Common Divisor of two numbers in JavaScript, both Bottom Up and Good Non-Recursion approaches generally offer better performance than Top Down and Good Recursion because they avoid recursion. The difference lies mainly in how division checks are performed; `goodNonRecursion` uses direct checks without `%`, while `bottomUp` does with the modulo operator.

Latest run results:

Run details: (Test run date: 8 years ago)

User agent: Mozilla/5.0 (Windows NT 6.3; WOW64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/53.0.2785.143 Safari/537.36

Browser/OS: Chrome 53 on Windows 8.1

View result in a separate tab

Test name	Executions per second
Bottom Up	86622.8 Ops/sec
Top Down	118654.0 Ops/sec
Good non-recursion	6166971.0 Ops/sec
Good Recusion	1678227.0 Ops/sec

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 26 days ago):