[math-fun] Simultaneous rational approximation of two irrationals
If x is irrational, and I wish to best approximate the ratio x:1 by integers a:b, then I would use continued fractions. Suppose x and y are irrational, and I wish to best approximate the ratio x:y:1 by integers a:b:c. Is it known how to do this? __________________________________________________ Do you Yahoo!? Yahoo! Mail Plus - Powerful. Affordable. Sign up now. http://mailplus.yahoo.com
This is just the integer relation problem for n = 3. The integer relation problem for n = 2 is solvable by the standard Euclidean algorithm. For n = 3 one can use PSLQ, or suitably modified application of LLL. DHB -----Original Message----- From: math-fun-admin@mailman.xmission.com [mailto:math-fun-admin@mailman.xmission.com]On Behalf Of Eugene Salamin Sent: Sunday, December 08, 2002 3:04 PM To: math-fun@mailman.xmission.com Subject: [math-fun] Simultaneous rational approximation of two irrationals If x is irrational, and I wish to best approximate the ratio x:1 by integers a:b, then I would use continued fractions. Suppose x and y are irrational, and I wish to best approximate the ratio x:y:1 by integers a:b:c. Is it known how to do this? __________________________________________________ Do you Yahoo!? Yahoo! Mail Plus - Powerful. Affordable. Sign up now. http://mailplus.yahoo.com _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
At 03:04 PM 12/8/2002 -0800, Eugene Salamin wrote:
If x is irrational, and I wish to best approximate the ratio x:1 by integers a:b, then I would use continued fractions. Suppose x and y are irrational, and I wish to best approximate the ratio x:y:1 by integers a:b:c. Is it known how to do this?
Why not take c=1 and approximate x/y by a/b? (I don't see any loss of generality.) +---------------------------------------------------------+ | Jud McCranie | | | | Programming Achieved with Structure, Clarity, And Logic | +---------------------------------------------------------+
At 08:05 PM 12/8/2002 -0500, Jud McCranie wrote:
Why not take c=1 and approximate x/y by a/b? (I don't see any loss of generality.)
Whoops, maybe you can get a better approximation by using a general c. +-----------------------------------------------------------------+ | Jud McCranie | | | |"Thought I saw angels, but I could have been wrong." Ian Anderson| +-----------------------------------------------------------------+
If irrational x is approximated by rational p/r, and irrational y is approximated by rational q/r, then a hand-waving argument using information conservation shows that there should be lots of approximations good to order r^(-3/2). If we did not require the same r in both denominators, then it is known from continued fraction theory that we could do better, namely r^(-2). Suppose x and y are given with n bits each, for a total of 2n bits. Then integers p, q, r will have (2/3)n bits each. If the fractions are to be good to n bits, then the error is of order r^(-3/2). Is this conjecture known to be true (or false)? __________________________________________________ Do you Yahoo!? Yahoo! Mail Plus - Powerful. Affordable. Sign up now. http://mailplus.yahoo.com
participants (3)
-
David H Bailey -
Eugene Salamin -
Jud McCranie