I'm thinking about the problem of designing gear trains for a lego orrery which I'd like to be fairly accurate. The standard gear sizes are 8, 16, 24, 40, so I have ratios of 1:2:3:5 to work with. I figure that since lg(3) (where lg is log base 2) is irrational, you can get arbitrary accuracy out of a gear train. I think I need a + b lg(3) + c lg(5) ~= lg(period), with a, b, c small. Is LLL the right tool for solving this kind of thing? -- Mike Stay - metaweta@gmail.com http://math.ucr.edu/~mike http://reperiendi.wordpress.com
It seems to be what most people use in practice; though the reformulation in terms of lattices is a little indirect. In particular, the irrational ratios have to be replaced by (large) integer ratios. I don't have a reference easily to hand ---- but a web search for the original paper (Lenstra, Lenstra & Lov'acs) should turn one up. Personally, I prefer to use my own, non-kosher matrix-based algorithm, which seems to give useful results in practice --- even if I can't (be bothered to) prove it! Fred Lunnon On 9/11/09, Mike Stay <metaweta@gmail.com> wrote:
I'm thinking about the problem of designing gear trains for a lego orrery which I'd like to be fairly accurate. The standard gear sizes are 8, 16, 24, 40, so I have ratios of 1:2:3:5 to work with. I figure that since lg(3) (where lg is log base 2) is irrational, you can get arbitrary accuracy out of a gear train. I think I need a + b lg(3) + c lg(5) ~= lg(period), with a, b, c small. Is LLL the right tool for solving this kind of thing?
-- Mike Stay - metaweta@gmail.com http://math.ucr.edu/~mike http://reperiendi.wordpress.com
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Having caught up with some background reading http://mathworld.wolfram.com/IntegerRelation.html and discovered how far out-of-the-loop I was, it's time for third thoughts. The current jargon is apparently "Integer Relation Finding", and it turns out there's a pretty solid-looking but rather complex algorithm due to Ferguson et al from 1997 called PSLQ --- see Ferguson, H. R. P., Bailey, D. H., Arno, S. "Analysis of PSLQ, An Integer Relation Finding Algorithm." Math. Comput. 68, 351-369, 1999. [online as cpslq.pdf] [This garnered some publicity at the time when Plouffe and others used it in a surprising algorithm to extract digits from \pi, recently mentioned in this list, I seem to recall --- see Bailey, D. and Plouffe, S. "Recognizing Numerical Constants." http://www.cecm.sfu.ca/organics/papers/bailey/paper/html/paper.html] PSLQ is implemented in both Mathematica and Maple. I compared the Maple version with my home-grown geometrically-inspired "Umbrella" algorithm, only to discover that PSLQ detected the polynomial satisfied by a quadratic surd, using only half the precision required by Umbrella --- Umbrella retires, blown inside-out. All these algorithms have an inherent limitation: they detect only homogeneous relations (i.e. with RHS = 0) with integer coefficients, between a given bunch of reals; whereas the Lego orrery appears to demand a RHS equal to the gear ratio required to be approximated. I'm still thinking about this --- if only as a last-ditch attempt to salvage a little pride. Fred Lunnon
On 9/22/09, Fred lunnon <fred.lunnon@gmail.com> wrote:
... PSLQ is implemented in both Mathematica and Maple. I compared the Maple version with my home-grown geometrically-inspired "Umbrella" algorithm, only to discover that PSLQ detected the polynomial satisfied by a quadratic surd, using only half the precision required by Umbrella --- Umbrella retires, blown inside-out.
All these algorithms have an inherent limitation: they detect only homogeneous relations (i.e. with RHS = 0) with integer coefficients, between a given bunch of reals; whereas the Lego orrery appears to demand a RHS equal to the gear ratio required to be approximated. I'm still thinking about this --- if only as a last-ditch attempt to salvage a little pride.
Mature reflection suggests that GAMP [as I'm thinking of re-christening the umbrella algorithm, just to keep up with MDCF, PSOS, HJLS, PSLQ, ...] only needed twice as many digits as PSLQ in tests, because I hadn't bothered to evaluate inner products with double precision, as any serious implementation should. Casual inspection might suggest that the inhomogeneous problem (the RHS might just as well be unity) should only involve some fairly trivial modification to the homogeneous problem. It seems to me that geometry gives some insight into this situation, so I'll take the liberty of describing GAMP briefly. The input target vector of real components to be rationally approximated is interpreted as a line in projective n-space joining the origin to the point at infinity with those coordinates. A `ratio' basis of n integer lattice points, regarded as vectors rooted at the origin, is initially set equal to the unit points on the Cartesian axes; as the algorithm progresses, its vectors fold ever more tightly around the line, like an umbrella closing around its shaft, in such a way that the volume of the enclosed parallelepiped remains unity, and their convex hull (as it were) continues to contains the line. Each member of the basis constitutes a rational approximation to the target vector; furthermore, since (Minkowski?) there can be no lattice points within the parallelepiped, the point at which the line emerges from it gives a lower bound on the length of any closer lattice point. At each iteration, the next vector in cyclic order is selected as candidate for improvement; its components with respect to the (non-Cartesian) basis comprising the target point, the origin, and the other n-1 vectors, are computed by inverting the matrix of that basis; then they are truncated to integers, and the corresponding linear combination subtracted from the candidate. Meanwhile the corresponding `relation' basis, the (Hodge) dual and matrix inverse of the ratio basis, yields progressively better approximate null linear combinations of the target reals. Termination is in practice easy to detect: either the candidate fails to improve, when an exact solution, or (nearly) best approximations given the precision, have been attained; or else it improves and lengthens wildly, when a relation will have been detected. Convergence takes place within at most d*log(10)/log(x) iterations, where d equals the decimal precision of the input, and x^n = x^(n-1) + ... + 1, with x ~ 2 - 1/2^n. Now then, an integer relation has a straightforward geometrical interpretation, as a prime flat (hyperplane) with integer coefficients, passing close to or meeting the target point; if the relation happens to be inhomogeneous, the prime simply fails to meet the origin as well. But there is then no apparent geometrical equivalent associated with its corresponding dual: rational approximate ratios are meaningful only for the homogeneous problem! This suggests that no obvious strategy, such as recasting GAMP to operate directly with the relation basis instead, can possibly succeed. I'm not at this stage sufficiently familiar with the other algorithms to comment on them; but I begin strongly to suspect that this difficulty is inherent. Perhaps the intelligent thing to do now would be to stop blathering on, and go and consult Ferguson ... Fred Lunnon
On second thoughts, this is just what's more usually referred to as "multidimensional continued fraction" --- googling which turns up a great raft of references, some of them remarkably recent. For example Multidimensional continued fraction and rational approximation Dai, Zongduo; Wang, Kunpeng; Ye, Dingfeng arXiv:math/0401141v1 [math.NT] [free download] Tilings, Quasicrystals, Discrete Planes, Generalized Substitutions, and Multidimensional Continued Fractions Pierre Arnoux, Valerie Berthe, Hiromi Ei, Shunji Ito Discrete Mathematics and Theoretical Computer Science Proceedings AA (DM-CCG), 2001, 059–078 [free download as dmAA0104.pdf] Generation and recognition of digital planes using multi-dimensional continued fractions Thomas Fernique (2008) Multidimensional continued fractions Fritz Schweiger Oxford University Press, 2000 ISBN 0198506864, 9780198506867 234 pages [book] Surely this topic must have been discussed here before --- RWG in particular must have something to say about it! Fred Lunnon On 9/11/09, Mike Stay <metaweta@gmail.com> wrote:
I'm thinking about the problem of designing gear trains for a lego orrery which I'd like to be fairly accurate. The standard gear sizes are 8, 16, 24, 40, so I have ratios of 1:2:3:5 to work with. I figure that since lg(3) (where lg is log base 2) is irrational, you can get arbitrary accuracy out of a gear train. I think I need a + b lg(3) + c lg(5) ~= lg(period), with a, b, c small. Is LLL the right tool for solving this kind of thing?
-- Mike Stay - metaweta@gmail.com http://math.ucr.edu/~mike http://reperiendi.wordpress.com
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On 9/11/09, Mike Stay <metaweta@gmail.com> wrote:
I'm thinking about the problem of designing gear trains for a lego orrery which I'd like to be fairly accurate. The standard gear sizes are 8, 16, 24, 40, so I have ratios of 1:2:3:5 to work with. I figure that since lg(3) (where lg is log base 2) is irrational, you can get arbitrary accuracy out of a gear train. I think I need a + b lg(3) + c lg(5) ~= lg(period), with a, b, c small. Is LLL the right tool for solving this kind of thing?
After flailing around for a fortnight, I stubbed my toe on the key to the inhomogeneous box of delights while looking the other way, and am now left wondering how I failed to see it straight away. Example: Given [-log(7), log(2), log(3), log(5)] with 10 decimal digits, GAMP2 delivers [1, 55, -30, -2] --- the inner product equals -0.000059714. Of course, the feasibility of building a train of 88 Lego cogs for the sake of a 7:1 ratio to 4 decimal places is another question entirely ... All that was required was duality: instead of constructing lattice primes (hyperplanes) in n-space near to a real target point at infinity --- so locking into the homogeneous case --- simply map the input vector, complete with its nonzero RHS, to a real target prime --- passing through the origin when the problem is homogeneous, but not otherwise --- and construct nearby lattice points. Instead of furling an umbrella of points about a target shaft, GAMP2 proceeds by unfurling an umbrella of primes onto a target prime, with a crucial extra degree of freedom. After initialising a basis of lattice primes with the n coordinate primes and the prime at infinity, represented projectively by the order-(n+1) unit matrix, the algorithm rattles on almost as before: choose a candidate prime in cyclic order (excluding oo), temporarily swap it for the target prime, invert the resulting matrix and multiply by the candidate to obtain coordinates with respect to the modified basis, subtract the truncated (integer) combination from the candidate to yield a refined basis. Then iterate till converge, or shot down by rounding error in the input, in time linear in the precision. The extra twist is that the above stage refines only angles: the constant (RHS) component has to be adjusted separately, so that the refined lattice prime meets the target prime as close as possible to the foot of the perpendicular line from origin to target. Finally, invert the converged basis matrix into a dual basis of lattice points, the first of which lies close to the target prime; the other points approximate the homogeneous prime instead, but may be added to the first to yield a basis of (approximate) inhomogeneous relations. The in-radius of the (n-1)-space polytope, formed by the parallelotope of basis primes intersecting the target prime, is trivial to compute and gives a lower bound on the length of any potential exact relation which the existing precision is insufficient to detect --- the orrery application has no need of such bounds, which is just as well as these are disappointingly conservative. Fred Lunnon [01/10/09]
participants (2)
-
Fred lunnon -
Mike Stay