{"ScriptPreparationCode":"/**\r\n * rational number of rank @i (using Stern diatonic sequence order)\r\n * @returns {Array} [num, den]\r\n *\r\n * non tail-end recursion version\r\n * O(log(n)) time\r\n * O(log(n)) space (heap) \r\n */\r\nfunction sternQ(i) {\r\n if (i === 0)\r\n return [0,1];\r\n let [n,d] = sternQ(i\u003E\u003E1);\r\n if (i\u00261) \r\n return [n\u002Bd,d];\r\n else\r\n return [n,n\u002Bd];\r\n}\r\n\r\n /**\r\n * rational number of rank @i (using Stern diatonic sequence order)\r\n * @returns {Array} - [num, den]\r\n *\r\n * non tail-end recursion version\r\n * O(log(n)) time\r\n * O(log(n)) space (if no tail calll elimination, O(1) otherwise)\r\n */\r\nfunction sternR_rec(i, frac = {num:[1,0],den:[0,1]}){\r\n if (i === 0)\r\n return [-frac.num[1],frac.num[0]];\r\n else if (i\u00261)\r\n return sternR(i\u003E\u003E1, {num:[frac.num[0]-frac.den[0], frac.num[1]-frac.den[1]], den : frac.den});\r\n else\r\n return sternR(i\u003E\u003E1, {num:frac.num, den : [frac.den[0]-frac.num[0], frac.den[1]-frac.num[1]]});\r\n}\r\n\r\n/**\r\n * rational number of rank @i (using Stern diatonic sequence order)\r\n * @returns {Array} - [num, den]\r\n *\r\n * iterative version\r\n * O(log(n)) time\r\n * O(1) space\r\n */\r\nfunction sternR(i){\r\n let frac = {num:[1,0],den:[0,1]};\r\n while (i !== 0){\r\n if (i\u00261) // odd\r\n frac.num = [frac.num[0]-frac.den[0], frac.num[1]-frac.den[1]];\r\n else // even\r\n frac.den = [frac.den[0]-frac.num[0], frac.den[1]-frac.num[1]];\r\n i = i\u003E\u003E1;\r\n }\r\n return [-frac.num[1],frac.num[0]];\r\n}\r\n/**\r\n * rational number of rank @i (using Stern diatonic sequence order)\r\n * @returns {Array} - [num, den]\r\n *\r\n * iterative version\r\n * O(log(n)) time\r\n * O(1) space\r\n */\r\nfunction sternR2(i){\r\n let q = [0,1];\r\n if (i===0)\r\n return q;\r\n let l = 1\u002B(Math.log2(i)\u003E\u003E0);\r\n let mask = 1 \u003C\u003C (l-1);\r\n for (let k=l; k\u003E0; k--){\r\n if (i\u0026mask)\r\n q[0] \u002B= q[1];\r\n else\r\n q[1] \u002B= q[0];\r\n i = i \u0026 (~mask);\r\n mask = mask \u003E\u003E1;\r\n }\r\n return q;\r\n}\r\n/**\r\n * rational number of rank @i (using Stern diatonic sequence order)\r\n * @returns {Array} - [num, den]\r\n *\r\n * iterative version\r\n * O(log(n)) time\r\n * O(1) space\r\n */\r\nfunction sternR3(i){\r\n let q = [0,1];\r\n if (i===0)\r\n return q;\r\n let mask = 1 \u003C\u003C (Math.log2(i));\r\n while (mask) {\r\n if (i\u0026mask)\r\n q[0] \u002B= q[1];\r\n else\r\n q[1] \u002B= q[0];\r\n i = i \u0026 (~mask);\r\n mask \u003E\u003E= 1;\r\n }\r\n return q;\r\n}\r\n/**\r\n * rational number of rank @i (using Stern diatonic sequence order)\r\n * @returns {Array} - [num, den]\r\n *\r\n * iterative version\r\n * O(log(n)) time\r\n * O(1) space\r\n */\r\nfunction sternR4(i){\r\n let q = [0,1];\r\n let mask = 1;\r\n for (let j = i\u003E\u003E1; j; j \u003E\u003E=1) {\r\n mask \u003C\u003C= 1;\r\n }\r\n while (mask) {\r\n if (i\u0026mask)\r\n q[0] \u002B= q[1];\r\n else\r\n q[1] \u002B= q[0];\r\n i = i \u0026 (~mask);\r\n mask = mask \u003E\u003E1;\r\n }\r\n return q;\r\n}\r\n \r\n/**\r\n * i-ranked term of Stern diatonic sequence\r\n */\r\nfunction stern(i){\r\n return sternR(i)[0];\r\n //return sternQ(i)[0];\r\n}\r\n\r\nvar n = 6000;","TestCases":[{"Name":"tail-end recursion (ascending)","Code":"sternR_rec(n);","IsDeferred":false},{"Name":"iterative (descending)","Code":"sternR(n);","IsDeferred":false},{"Name":"iterative (descending) #2","Code":"sternR2(n);","IsDeferred":false},{"Name":"iterative (descending) #3","Code":"sternR3(n);","IsDeferred":false},{"Name":"iterative (descending) #4","Code":"sternR4(n)","IsDeferred":false}]}