I have two numbers, $A$ and $B$, that are sums of integer multiples of a set of square roots of small primes (and 1) and their products:

$A = a_0 + a_1\sqrt 2 + a_2\sqrt 3 + a_3\sqrt 5 + a_4\sqrt 6 + a_5\sqrt{10} + a_6\sqrt{15} + a_7\sqrt{30}$

$B = b_0 + b_1\sqrt 2 + b_2\sqrt 3 + b_3\sqrt 5 + b_4\sqrt 6 + b_5\sqrt{10} + b_6\sqrt{15} + b_7\sqrt{30} $

I would like to be able to compare A and B by approximating the square roots with rational approximations based on an $n$th convergent from a continued fraction representation of each square root. I need to keep the accumulated error from these approximations less than $2^{-32}$, with each term contributing approximately the same amount of error. The results of the comparison need to be exact (the same as if the square roots were not approximated). Each coefficient $a_k$ and $b_k$ are between $-2^{31}$ and $2^{31} - 1$ (signed 32-bit integers). How do I go about finding convergents of sufficiently small error? I am inexperienced with both numerical analysis and Diophantine approximation I'm afraid.


I want to clarify that I'm not insisting on a continued fraction or rational number representation for the square roots. A binary fixed-point representation of sufficient accuracy is fine. I just want to be confident in the results of these comparisons by understanding how to evaluate and control the error.

I also want to clarify that it is alright for results that are very close to be counted as equal, but it is not alright for results that are very close to be counted as "less than" when they should be "greater than or equal" or vice versa.

  • $\begingroup$ Surely you mean the coefficients are between $-2^{31}$ and $2^{31}-1$? $\endgroup$ – TonyK Jan 10 '13 at 16:42
  • $\begingroup$ Yes sorry. Silly mistake. Fixed now. $\endgroup$ – hatch22 Jan 11 '13 at 22:22
  • $\begingroup$ In boundary cases, it's not at all clear that $2^{-32}$ error is small enough to obtain an exact comparison (my rough guess is that $2^{-224}$ might be needed). Is it absolutely necessary that the comparison be exact with no exceptions? $\endgroup$ – Erick Wong Jan 11 '13 at 23:00
  • $\begingroup$ It is necessary that the comparison be correct, not necessarily exact (meaning that even if the approximations are not exact/infinite precision, as long as the comparisons still give the correct results, that is acceptable. $\endgroup$ – hatch22 Jan 13 '13 at 2:37
  • $\begingroup$ @Erick, can you explain how you are estimating your rough guess? $\endgroup$ – hatch22 Jan 13 '13 at 2:52

Your expressions have eight terms, so each term must be accurate to within $2^{-35}$. The coefficient of each term can be as large as $2^{31}$ in absolute value, so your square roots must be accurate to within $2^{-66}$. So 64-bit arithmetic is not good enough.

Also, if you represent your square roots as fractions, you will have the nasty problem of adding eight fractions with different denominators. So this is probably not the way to do it.

If speed is important, some kind of customised fixed-point arithmetic may be indicated. What is your hardware platform?

  • $\begingroup$ Thank you for the response. Could you please explain where you are getting $2^{-35}$ and $2^{-66}$? I was considering a fixed point representation and multi-word arithmetic as an alternative to rational approximations, so thanks for the tip. As for hardware platform, standard desktop/notebook computer. Nothing embedded or anything like that. $\endgroup$ – hatch22 Jan 13 '13 at 2:42
  • $\begingroup$ I do see that $2^{-35} \times 2^{-31} = 2^{-66}$ $\endgroup$ – hatch22 Jan 13 '13 at 3:00
  • $\begingroup$ @hatch22 The $2^{-35}$ is just $2^{-32}/8$, since you wanted an accumulated accuracy of $2^{-32}$ across 8 summands. And $2^{-66}$ is, as you deduced, the allowable error in the square root before it is magnified by $a_k$. $\endgroup$ – Erick Wong Jan 13 '13 at 3:27

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.