0
$\begingroup$

So I was writing a computer program, which is supposed to check whether $x$, an approximation of $\sqrt{a}$, is close enough to $\sqrt{x}$. Since these definitions aren't very precise, I defined "close enough" as $$\left|a - x^2\right| \le \dfrac{1}{10^{100}}$$ However my code involves division. Since doubles/floats do not give the desired precision, I had to use the BigDecimal class which requires the programmer to specify the decimal place to which it should round the answer. Originally, I put 100. This worked for my original case of $a = 2$. However, I realized that simply running the code once would not work. Running the code more than once wouldn't work either, because Java would optimize producing inaccurate results. I decided to run the code for all $1 \le a \le 100$. $100$ didn't work for 5, however, so I put 101. This worked for more values of $a$, but then stopped working. I had no idea how to choose the right value of $n$ at which to round to, which is why I am posing the question here.


Find the least positive integer $n$ such that the statement

"For all real numbers $x$, if $\left|\sqrt{a}-x\right| \le \dfrac{1}{10^n}$, then $\left|a - x^2\right| \le \dfrac{1}{10^{100}}$"

holds true for all integers $1 \le a \le 100$


$\endgroup$
1
  • $\begingroup$ You'll want to look at $|a^2 - x|$ in your entire post, or label $x$ the approximation of $\sqrt a$. $\endgroup$ – AlexR Dec 18 '13 at 22:22
1
$\begingroup$

Actually, including the little correction: $$\begin{align*} |\sqrt x - a| & \leq 10^{-n} \\ \Leftrightarrow |\sqrt x - a||\sqrt x + a| & \leq 10^{-n} |\sqrt x + a| \\ \Leftrightarrow |x - a^2| & \leq 10^{-n} |\sqrt x + a| \end{align*}$$ This gives us $$10^{-n} |\sqrt x + a| \leq 10^{-100}$$ Which depends on the number whose square root you want to approximate. If you take $a = \sqrt x$ (the "ideal"), you'd need $$n \approx 100 -\log_{10} (\frac1{2\sqrt x}) = 100 + \log_{10}(2) + \frac12 \log_{10} x$$

$\endgroup$
2
  • $\begingroup$ Well I want to approximate $\sqrt{2}$, $\sqrt{3}$, all the way up to $\sqrt{97}$ (or all square-free integers from $1$ to $100$) $\endgroup$ – user1380792 Dec 18 '13 at 22:47
  • $\begingroup$ Then use $x = 100$ in the approximation (to stay conservative). This would give $n \approx 100 + \log_{10} 2 + 1 < 102$. The problem is that this doesn't take rounding errors into account, so you can probably double that to be sure. $\endgroup$ – AlexR Dec 18 '13 at 22:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.