Anonymous user
Sturmian word: Difference between revisions
note on floor of square root
imported>CosmiaNebula No edit summary |
imported>CosmiaNebula (note on floor of square root) |
||
Line 16:
Stretch goal: calculate the Sturmian word for other kinds of definable real numbers, such as cubic roots.
The key difficulty is accurately calculating <math>floor(k\sqrt a) </math> for large <math>k</math>. Floating point arithmetic would lose precision. One can either do this simply by directly searching for some integer <math>a'</math> such that <math>a'^2 \leq k^2a < (a'+1)^2</math>, or by more trickly methods, such as first calculating the continued fraction representation of <math>\sqrt a</math>, then obtaining the convergent sequence to <math>\sqrt a</math>. Let <math>\frac mn </math> be a convergent to <math>\sqrt a</math>, such that <math>n \geq k</math>, then since the convergent sequence is the '''best rational approximant''' for denominators up to that point, we know for sure that, if we write out <math>\frac{0}{k}, \frac{1}{k}, \dots</math>, the sequence would stride right across the gap <math>(m/n, 2x - m/n)</math>. Thus, we can take the largest <math>l</math> such that <math>l/k \leq m/n</math>, and we would know for sure that <math>l = floor(k\sqrt a)</math>.
| |||