10

Given some $\epsilon>0$, is there an efficient way to find an integer $n$ such that $$1-\sin(n)<\epsilon$$

We all know there is always one (and many), and so I can test all $n$ from $0$ until I find a good candidate, but I ask for some efficient algorithm that given some $\epsilon$, computes quickly such an $n$.

Τίμων
  • 1,669
Xoff
  • 10,310
  • 4
    $\sin n$ is close to $1$ if $n$ is close to $\left(2k+\frac{1}{2}\right)\pi$ for some $k$, which happens if $\frac{n}{2k+\frac{1}{2}}$ is very close to $\pi$. The continued fraction expansion of $\pi$ thus gets you candidates. – Daniel Fischer Jan 07 '15 at 10:11
  • 2
    @DanielFischer does continued fraction converges quickly enough to give something good ? Because it must converges more quickly than $k$ is increasing to be of any help, as $n/(2k+1/2)$ converges to $\pi$, is $n$ converging to $\pi\times(2k+1/2)$ is another question. Even if it's true, if the convergence is very slow, it could be quicker to use the naive algorithm. – Xoff Jan 07 '15 at 10:27
  • 2
    If $\frac{p}{q}$ is a convergent (of the continued fraction expansion) of $\xi$ (which shall be irrational), then you have $\lvert\frac{p}{q}-\xi\rvert <\frac{1}{q^2}$, so $\lvert p-q\xi\rvert <\frac{1}{q}$. So if $\frac{2n}{4k+1}$ is a convergent of $\pi$, you have $\lvert n-\left(2k+\frac{1}{2}\right)\pi\rvert <\frac{1}{8k+2}$, which is good enough. The problem is of course that to get far in the continued fraction expansion of $\pi$, you need to compute $\pi$ with high accuracy. But it's still better than the naive way if you use a good algorithm to compute $\pi$. – Daniel Fischer Jan 07 '15 at 10:40
  • @DanielFischer you're right, and should probably put that in an answer to that question. Can we use some regular continued fraction of $\pi$ like the one in http://functions.wolfram.com/Constants/Pi/10/ . Hence you don't need to compute $\pi$ ? – Xoff Jan 07 '15 at 10:45
  • I only know how well the simple continued fraction expansions (all numerators $1$) converge. If they converge fast enough, you can also use an expansion like $$\pi = 3 + \cfrac{1}{6 + \cfrac{9}{6+\cfrac{25}{6+\ddots}}},$$ but I don't know how good the convergence of such non-simple continued fractions is. – Daniel Fischer Jan 07 '15 at 11:18
  • 1
    Possibly helpful answer: http://mathoverflow.net/a/184223/10423 – Kirill Jan 07 '15 at 20:47

1 Answers1

2

Consider the Taylor series of $\sin(x)$ around $\left(2k + \frac{1}{2}\right) \pi$, \begin{align*} \sin\left(\left(2k + \frac{1}{2}\right)\pi + x\right) &= 1 - \frac{x^2}{2} + \frac{x^4}{24} - \ldots \\ &\le 1 - \frac{x^2}{2} \end{align*} as it is reasonably clear that $\frac{x^4}{24} - \frac{x^6}{120} + \ldots > 0$ for a small $x$.

So if we want $1 - \sin(n) < \epsilon$ then consider $n = \left(2k + \frac{1}{2}\right)\pi + x$, we thus obviously require $$ \left| n - \left(2k + \frac{1}{2}\right)\pi \right| < \sqrt{2 \epsilon}. $$ As pointed out above, this is equivalent to finding a rational approximation $\frac{2n}{4k + 1}$, which if furthermore is the convergent of a continued fraction approximation, we get $$ \left| n - \left(2k + \frac{1}{2}\right)\pi \right| < \frac{1}{8k+2} $$ for free.

Now, there are continued fraction formulae that do not require the knowledge of $\pi$, for example Stern's formula $$ \frac{\pi}{2} = 1 - \frac{1}{3 - \frac{2\cdot 3}{1 - \frac{1\cdot 2}{3 - \frac{4\cdot5}{1 - \frac{3\cdot 4}{3 - \frac{6\cdot7}{1 - \cdots } } } }}}, $$ which can give you a sequence of rational approximations of $\frac{\pi}{2}$. The sequences of convergents and their numerators OEIS A001901 and denominators OEIS A046126 for this can be found, and effectively all you have to do now, as we are considering $\pi/2$ i.e. $2n$ doesn't matter any more, is find a denominator of the form $4k+1$ such that $\frac{1}{8k+2} < \sqrt{2\epsilon}$, and the corresponding $2n$ in the numerator gives our answer.

occassional user
  • 156