1
$\begingroup$

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.

*Update*

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.

$\endgroup$
10
  • $\begingroup$ Surely you mean the coefficients are between $-2^{31}$ and $2^{31}-1$? $\endgroup$
    – TonyK
    Commented Jan 10, 2013 at 16:42
  • $\begingroup$ Yes sorry. Silly mistake. Fixed now. $\endgroup$
    – hatch22
    Commented Jan 11, 2013 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
    Commented Jan 11, 2013 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
    Commented Jan 13, 2013 at 2:37
  • $\begingroup$ @Erick, can you explain how you are estimating your rough guess? $\endgroup$
    – hatch22
    Commented Jan 13, 2013 at 2:52

1 Answer 1

Reset to default
1
$\begingroup$

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?

$\endgroup$
3
  • $\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
    Commented Jan 13, 2013 at 2:42
  • $\begingroup$ I do see that $2^{-35} \times 2^{-31} = 2^{-66}$ $\endgroup$
    – hatch22
    Commented Jan 13, 2013 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
    Commented Jan 13, 2013 at 3:27

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .