30:T410,Plot.plot({ title: target.desc || target.txt, marginBottom: 60, x: { type: "log", grid: true, label: "Denominator 𝑑" }, y: { type: "log", grid: true, label: "Score 𝜀 · 𝑑", }, marks: [ Plot.line(data, {x: [Math.max(2, x[0]), x.at(-1)], y: [1/Math.max(2, x[0]), 1/x.at(-1)], stroke: "red", strokeDasharray: [3, 5], strokeWidth: 1}), Plot.line(data.slice(0, LINE_GRAPH_LIMIT), {x: "d", y: "score", strokeWidth: 1.5, curve: "step"}), Plot.ruleX(data_decimated, {x: "d", y1: "max_score", y2: "min_score", strokeLinecap: "round", strokeWidth: 1.5}), Plot.dot(data_tips , {x: "d", y: "score"}), Plot.text(data_filtered , { x: "d", y: d => d.score * .4, text: d => `${d.n}⁄${d.d}`, fontSize: 18, frameAnchor: "bottom", dy: -3 }), Plot.tip(data_tips, Plot.pointer( {x: "d", y: "score", dy: 3, textPadding: 5, anchor: "top", title: d => `Fraction: ${d.n}⁄${d.d}\nGood: ${d.good.toFixed(1)}`})) ] })31:[] 2d:{"title":"Rational approximations","cells":[{"id":0,"value":"# Rational approximations\n\nHow good are rational approximations of various types of numbers? This is the [Approximation game from lcamtuf’s thing](https://lcamtuf.substack.com/p/approximation-game).\n\nFor rational numbers the rule is that the approximation must be different from the actual number.","pinned":false,"hidden":false,"mode":"md"},{"id":9,"value":"viewof target = Inputs.radio(options, {label: \"Select one\", value: options[0], format: o => o.txt})","pinned":false,"hidden":false,"mode":"ojs"},{"id":211,"value":"viewof max_d = Inputs.radio([1e4, 1e5, 1e6, 1e7], {label: \"Max d\", value: 1e4, format: n => n > 1e6 ? `${n.toLocaleString()} (⚠️ slow)`: n.toLocaleString()})","pinned":false,"hidden":false,"mode":"ojs"},{"id":22,"value":"$30","pinned":false,"hidden":false,"mode":"ojs"},{"id":249,"value":"

Target: ${target.value.toFixed(8)}

The fractions with the best ratio between the error and 1 / d ² are marked. Hover other data points below the 1 / d ² line to see more fractions.

","pinned":false,"hidden":false,"mode":"md"},{"id":12,"value":"options = [\n {txt: \"π\", value: Math.PI},\n {txt: \"e\", value: Math.E, desc: \"Natural exponential base e\"},\n {txt: \"φ\", value: 0.5 * (1 + Math.sqrt(5)), desc: \"Golden ratio φ\"},\n {txt: \"√2\", value: Math.SQRT2},\n {txt: \"∛2\", value: Math.cbrt(2)},\n {txt: \"√3\", value: Math.sqrt(3)},\n {txt: \"√5\", value: Math.sqrt(5)},\n {txt: \"√10\", value: Math.sqrt(10)},\n {txt: \"sin 1\", value: Math.sin(1.0), desc: \"Sine of 1 radian\"},\n {txt: \"sin 1°\", value: Math.sin(Math.PI / 180), desc: \"Sine of 1°\"},\n {txt: \"ln 2\", value: Math.log(2.0), desc: \"Solution to eˣ = 2\"},\n {txt: \"1/4\", value: 0.25},\n {txt: \"1/10\", value: 0.1},\n {txt: \"1/100\", value: 0.01},\n {txt: \"3.1400\", value: 3.1400, desc: \"3.14 decimal approximation of π\"},\n]","pinned":true,"hidden":false,"mode":"ojs"},{"id":280,"value":"first_decade = Math.max(1, Math.pow(10, Math.floor(-Math.log10(target.value))))","pinned":true,"hidden":false,"mode":"ojs"},{"id":15,"value":"x = Array.from({ length: max_d }, (_, i) => i + Math.max(1, Math.floor(0.500001 / target.value)));","pinned":true,"hidden":false,"mode":"ojs"},{"id":17,"value":"data = x.map(d => {\n const n_ideal = d * target.value;\n const n1 = Math.floor(n_ideal * (1 - 16 * Number.EPSILON));\n const n2 = Math.ceil(n_ideal * (1 + 16 * Number.EPSILON));\n const n = (n_ideal - n1 < n2 - n_ideal) ? n1 : n2;\n const err = Math.abs(n/d - target.value);\n return {\n d: d,\n n: n,\n score: err * d,\n good: d > 1 ? -Math.log(err) / Math.log(d) : 0\n }; \n});","pinned":true,"hidden":false,"mode":"ojs"},{"id":60,"value":"best_2 = data.reduce((a, b) => (a.score * a.d < b.score * b.d ? a : b))","pinned":true,"hidden":false,"mode":"ojs"},{"id":188,"value":"// plotting 1,000,000 data points the naive way is too slow, so\n// we only use a line mark for the first few, and then we use a\n// vertical bar mark for aggregated data points\nLINE_GRAPH_LIMIT = 3000","pinned":true,"hidden":false,"mode":"ojs"},{"id":185,"value":"data_decimated = {\n var data_decimated = [];\n var d1 = data[LINE_GRAPH_LIMIT].d;\n var min_score = 1;\n var max_score = 0;\n for (var i = LINE_GRAPH_LIMIT; i < x.length; ++i)\n {\n var {d, score} = data[i];\n min_score = Math.min(score, min_score);\n max_score = Math.max(score, max_score);\n if (d > d1 * 1.001)\n {\n data_decimated.push({d: 0.5 * (d + d1), min_score: min_score, max_score: max_score});\n min_score = 1;\n max_score = 0;\n d1 = d;\n }\n }\n return data_decimated;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":155,"value":"data_filtered = data.filter(d => (\n (d.good > 2.01 && d.score * d.d < best_2.score * best_2.d * 2) ||\n d.good > 3) && d.n > 0 && d.d > 1)","pinned":true,"hidden":false,"mode":"ojs"},{"id":229,"value":"function gcd(a, b) {\n // Ensure inputs are positive as GCD is typically defined for positive integers.\n a = Math.abs(a);\n b = Math.abs(b);\n while (b !== 0) {\n const temp = b;\n b = a % b;\n a = temp;\n }\n return a;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":220,"value":"data_tips = data.filter(d => d.good > 2 && d.n > 0 && d.d > 1 && gcd(d.d, d.n) == 1)","pinned":true,"hidden":false,"mode":"ojs"}],"files":"$W31","stdlib":"1","titling":"auto"}