Re: [math-fun] 'Rationalize' a vector of real numbers ?
I don't understand the connection with bifurcating continued fractions at all. I looked at the referenced papers, but I didn't see any discussion of approximating vectors of real numbers to minimize denominators. At 02:26 PM 7/23/2013, Mike Stay wrote:
Actually, it has to do with "cubic" continued fractions. See, e.g. Gupta & Mittal, "Bifurcating Continued Fractions" and Mittal & Gupta "Bifurcating Continued Fractions II". Both are available on the arxiv or here:
http://www.cs.auckland.ac.nz/~mike/maths/continued%20fractions/BCF1.pdf http://www.cs.auckland.ac.nz/~mike/maths/continued%20fractions/BCF2.pdf
On Tue, Jul 23, 2013 at 3:13 PM, Henry Baker <hbaker1@pipeline.com> wrote:
Various forms of 'rationalize' in Maxima & Common Lisp attempt to produce a rational number that approximates a given number but the magnitude of the rational's denominator is limited.
This problem can be easily solved with a continued fraction approximation.
The question now is how to 'rationalize' a _vector_ of given numbers, but do so with a single denominator.
In other words, I'd like to approximate the vector [x,y,z] with a rational vector [xn/d,yn/d,zn/d], where xn, yn, zn, d are all integers, but this rational vector is the _best possible_ with the given denominator bound.
The problem with rationalizing x, y, z individually is that the denominators might be so different that the overall denominator gets too big.
Also, we'd like to measure 'close' using the traditional Euclidean norm sqrt((x-xn/d)^2,(y-yn/d)^2,(z-zn/d)^2).
I would guess that the answer for 2D is Gaussian continued fractions, and that the answer for dimensions 3 & 4 has something to do with quaternion continued fractions ?
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
participants (2)
-
Henry Baker -
Simon Plouffe