Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Topic: Approximating GCF
Replies: 1   Last Post: Jul 17, 2014 8:47 PM

 James Waldby Posts: 535 Registered: 1/27/11
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 continued-fractions 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 = s-t. 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