Path: news.mathworks.com!not-for-mail
From: "Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid>
Newsgroups: comp.soft-sys.matlab
Subject: Re: Largest Common Factor
Date: Wed, 30 Apr 2008 11:12:03 +0000 (UTC)
Organization: The MathWorks, Inc.
Lines: 45
Message-ID: <fv9k63$qkv$1@fred.mathworks.com>
References: <7ebde538-62ed-4bba-aed4-15843490c573@24g2000hsh.googlegroups.com> <fv8j8a$2j8$1@fred.mathworks.com> <fv959q$34q$1@fred.mathworks.com>
Reply-To: "Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid>
NNTP-Posting-Host: webapp-05-blr.mathworks.com
Content-Type: text/plain; charset="ISO-8859-1"
Content-Transfer-Encoding: 8bit
X-Trace: fred.mathworks.com 1209553923 27295 172.30.248.35 (30 Apr 2008 11:12:03 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Wed, 30 Apr 2008 11:12:03 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 1187260
Xref: news.mathworks.com comp.soft-sys.matlab:465904


"Bruno Luong" <b.luong@fogale.fr> wrote in message <fv959q$34q
$1@fred.mathworks.com>...
> I also think euclide's algorithm is a great idea. But we
> need to define how to apply on the array. What about
> 
> 1) find the minimum element "p" (absolute value) of the array
> 2) Replace all other elements by the remaining with "p".
> 3) if all the replacements are "zero" (within a tolerance)
> then stop
> 4) Otherwise loop on 1)
> 
> When break the loop, p is the answer.
> 
> Bruno
-----------
  I would envision implementing Euclid's algorithm for arrays of non-integers 
with something like the following.  Let x be a vector of values, not necessarily 
integers and not necessarily of like sign, for which we wish to find the largest 
common factor, f.  That is, we want the largest magnitude, f, such that all 
elements of x are integer multiples of f (ignoring round-off errors.)  For this 
to work properly, the vector x should not contain any zero or nearly zero 
values - the multiples should be non-zero multiples.

 tol = 1e-8;
 f = x(1);
 for k = 2:length(x)
  r = f;
  f = x(k);
  while abs(r) > tol
   t = f;
   f = r;
   r = rem(t,f);
  end
 end
 f = abs(f); % This is the largest common factor of elements in x

  The value for 'tol' here is not necessarily optimum.  The best choice would 
depend on the magnitudes of elements in x and on the length of x, but I 
haven't worked out a good criterion as yet.  It does have to be chosen 
carefully.  If it is too small, it will miss cases where a common factor exists 
but gets overlooked because of accumulating round-off errors.  If it is too 
large, it will allow false, overly-large common factors to be admitted.

Roger Stafford