Benchmark: Stern sequence3 - 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]];
}
/**
 *  rational number of rank @i (using Stern diatonic sequence order)
 *  @returns {Array} - [num, den]
 *
 *  iterative version
 *  O(log(n)) time
 *  O(1) space
 */
function sternR2(i){
    let q = [0,1];
    if (i===0)
        return q;
    let l = 1+(Math.log2(i)>>0);
    let mask = 1 << (l-1);
    for (let k=l; k>0; k--){
        if (i&mask)
            q[0] += q[1];
        else
            q[1] += q[0];
        i = i & (~mask);
        mask = mask >>1;
    }
    return q;
}
 
/**
 * i-ranked term of Stern diatonic sequence
 */
function stern(i){
    return sternR(i)[0];
    //return sternQ(i)[0];
}

var n = 6000;

Tests:

tail-end recursion (ascending)
sternR_rec(n);
iterative (descending)
sternR(n);
iterative (descending) #2
sternR2(n);

Rendered benchmark preparation results:

Suite status: <idle, ready to run>

Previous results

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

Fastest: N/A

Slowest: N/A

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

LLMs can make mistakes. Check important info.

I'd be happy to explain what's being tested in the provided benchmark.

**Benchmark Overview**

The Stern sequence is a mathematical concept that refers to the order of rational numbers generated by the Stern diatonic sequence. The task at hand is to measure the performance of three different implementations of calculating the i-ranked term of this sequence: `sternR_rec`, `sternR`, and `sternR2`.

**Options Being Compared**

The three options being compared are:

1. **`sternR_rec`**: This implementation uses tail-end recursion, which is a technique where the recursive call is made from the end of the function, avoiding stack overflow issues.
2. **`sternR`**: This implementation uses iterative approach with a loop to calculate the Stern sequence term.
3. **`sternR2`**: This implementation uses bitwise operations to optimize the calculation.

**Pros and Cons**

* **`sternR_rec`**: Pros:
	+ Avoids stack overflow issues due to tail-end recursion.
	+ Can be more efficient in terms of memory usage.
* Cons:
	+ May have slower performance compared to other approaches due to recursive calls.
* **`sternR`**: Pros:
	+ Fast and efficient, with O(log(n)) time complexity.
	+ Simple to implement.
* Cons:
	+ Uses a loop, which may be less optimal than bitwise operations for large values of n.
* **`sternR2`**: Pros:
	+ Optimized for performance using bitwise operations.
	+ Can handle large values of n efficiently.
* Cons:
	+ May have more complex implementation compared to `sternR`.

**Library/External Dependencies**

None mentioned in the benchmark definition.

**Special JS Features/Syntax**

The benchmark uses some advanced JavaScript features, such as:

* **Tail-end recursion**: The `sternR_rec` function uses tail-end recursion, which is a technique used to optimize recursive functions.
* **Bitwise operations**: The `sternR2` function uses bitwise operations to calculate the Stern sequence term.

**Other Alternatives**

If the benchmark were to consider other alternatives, some options could be:

* Using a different algorithm for calculating the Stern sequence, such as an iterative approach using matrix multiplication.
* Comparing the performance of these implementations on different platforms or browsers.
* Considering the use of just-in-time (JIT) compilation or ahead-of-time (AOT) compilation to optimize the performance of the implementation.

I hope this explanation helps! Let me know if you have any further questions.

Latest run results:

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

User agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.13; rv:61.0) Gecko/20100101 Firefox/61.0

Browser/OS: Firefox 61 on Mac OS X 10.13

View result in a separate tab

Test name	Executions per second
tail-end recursion (ascending)	3595501.2 Ops/sec
iterative (descending)	3933695.8 Ops/sec
iterative (descending) #2	15843731.0 Ops/sec

Related benchmarks:

Stern sequence3 (version: 0)

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

Created: 6 years ago by: Guest

Jump to the latest result

tail-end recursion (ascending)

iterative (descending)

iterative (descending) #2

Suite status: <idle, ready to run>

Experimental features:

Fastest: N/A

Slowest: N/A

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