|Re: A quickie: improve the HP 50g IABCUV function|
Message #5 Posted by Thomas Klemm on 2 Feb 2013, 10:03 a.m.,
in response to message #4 by David Hayden
The equation 11x + 13y = 765 describes a line. You can interpret the left hand side of the equation as a scalar product: (11, 13)(x, y) = 765. So you're looking for all the points (x, y) that have the same value when scalar multiplied with the vector (11, 13). These points are on a line that is perpendicular to the vector (11, 13). Or you just know the fact that the vector made of the coefficients is orthogonal to the line.
So I crosscut the line with the orthogonal line through the origin (0, 0): (x, y) = (11t, 13t) for a parameter t. Insert that into the equation of the line and solve for t. This will give you the exact solution: the point on the line which is closest to (0, 0).
Now for the closest integer solution you can just start with any of them like (66, 3). To get the other integer solutions you can just add multiples of the vector (13, -11). This vector is parallel to the line. So I'm trying to figure out which integer multiple of (13, -11) I have to add to (66, 3) to be as close as possible to the exact solution. You can find that factor based on x-coordinates or y-coordinates or even on the length of the vectors: you will always end up with the same factor.
Probably I should have solved the example of the initial post. Okay then, here we go:
Calculate exact solution
(x, y) = t (79, 179) as it is orthogonal to the line
t (792 + 1792) = 7319
38282 t = 7319
t = 0.1912
(x, y) = (15.10, 34.22)
Find closest integer solution
248846 + 179 k = 15.10
k = - 1390.12
Now round that to the closest integer:
k = - 1390
x = 248846 - 179 * 1390 = 36
y = - 109785 + 79 * 1390 = 25