Re: [math-fun] 'Rationalize' a vector of real numbers ?
Wouldn't it be possible to pose this problem (for 2 real numbers) as an _integer linear programming_ problem, and aren't there pretty decent algorithms for such a relatively small integer programming problem? Of course, you would have to approximate the real numbers to some large number of digits -- perhaps 10 decimal digits (?) -- if you wanted to find the best rational approximations with max denominator < 10000. At 06:25 AM 7/24/2013, Simon Plouffe wrote:
Hello,
I made a lot of research in that area of approximation of 1 real by a vector of reals.
The thing is : There has been a lot of papers written on the generalisation of cont. frac. T - fractions , U -fractions, any_letter- fractions. one problem being that there are no natural way of doing that, well at least not any which is simple enough that will give the 'best possible ' approximation.
Let's say you have the simplest case where there is more than 1 number to approximate by real numbers, take pi and e or exp(1),
if we ask what is the best rational approximation to both of them at the same time , well there is no clear answer,
One simple algorithm is this one :
for example take 2 numbers a and b
in pseudo - code :
do { | a - b | } = c a <-- b b <-- c od
So this will find X, Y, Z such that
aX + bY + Z = 0
or said differently, you find 2 integers mutiplied by (in this example) by Pi and E so that the error is as small as possible
If you do a couple of iterations then one can find : 9257454 * E - 5824723 * pi = 6865462
BUT this example is not very good , with LLL or PSLQ it is possible to find smaller integers that will give a better approximation and this is the whole point. There are many ways to do that,
When you have a vector of reals then there are many- many possible ways.
if you look at the Maple doc. on ?kronecker or ?numtheory[minkowski]
the algorithms shown are interesting in a sense that it adresses the problem without necessarly finding the best answer. ...
Best regards
Simon plouffe
The paper on LLL I cited earlier mentions integer linear programming as one of its applications. WFL On 7/24/13, Henry Baker <hbaker1@pipeline.com> wrote:
Wouldn't it be possible to pose this problem (for 2 real numbers) as an _integer linear programming_ problem, and aren't there pretty decent algorithms for such a relatively small integer programming problem?
Of course, you would have to approximate the real numbers to some large number of digits -- perhaps 10 decimal digits (?) -- if you wanted to find the best rational approximations with max denominator < 10000.
At 06:25 AM 7/24/2013, Simon Plouffe wrote:
Hello,
I made a lot of research in that area of approximation of 1 real by a vector of reals.
The thing is : There has been a lot of papers written on the generalisation of cont. frac. T - fractions , U -fractions, any_letter- fractions. one problem being that there are no natural way of doing that, well at least not any which is simple enough that will give the 'best possible ' approximation.
Let's say you have the simplest case where there is more than 1 number to approximate by real numbers, take pi and e or exp(1),
if we ask what is the best rational approximation to both of them at the same time , well there is no clear answer,
One simple algorithm is this one :
for example take 2 numbers a and b
in pseudo - code :
do { | a - b | } = c a <-- b b <-- c od
So this will find X, Y, Z such that
aX + bY + Z = 0
or said differently, you find 2 integers mutiplied by (in this example) by Pi and E so that the error is as small as possible
If you do a couple of iterations then one can find : 9257454 * E - 5824723 * pi = 6865462
BUT this example is not very good , with LLL or PSLQ it is possible to find smaller integers that will give a better approximation and this is the whole point. There are many ways to do that,
When you have a vector of reals then there are many- many possible ways.
if you look at the Maple doc. on ?kronecker or ?numtheory[minkowski]
the algorithms shown are interesting in a sense that it adresses the problem without necessarly finding the best answer. ...
Best regards
Simon plouffe
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Yes, and no. Yes the problem can be done with HSG (high speed guessing) easily on a computer using linear programming techniques or equivalent. BUT : the current LLL-PSLQ algorithms do have a long history: The first versions of PSLQ was based on one article of a certain Ferguson ( et al ?) at the time the cost of computation was of the order of n^8 , nowaday, this is far better. Some of the readers of this group are experts in this domain. I recall that the PSLQ integer relation algorithm was based on 1 famous algorithm of linear algebra not trivial at all from a certain Dongarra and a lot of work was made on it to finaly come up with something that can attack simple questions concerning real numbers like : Is the Madelung Constant (the NACL constant) is made of simple numbers, like log(2), log(Pi) , etc. Is gamma , exp(1) and Pi linearly independant ? Is there a simple integer relation between the first non-trivial zeros of the Zeta function ? (I tested that one, does not work apparently). Best regards. Simon plouffe
If an algebraic number is a Salem number, or a Pisot number, or something like that, then it's the principal eigenvalue of some integer matrix. And you can efficiently raise a matrix to a high power by repeated squaring. So this should give an efficient way to approximate such a number by rational numbers. Jim Propp On Wed, Jul 24, 2013 at 11:08 AM, Simon Plouffe <simon.plouffe@gmail.com>wrote:
Yes, and no.
Yes the problem can be done with HSG (high speed guessing) easily on a computer using linear programming techniques or equivalent. BUT : the current LLL-PSLQ algorithms do have a long history: The first versions of PSLQ was based on one article of a certain Ferguson ( et al ?) at the time the cost of computation was of the order of n^8 , nowaday, this is far better.
Some of the readers of this group are experts in this domain. I recall that the PSLQ integer relation algorithm was based on 1 famous algorithm of linear algebra not trivial at all from a certain Dongarra and a lot of work was made on it to finaly come up with something that can attack simple questions concerning real numbers like :
Is the Madelung Constant (the NACL constant) is made of simple numbers, like log(2), log(Pi) , etc.
Is gamma , exp(1) and Pi linearly independant ?
Is there a simple integer relation between the first non-trivial zeros of the Zeta function ? (I tested that one, does not work apparently).
Best regards.
Simon plouffe _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Why should that process be "efficient", in the sense of minimising the denominator for given error bound? WFL On 7/24/13, James Propp <jamespropp@gmail.com> wrote:
If an algebraic number is a Salem number, or a Pisot number, or something like that, then it's the principal eigenvalue of some integer matrix. And you can efficiently raise a matrix to a high power by repeated squaring. So this should give an efficient way to approximate such a number by rational numbers.
Jim Propp
On Wed, Jul 24, 2013 at 11:08 AM, Simon Plouffe <simon.plouffe@gmail.com>wrote:
Yes, and no.
Yes the problem can be done with HSG (high speed guessing) easily on a computer using linear programming techniques or equivalent. BUT : the current LLL-PSLQ algorithms do have a long history: The first versions of PSLQ was based on one article of a certain Ferguson ( et al ?) at the time the cost of computation was of the order of n^8 , nowaday, this is far better.
Some of the readers of this group are experts in this domain. I recall that the PSLQ integer relation algorithm was based on 1 famous algorithm of linear algebra not trivial at all from a certain Dongarra and a lot of work was made on it to finaly come up with something that can attack simple questions concerning real numbers like :
Is the Madelung Constant (the NACL constant) is made of simple numbers, like log(2), log(Pi) , etc.
Is gamma , exp(1) and Pi linearly independant ?
Is there a simple integer relation between the first non-trivial zeros of the Zeta function ? (I tested that one, does not work apparently).
Best regards.
Simon plouffe _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On 7/24/13, Fred lunnon <fred.lunnon@gmail.com> wrote:
Why should that process be "efficient", in the sense of minimising the denominator for given error bound?
WFL
On 7/24/13, James Propp <jamespropp@gmail.com> wrote:
If an algebraic number is a Salem number, or a Pisot number, or something like that, then it's the principal eigenvalue of some integer matrix. And you can efficiently raise a matrix to a high power by repeated squaring. So this should give an efficient way to approximate such a number by rational numbers.
Jim Propp
On Wed, Jul 24, 2013 at 11:08 AM, Simon Plouffe <simon.plouffe@gmail.com>wrote:
Yes, and no.
Yes the problem can be done with HSG (high speed guessing) easily on a computer using linear programming techniques or equivalent. BUT : the current LLL-PSLQ algorithms do have a long history: The first versions of PSLQ was based on one article of a certain Ferguson ( et al ?) at the time the cost of computation was of the order of n^8 , nowaday, this is far better.
Some of the readers of this group are experts in this domain. I recall that the PSLQ integer relation algorithm was based on 1 famous algorithm of linear algebra not trivial at all from a certain Dongarra and a lot of work was made on it to finaly come up with something that can attack simple questions concerning real numbers like :
Is the Madelung Constant (the NACL constant) is made of simple numbers, like log(2), log(Pi) , etc.
Is gamma , exp(1) and Pi linearly independant ?
Is there a simple integer relation between the first non-trivial zeros of the Zeta function ? (I tested that one, does not work apparently).
Best regards.
Simon plouffe _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (4)
-
Fred lunnon -
Henry Baker -
James Propp -
Simon Plouffe