[math-fun] 'Rationalize' a vector of real numbers ?
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 ?
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 ?
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 -- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com
On 7/23/13, Mike Stay <metaweta@gmail.com> 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 --
[Oops--- there goes the carpet again.] The authors seem completely unaware of the existing literature on MDCF (Multidimensional Continued Fractions), Lattice Basis Reduction, Diophantine Approximation etc. There are a number of algorithms besides LLL, with implementations built into Mathematica, Maple etc. See eg. http://en.wikipedia.org/wiki/Lenstra%E2%80%93Lenstra%E2%80%93Lov%C3%A1sz_lat... http://ocw.mit.edu/courses/mathematics/18-409-topics-in-theoretical-computer... I haven't managed to make sense of the "bifurcating" scripts at a quick glance; but it's worth remembering that "MDCF" algorithms --- which attempt directly to generalise continued fractions in some kind of mechanistic fashion --- invariably fail to converge in general. Fred Lunnon
On Tue, Jul 23, 2013 at 5:05 PM, Fred lunnon <fred.lunnon@gmail.com> wrote:
On 7/23/13, Mike Stay <metaweta@gmail.com> 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 --
[Oops--- there goes the carpet again.]
The authors seem completely unaware of the existing literature on MDCF (Multidimensional Continued Fractions), Lattice Basis Reduction, Diophantine Approximation etc.
That is true. That said, they have some really nice parallels to normal continued fractions that I haven't seen in other higher-order CFs. The cubic continued fraction algorithm approximates a pair of numbers (alpha, beta) with a pair of sequences of integers. One can use these terms to find triples (a_n, b_n, c_n) such that lim a_n n->inf --- = alpha c_n lim b_n n->inf --- = beta c_n At least one of the sequences terminate if alpha or beta is rational. If both sequences repeat, then alpha and beta are solutions to a pair of cubic equations. alpha_n is a positive integer for n>0; beta_n is a nonnegative integer. The algorithm is as follows: alpha'_0= alpha beta'_0 = beta alpha_n = [alpha'_n] beta_n = [beta'_n] alpha'_{n+1} = 1 / (beta'_n - [beta'_n]) beta'_{n+1} = (alpha'_n - [alpha'_n]) / (beta'_n - [beta'_n]) where [x] is greatest integer less than x. To find the nth covergent, take a_n = alpha_n b_n = beta_n c_n = 1 a_{n-1} = alpha_{n-1} a_n + b_n b_{n-1} = beta_{n-1} a_n + c_n c_{n-1} = a_n The determinant |a_n a_{n-1} a_{n-2}| |b_n b_{n-1} b_{n-2}| = 1 |c_n c_{n-1} c_{n-2}| My interest in them was to see if there was a similar continued fraction algorithm for factoring; with the usual continued fractions, the magnitude of the square of the numerator of the convergents is within 2sqrt(N) of a multiple of N. Here, instead of sqrt(N), it's N^{2/3}: Let x=n^(1/3). a_i/c_i -> x^2, b_i/c_i -> x, w = complex root of 1, w^2=-w |a_i b_i x c_i x^2| |b_i x c_i x^2 a_i | |c_i x^2 a_i b_i x | = |a_i^3 + b_i^3 x^3 + c_i^3 x^6 - 3a_i b_i c_i x| = c_i^3 |1 x^2 + 1 b_i/c_i x + 1 a_i/c_i| |1 x^2 + w b_i/c_i x - w a_i/c_i| |1 x^2 - w b_i/c_i x + w a_i/c_i| <= c_i^3 3 x^2 1/c_{i+1} 1/c_{i+2} <= 3 x^2 Let S be the set of numbers expressible in the form a x^2 + b x + c where a,b,c, are integers. It is self-evident that if y,z are elements of S, then yz is also an element of S. The determinant above acts like a kind of norm for S. Similar determinants exist for higher-order BCFs as well.
There are a number of algorithms besides LLL, with implementations built into Mathematica, Maple etc. See eg.
These will get you far better denominators than BCFs. -- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com
participants (3)
-
Fred lunnon -
Henry Baker -
Mike Stay