Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.



Re: Approximating GCF
Posted:
Jul 17, 2014 8:47 PM


On Thu, 17 Jul 2014 04:46:36 0700, ryan.mitchley wrote: > On Thursday, July 17, 2014 11:46:53 AM UTC+2, William Elliot wrote: >> >> >> Let n1, n2,.. nj be j integers, r a real number and d1, d2, .. dj small >> numbers. You are given what? n1,.. nj & d1,.. dj and are looking for >> some r for which the sequence r.n1 + d1, r.n2 + d2,.. r.nj + sj does what?
> Sorry for being unclear. I want the best estimate of r, given a number of < samples of the sums r.ni+di > > e.g. given [1.3375, 2.0776, 4.7121, 2.0996, 3.8090] > we notice that 1.7 is the "closest" common factor  i.e. after subtracting > 0.425 and dividing by 1.7 the sequence is nearly a set of integers: > [1.0368, 0.9721, 3.0218, 0.9851, 1.9906]
Let's say you are given n values y_1 ... y_n. By knowledge about some process, you know that each y_i is some random noise d_i plus r * x_i, where r, x_i, and d_i are unknowns except that all the x_i are integers. You want to compute r.
There may be a way of writing the problem as a mixed integer linear programming problem, or it might be analyzed as a clustering problem, and there might be a continuedfractions method. A Fourier analysis might have a spike at frequency 1/r or a multiple.
Also consider the following brute force approach: Let s = max(y_i), t = min(y_i), u = st. For values of j from 1 to some large number, compute a trial value of r_j as u/j. Compute a quality statistic Q_j as the sum of absolute differences (or squared differences, etc) over all i of y_i  k_i*r_j  b_j, where k_i is either int((y_i  b_j)/r_j) or that number plus 1, whichever is closer. Offset b_j can be set equal to y_1, or can be chosen to minimize Q_j. . It probably is possible to compute a minimizing b_j for a given r_j in O(n) time. If you try m different values of j while trying to minimize Q_j over j, the overall process is O(m*n).
 jiw



