How much precision is needed to compare two sums of square roots of integers?

• Published in: Information processing letters 2006-12, Vol.100 (5), p.194-198
• Main Authors: Qian, Jianbo, Wang, Cao An
• Format: Article
• Language: English
• Subjects: Algorithmics. Computability. Computer arithmetics; Applied sciences; Artificial intelligence; Computational geometry; Computer science; control theory; systems; Exact sciences and technology; Geometry; Numbers; Numerical analysis; Numerical computations; Pattern recognition. Digital image processing. Computational geometry; Precision; Square root of integer; Studies; Theoretical computing
• ISSN: 0020-0190; 1872-6119
• DOI: 10.1016/j.ipl.2006.05.002

In this paper, we investigate the problem of the minimum nonzero difference between two sums of square roots of integers. Let r ( n , k ) be the minimum positive value of | ∑ i = 1 k a i − ∑ i = 1 k b i | where a i and b i are integers not larger than integer n. We prove by an explicit construction that r ( n , k ) = O ( n − 2 k + 3 / 2 ) for fixed k and any n. Our result implies that in order to compare two sums of k square roots of integers with at most d digits per integer, one might need precision of as many as ( 2 k − 3 2 ) d digits. We also prove that this bound is optimal for a wide range of integers, i.e., r ( n , k ) = Θ ( n − 2 k + 3 / 2 ) for fixed k and for those integers in the form of a i = ( 2 k − 1 2 i ) 2 ( n ′ + 2 i ) and b i = ( 2 k − 1 2 i + 1 ) 2 ( n ′ + 2 i + 1 ) , where n ′ is any integer satisfied the form and i is any integer in [ 0 , k − 1 ] . We finally show that for k = 2 and any n, this bound is also optimal, i.e., r ( n , 2 ) = Θ ( n − 7 / 2 ) .