Benchmark: Stern sequence2 - MeasureThat.net

Script Preparation code:

/**
 *  rational number of rank @i (using Stern diatonic sequence order)
 *  @returns {Array}  [num, den]
 *
 *  non tail-end recursion version
 *  O(log(n)) time
 *  O(log(n)) space (heap) 
 */
function sternQ(i) {
    if (i === 0)
        return [0,1];
    let [n,d] = sternQ(i>>1);
    if (i&1) 
        return [n+d,d];
    else
        return [n,n+d];
}

 /**
 *  rational number of rank @i (using Stern diatonic sequence order)
 *  @returns {Array} - [num, den]
 *
 *  non tail-end recursion version
 *  O(log(n)) time
 *  O(log(n)) space (if no tail calll elimination, O(1) otherwise)
 */
function sternR_rec(i, frac = {num:[1,0],den:[0,1]}){
  if (i === 0)
    return [-frac.num[1],frac.num[0]];
  else if (i&1)
    return sternR(i>>1, {num:[frac.num[0]-frac.den[0], frac.num[1]-frac.den[1]], den : frac.den});
  else
    return sternR(i>>1, {num:frac.num, den : [frac.den[0]-frac.num[0], frac.den[1]-frac.num[1]]});
}

/**
 *  rational number of rank @i (using Stern diatonic sequence order)
 *  @returns {Array} - [num, den]
 *
 *  iterative version
 *  O(log(n)) time
 *  O(1) space
 */
function sternR(i){
  let frac = {num:[1,0],den:[0,1]};
  while (i !== 0){
    if (i&1) // odd
        frac.num = [frac.num[0]-frac.den[0], frac.num[1]-frac.den[1]];
    else     // even
        frac.den = [frac.den[0]-frac.num[0], frac.den[1]-frac.num[1]];
    i = i>>1;
  }
  return [-frac.num[1],frac.num[0]];
}
/**
 * i-ranked term of Stern diatonic sequence
 */
function stern(i){
    return sternR(i)[0];
    //return sternQ(i)[0];
}

var n = 6000;

Tests:

non tail-end recursion (descending)
sternQ(n);
tail-end recursion (ascending)
sternR_rec(n);
iterative (descending)
sternR(n)

Rendered benchmark preparation results:

Suite status: <idle, ready to run>

Previous results

Test case name	Result
non tail-end recursion (descending)
tail-end recursion (ascending)
iterative (descending)

Fastest: N/A

Slowest: N/A

Latest run results:

No previous run results

This benchmark does not have any results yet. Be the first one to run it!

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

LLMs can make mistakes. Check important info.

Measuring JavaScript performance is a complex task, and understanding the nuances of each benchmark is essential to get accurate results.

**Benchmark Definition**

The provided JSON represents a benchmark for calculating the i-ranked term of Stern diatonic sequence. The sequence is generated using three different approaches:

1. **non tail-end recursion (descending)**: This approach uses a recursive function with a non-optimized form of tail call elimination, which means that the return value is not immediately passed to the next line of code. However, since it's still a recursive function, this optimization does not apply.
2. **tail-end recursion (ascending)**: This approach uses another recursive function, but with an optimized form of tail call elimination. The return value is immediately passed to the next line of code, reducing overhead and improving performance.
3. **iterative (descending)**: This approach uses a loop instead of recursion, which is generally faster due to fewer function calls and less overhead.

**Options Compared**

The benchmark compares the execution time of each approach on different browsers (Safari 11) running on Mac OS X 10.13.6 desktop devices. The options being compared are:

* Non tail-end recursion with descending order
* Tail-end recursion with ascending order
* Iterative with descending order

**Pros and Cons**

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

1. **Non tail-end recursion (descending)**:
	* Pros: May be easier to implement and understand, especially for developers familiar with recursive functions.
	* Cons: Without tail call elimination optimization, this approach can be slower due to function call overhead.
2. **Tail-end recursion (ascending)**:
	* Pros: Optimized form of tail call elimination reduces overhead and improves performance.
	* Cons: May require more complex code and better understanding of tail call optimization.
3. **Iterative (descending)**:
	* Pros: Generally faster due to fewer function calls and less overhead, making it a good choice for performance-critical code.
	* Cons: May be more difficult to implement and understand, especially for developers without experience with loops.

**Library**

The `sternQ` function uses the `ternary operator` (`? :`) which is not explicitly mentioned in the provided JSON. However, I'll mention it as an additional context. The ternary operator allows for a concise way of expressing conditional statements and is commonly used in JavaScript.

**Special JS Feature or Syntax**

None are explicitly mentioned in the provided code snippets.

**Other Considerations**

To get accurate results, consider the following:

* Use a recent version of JavaScript (ES6+) to ensure that all features are supported.
* Test on multiple browsers and devices to account for variations in performance.
* Run each benchmark multiple times and take the average execution time to reduce noise.
* Consider using additional optimization techniques, such as caching or memoization, depending on the specific use case.

**Alternatives**

Some alternative approaches for calculating Stern diatonic sequence include:

* Using a more optimized algorithm, such as one that uses bit manipulation or arithmetic progression instead of recursion.
* Implementing the sequence using a different data structure, like an array or a linked list, to reduce overhead.
* Utilizing modern JavaScript features like `let` and `const` for variable declaration, or `async/await` for asynchronous programming.

Related benchmarks:

Stern sequence2 (version: 0)

Comparing performance of: non tail-end recursion (descending) vs tail-end recursion (ascending) vs iterative (descending)

Created: 7 years ago by: Guest

Jump to the latest result

non tail-end recursion (descending)

tail-end recursion (ascending)

iterative (descending)

Suite status: <idle, ready to run>

Fastest: N/A

Slowest: N/A

No previous run results

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