2b:null 2c:["$","title",null,{"children":"Rational Approximation | Christophe Yamahata | Observable"}] 31:T5e2,{ const lowerBound = approximation.lastLowerNumFactors.reduce((a, b) => a * b, 1) / approximation.lastLowerDenFactors.reduce((a, b) => a * b, 1); const upperBound = approximation.lastUpperNumFactors.reduce((a, b) => a * b, 1) / approximation.lastUpperDenFactors.reduce((a, b) => a * b, 1); return html`
After ${approximation.results.length} iterations, the approximation of ${target==initial_value? "S": "R"} = ${target} is refined to:

${tex` \large \begin{array}{rcccll} \frac{${approximation.lastLowerNumFactors.reduce((a, b) => a * b, 1).toLocaleString()}}{${approximation.lastLowerDenFactors.reduce((a, b) => a * b, 1).toLocaleString()}} & ${lowerBound == target? "=" : "<"} & \small ${target} & ${upperBound == target? "=" : "<"} & \frac{${approximation.lastUpperNumFactors.reduce((a, b) => a * b, 1).toLocaleString()}}{${approximation.lastUpperDenFactors.reduce((a, b) => a * b, 1).toLocaleString()}}, & \small \text{which rewrites:} \\[10pt] \frac{${formatFactorsForTeX(approximation.lastLowerNumFactors)}}{${formatFactorsForTeX(approximation.lastLowerDenFactors)}} & ${upperBound == target? "=" : "<"} & \small ${target} & ${lowerBound == target? "=" : "<"} & \frac{${formatFactorsForTeX(approximation.lastUpperNumFactors)}}{${formatFactorsForTeX(approximation.lastUpperDenFactors)}} & \small \text{using prime factorization.} \end{array} `}

` }32:T489,md` | Iteration | Lower bound | Upper bound | Mediant | |-----------|-------------|-------------|---------| ${approximation.results.map(row => `| ${row.iteration} | ${row.lower} | ${row.upper} | ${row.mediant} |` ).join('\n')} ${(() => { const lastRow = approximation.results[approximation.results.length - 1]; const lastRowMediant = lastRow.mediant; const [numerator, denominator] = lastRowMediant.split('/').map(Number); const mediantValue = numerator / denominator; let newLower, newUpper; if (mediantValue < target) { newLower = lastRowMediant; newUpper = lastRow.upper; } else if (mediantValue > target) { newLower = lastRow.lower; newUpper = lastRowMediant; } else { newLower = lastRowMediant; newUpper = lastRowMediant; } const [lowerNum, lowerDen] = newLower.split('/').map(Number); const [upperNum, upperDen] = newUpper.split('/').map(Number); const newMediantNum = lowerNum + upperNum; const newMediantDen = lowerDen + upperDen; return `| ${lastRow.iteration + 1} | ${newLower} | ${newUpper} | ${mediantValue == target ? "–" : `${newMediantNum}/${newMediantDen}`} |`; })()} `33:T90a,mediantApproximation = (target, maxIterations, maxDenominator) => { if (isNaN(target) || target <= 0) { return { results: [], lastLowerNumFactors: [NaN], lastLowerDenFactors: [NaN], lastUpperNumFactors: [NaN], lastUpperDenFactors: [NaN] }; } let bounds = { lower: { num: Math.floor(target), den: 1 }, upper: { num: Math.ceil(target), den: 1 } }; let results = []; let lastLowerNumFactors = primeFactors(bounds.lower.num); let lastLowerDenFactors = primeFactors(bounds.lower.den); let lastUpperNumFactors = primeFactors(bounds.upper.num); let lastUpperDenFactors = primeFactors(bounds.upper.den); for (let i = 0; i < maxIterations; i++) { const mediant = { num: bounds.lower.num + bounds.upper.num, den: bounds.lower.den + bounds.upper.den }; const A_primeFactors = primeFactors(mediant.num); const B_primeFactors = primeFactors(mediant.den); const [A_reduced, B_reduced] = reduceFraction(A_primeFactors, B_primeFactors); const simplifiedNum = A_reduced.reduce((a, b) => a * b, 1); const simplifiedDen = B_reduced.reduce((a, b) => a * b, 1); const mediantValue = simplifiedNum / simplifiedDen; if (simplifiedDen > maxDenominator) { break; } results.push({ iteration: i, lower: `${bounds.lower.num}/${bounds.lower.den}`, upper: `${bounds.upper.num}/${bounds.upper.den}`, mediant: `${simplifiedNum}/${simplifiedDen}`, mediantNumFactors: A_reduced, mediantDenFactors: B_reduced, value: mediantValue, error: mediantValue - target }); if (mediantValue < target) { bounds.lower = { num: simplifiedNum, den: simplifiedDen }; lastLowerNumFactors = A_reduced; lastLowerDenFactors = B_reduced; } else if (mediantValue > target) { bounds.upper = { num: simplifiedNum, den: simplifiedDen }; lastUpperNumFactors = A_reduced; lastUpperDenFactors = B_reduced; } else { lastLowerNumFactors = A_reduced; lastLowerDenFactors = B_reduced; lastUpperNumFactors = A_reduced; lastUpperDenFactors = B_reduced; break; } } return { results, lastLowerNumFactors, lastLowerDenFactors, lastUpperNumFactors, lastUpperDenFactors }; }34:[] 2f:{"id":"b2e2fb7b6fb3fead","slug":"rational-approximation","title":"Rational Approximation","thumbnail":"47008d10f5217dedb42e3be101f8b1f3de8bee1c1c5b056fc1a838be1d3397e1","access_level":"public","create_time":"$D2025-03-25T14:05:30.756Z","update_time":"$D2025-03-25T23:37:21.095Z","view_time":null,"first_public_time":"$D2025-03-25T16:51:51.491Z","fork":false,"stars":0,"starred":false,"owner":{"type":"team","id":"dd67891d326bcfb1","login":"christophe-yamahata","name":"Christophe Yamahata","avatar_url":"https://avatars-next.observableusercontent.com/8256ac716aa8395babba412b2835913d186874fa4190df57a4a28f2e60129876","tier":"starter_2024"},"version":459,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"06f083eba60f5a76","login":"christophe-yamahata","name":"Christophe Yamahata","avatar_url":"https://avatars-next.observableusercontent.com/8256ac716aa8395babba412b2835913d186874fa4190df57a4a28f2e60129876","tier":null}],"members":[{"type":"individual","id":"06f083eba60f5a76","login":"christophe-yamahata","name":"Christophe Yamahata","avatar_url":"https://avatars-next.observableusercontent.com/8256ac716aa8395babba412b2835913d186874fa4190df57a4a28f2e60129876","tier":null,"role":"editor"},{"type":"team","id":"dd67891d326bcfb1","login":"christophe-yamahata","name":"Christophe Yamahata","avatar_url":"https://avatars-next.observableusercontent.com/8256ac716aa8395babba412b2835913d186874fa4190df57a4a28f2e60129876","tier":"starter_2024","role":"editor"}],"comments":[],"custom_thumbnail":true,"trashed":false,"subscribed":null,"forks":0,"collection":{"id":"19262496cb287a16","slug":"mathematics","title":"Mathematics","owner":{"id":"dd67891d326bcfb1","login":"christophe-yamahata","name":"Christophe Yamahata"}},"type":"notebook","body":{"title":"Rational Approximation","cells":[{"id":0,"value":"# Rational Approximation\n\nThis notebook allows you to approximate a positive real number by a rational number using mediant inequality.\nThe process iteratively refines bounds by computing mediants and simplifies fractions through prime factorization of numerators and denominators.\n\n---","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":348,"value":"{\n if(target==initial_value) {\n return html`\nAs an example, we initialize with the Moon's synodic month, which is approximately:\n
S = ${initial_value} (29 days, 12 hours, 44 minutes, and 2.8 seconds).\n

\n `\n } else {\n return html`\nHereafter, the rational approximation is computed for the real number \n
R = ${target} introduced in the input field.\n

\n`\n }\n}\n\n\n","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":7,"value":"viewof target = Inputs.text({ \n label: \"Real positive number:\", \n value: initial_value.toString(), \n submit: false,\n pattern: \"[0-9]*\\\\.?[0-9]*\" \n}, v => {\n const num = parseFloat(v);\n return num;\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":61,"value":"viewof maxDenominator = Inputs.select([10, 100, 1000, 10000, 100000, 1000000, 10000000], { value: 100, label: \"Max. denominator value:\" })","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":57,"value":"viewof maxIterations = Inputs.range([10, 1000], {value: 100, step: 10, label: \"Max. iterations:\"})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":40,"value":"$31","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":334,"value":"
\nThe table below lists the intermediate values calculated during the approximation process. Each row shows the iteration number, the lower and upper bounds, and the mediant fraction that narrows the range around the target value (${target==initial_value? \"S\": \"R\"} = ${target}).","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":331,"value":"$32","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":84,"value":"---","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":5,"value":"## Appendix","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":9,"value":"initial_value = 29.530588 // Math.PI","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":33,"value":"approximation = mediantApproximation(target, maxIterations, maxDenominator)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":21,"value":"primeFactors = (n) => {\n if (n < 2) return [n];\n const factors = [];\n let divisor = 2;\n while (n >= 2) {\n if (n % divisor === 0) {\n factors.push(divisor);\n n = n / divisor;\n } else {\n divisor++;\n }\n }\n return factors;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":24,"value":"reduce_array = (array_in, index) => {\n const array_out = array_in.slice();\n array_out.splice(index, 1);\n return array_out;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":27,"value":"reduceFraction = (A_primeFactors, B_primeFactors) => {\n let A_reduced = A_primeFactors.slice();\n let B_reduced = B_primeFactors.slice();\n for (let i = 0; i < A_reduced.length; i++) {\n let j = 0;\n while (j < B_reduced.length) {\n if (A_reduced[i] === B_reduced[j]) {\n A_reduced = reduce_array(A_reduced, i);\n B_reduced = reduce_array(B_reduced, j);\n i--;\n break;\n } else {\n j++;\n }\n }\n }\n return [A_reduced, B_reduced];\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":134,"value":"formatFactorsForTeX = (factors) => {\n if (factors.length === 0) return \"1\";\n if (factors.length === 1) return factors[0].toString();\n \n const factorCounts = {};\n factors.forEach(f => {\n factorCounts[f] = (factorCounts[f] || 0) + 1;\n });\n \n return Object.entries(factorCounts)\n .map(([base, exp]) => exp > 1 ? `${base}^{${exp}}` : base)\n .join(\" \\\\times \");\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":30,"value":"$33","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"}],"files":"$W34","stdlib":"1","titling":"auto"}} 30:"$2f:body"