Benchmark: Stern sequence5 - 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;
}
/**
 *  rational number of rank @i (using Stern diatonic sequence order)
 *  @returns {Array} - [num, den]
 *
 *  iterative version
 *  O(log(n)) time
 *  O(1) space
 */
function sternR3(i){
    let q = [0,1];
    if (i===0)
        return q;
    let mask = 1 << (Math.log2(i));
    while (mask) {
        if (i&mask)
            q[0] += q[1];
        else
            q[1] += q[0];
        i = i & (~mask);
        mask >>= 1;
    }
    return q;
}
/**
 *  rational number of rank @i (using Stern diatonic sequence order)
 *  @returns {Array} - [num, den]
 *
 *  iterative version
 *  O(log(n)) time
 *  O(1) space
 */
function sternR4(i){
    let q = [0,1];
    let mask = 1;
  	let j = i>>1;
    while (j) {
        j >>= 1;
        mask <<= 1;
    }
    while (mask) {
        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);
iterative (descending) #3
sternR3(n);
iterative (descending) #4
sternR4(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
iterative (descending) #3
iterative (descending) #4

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.

The provided code appears to be JavaScript and is using the `Benchmark` library for benchmarking purposes.

Based on the benchmark results, here are some observations:

1. The recursive version of the `sternR_rec` function has the slowest execution time, which suggests that it's not an efficient algorithm.
2. The iterative versions of `sternR_n` functions (`n=6000`) have faster execution times compared to the recursive version, with the fastest one being `sternR4(n)`. This implies that iterative algorithms are generally more efficient than recursive ones in JavaScript.
3. Among the iterative versions, `sternR4(n)` has the highest number of executions per second (4300124), which indicates it's the most efficient algorithm.
4. The results also show a decline in execution speed for `sternR_n` functions with smaller values of `n`, suggesting that the overhead of recursive function calls increases as the input size decreases.

To optimize the code, I would recommend using the iterative version `sternR4(n)` and exploring potential further optimizations, such as:

* Reducing memory allocations by reusing variables
* Using more efficient data structures (e.g., arrays instead of objects)
* Considering parallelization or multi-threading to take advantage of multiple CPU cores

However, without seeing the actual code, it's difficult to provide specific suggestions for improvement.

Related benchmarks:

Stern sequence5 (version: 0)

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

Created: 7 years ago by: Guest

Jump to the latest result

tail-end recursion (ascending)

iterative (descending)

iterative (descending) #2

iterative (descending) #3

iterative (descending) #4

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):