Numeric Combinations of Pi and Sqrt(2)Date: 09/25/2005 at 15:03:19 From: anonymous Subject: Combinations of Pi and Sqrt(2) Say I am given a number X = A*[sqrt]2 + B*[pi], where A and B are integers. Given X, how can you find A and B? My immediate intuition was dot products, because whenever I see a function which is a linear combination of basis functions, I know I can take the dot product of the function with each basis function to get the coefficients of the linear combination. However, these are integral coefficients, and it doesn't make sense to say [pi] and [sqrt]2 are orthogonal functions. [pi] cannot be expressed as a rational multiple of [sqrt]2. So there is only one possible solution, if any. Is it true that for any [epsilon] > 0, [exists] integers A and B such that [epsilon] = A[pi] + B[sqrt]2? How to prove/disprove this? If it is true, then perhaps we can argue that the problem is uncomputable, because finding a solution would require infinite precision computations, and thus infinite time/space. A different, simpler, proof that numbers of the form (A[sqrt]2 + B[pi]) do not consist of all positive reals is simply to note that the set of such numbers is countable, while the positive reals are not. My thought is to find an integer B satisfying x[sup2] - 2B[pi]x + B[sup2][pi][sup2] [equiv] 0 mod 1. I may be wrong, but I suspect that if such a B exists, it has to be unique. Date: 09/25/2005 at 21:08:46 From: Doctor Vogler Subject: Re: Combinations of Pi and Sqrt(2) Hi Anonymous, Thanks for writing to Dr. Math. The answer to your question depends very much on what you know about x. If you know x exactly, then the answer to your question is almost certainly obvious, because x will probably be something like x = 2*sqrt(2) + 3*pi. But I'm guessing that you have x in decimal, as something like x = 12.25320508551556981299130759825790480973085194887921360927. In that case, I will tell you that there are either no solutions, or infinitely many solutions, and you are just looking for a *good* solution. So let's back up and look at a simpler problem. Suppose you have a number like 0.235294117647058823529411764705882352941176470588235294117647 and you think it's a rational number (indeed, it's 4/17) and want to figure out what the numerator and denominator should be. It turns out that there is a convenient way of doing this. You invert the number (1/x) and then subtract off the integer part, and repeat until you get zero. But here are the issues, and they are precisely the same issues that appear in your problem. There is an obvious answer to the above problem, not 4/17 but 235294117647058823529411764705882352941176470588235294117647 -------------------------------------------------------------. 1000000000000000000000000000000000000000000000000000000000000 Now consider why this is not as good an answer as 4/17. Notice that this answer is closer to the value that you started with. The problem, you see, is round-off error. You didn't start with infinitely many digits; you only started with (hopefully) enough to tell what the number is, which means it should be sufficiently more than the number of digits in the numerator and denominator of the solution you're looking for. Then when you find an answer that's close (like 4/17), you have to concede that it's not exact, but it's close enough. In particular, it's much closer than you would expect a random fraction of that size. For example, try to find a rational number that equals pi = 3.1415926... There are plenty of fractions (such as 22/7) that get close, but you'll find that you have to get very big numbers to get very close; this is what I mean by being "randomly close." If we start with a (supposedly) rational number, then we should expect our solution to be more than just randomly close. So perhaps you have a number x = A*sqrt(2) + B*pi, known to several digits, and you want to find small integers A and B that will be more than randomly close to your number x. Notice, first of all, that the right side of the equation is dense, in the sense that no matter what x value you pick, you can choose integers for A and B so that the right side will get the first ten million digits of x correct. But that's like the "obvious" solution to the rational number problem I gave above, not the kind of answer you're really looking for. You want small numbers A and B, compared to the number of digits of x (and r) that you have. In any case, much like the rational number problem, there are algorithms to find the numbers A and B. I won't describe them here. Instead, I'll tell you where you can find several of them. If you search MathWorld for the phrase integer relations at their search site http://mathworld.wolfram.com/search/ it will give you several links, including a description of what that phrase means at Integer Relation http://mathworld.wolfram.com/IntegerRelation.html and a list of several algorithms that can accomplish this task, with links to very short (and not very detailed) descriptions of those algorithms. But then you can search the Internet for one (or more) of these algorithms by name and find out how it works. I hope this helps. If you have any questions about this or need more help, please write back and show me what you have been able to do, and I will try to offer further suggestions. And happy searching! - Doctor Vogler, The Math Forum http://mathforum.org/dr.math/ Date: 09/26/2005 at 02:00:49 From: anonymous Subject: Thank you (Combinations of Pi and Sqrt(2) ) The links were quite helpful. Thank you. |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/