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