Run results for: Stern sequence4

Run details:

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

Browser: Firefox 62

Operating system: Mac OS X 10.13

Device Platform: Desktop

Date tested: 6 years ago

Test name	Executions per second
tail-end recursion (ascending)	5542822.0 Ops/sec
iterative (descending)	6348446.0 Ops/sec
iterative (descending) #2	25146106.0 Ops/sec
iterative (descending) #3	25662526.0 Ops/sec
iterative (descending) #4	25285730.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]];
}
/**
 *  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;
    for (let j = i>>1; 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)

Run results for: Stern sequence4

tail-end recursion (ascending)

iterative (descending)

iterative (descending) #2

iterative (descending) #3

iterative (descending) #4