[math-fun] Equation mixing integers and reals
Let f(x , x , ..., x ) = k x + k x + ... + k x 1 2 n 1 1 2 2 n n where k , k , ..., k are n REAL constants 1 2 n and x , x , ..., x are n INTEGERS (positive or negative) 1 2 n If we try to have the best possible approximations of f(x , x , ... x ) = 0 1 2 n do you know good algorithms giving best values of (x , x , ..., x )? 1 2 n When n = 2, a good algorithm is to compute the continued fraction of k / k 2 1 At each step of the algorithm, the continued fraction will give more and more excellent (x , x ). 1 2 But which algorithm(s) for n > 2? Christian.
Isn't this similar to the "integer linear programming" problem (integer version of linear programming problem) ? It looks like you may be able to reduce this to some sort of knapsack problem. Of course, there's always the issue of how to represent the "reals" in this problem. At 06:42 AM 9/16/2008, Christian Boyer wrote:
Let f(x , x , ..., x ) = k x + k x + ... + k x 1 2 n 1 1 2 2 n n
where k , k , ..., k are n REAL constants 1 2 n
and x , x , ..., x are n INTEGERS (positive or negative) 1 2 n
If we try to have the best possible approximations of
f(x , x , ... x ) = 0 1 2 n
do you know good algorithms giving best values of (x , x , ..., x )? 1 2 n
When n = 2, a good algorithm is to compute the continued fraction of k / k 2 1 At each step of the algorithm, the continued fraction will give more and more excellent (x , x ). 1 2
But which algorithm(s) for n > 2?
Christian.
This polynomial: x^4 - 48*x^3 - 12*x^2 - 33*x + 1613 has a root very near Pi. How can I know if this is unusual for the size of the coefficients? -- I think that it is. I suppose this problem is in the category you describe -- but sorry I don't know how to do it. Jim On Tue, Sep 16, 2008 at 8:42 AM, Christian Boyer <cboyer@club-internet.fr> wrote:
Let f(x , x , ..., x ) = k x + k x + ... + k x 1 2 n 1 1 2 2 n n
where k , k , ..., k are n REAL constants 1 2 n
and x , x , ..., x are n INTEGERS (positive or negative) 1 2 n
If we try to have the best possible approximations of
f(x , x , ... x ) = 0 1 2 n
do you know good algorithms giving best values of (x , x , ..., x )? 1 2 n
When n = 2, a good algorithm is to compute the continued fraction of k / k 2 1 At each step of the algorithm, the continued fraction will give more and more excellent (x , x ). 1 2
But which algorithm(s) for n > 2?
Christian.
participants (3)
-
Christian Boyer -
Henry Baker -
James Buddenhagen