Run results for: Stern sequence2

Run details:

User agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10_13_6) AppleWebKit/605.1.15 (KHTML, like Gecko) Version/11.1.2 Safari/605.1.15

Browser: Safari 11

Operating system: Mac OS X 10.13.6

Device Platform: Desktop

Date tested: 6 years ago

Test name	Executions per second
non tail-end recursion (descending)	459123.5 Ops/sec
tail-end recursion (ascending)	1488291.0 Ops/sec
iterative (descending)	1932483.0 Ops/sec

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)

Run results for: Stern sequence2

non tail-end recursion (descending)

tail-end recursion (ascending)

iterative (descending)