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 01:50:02 +0000 (UTC)
Organization: The MathWorks, Inc.
Lines: 41
Message-ID: <fv8j8a$2j8$1@fred.mathworks.com>
References: <7ebde538-62ed-4bba-aed4-15843490c573@24g2000hsh.googlegroups.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 1209520202 2664 172.30.248.35 (30 Apr 2008 01:50:02 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Wed, 30 Apr 2008 01:50:02 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 1187260
Xref: news.mathworks.com comp.soft-sys.matlab:465836


Greg Heath <heath@alumni.brown.edu> wrote in message 
<7ebde538-62ed-4bba-
aed4-15843490c573@24g2000hsh.googlegroups.com>...
> What is the best way to find the largest common
> factor of an array? For example, 4.1 is the largest  common factor of
> [12.3 20.5 32.8]].
> I've looped over whole fractions of 12.3 to
> get an integer array but feel there must be a better way.
> 
> Thanks,
> 
> Greg
---------
  Euclid's algorithm would still work for non-integer elements like 12.3, but it 
would have to have a tolerance that allows for round-off errors.  For example, 
the binary floating point value matlab uses to approximate 12.3 is not an 
exact integral multiple of the number with which it approximates 4.1.  I don't 
know whether the current version of 'gcd' makes such an allowance or 
whether it even permits non-integers as input arguments.  (My own version 
does not.)

  Using Euclid's algorithm, the numbers 12.3 and 20.5 would go:

 rem(20.5,12.3) = 8.2
 rem(12.3, 8.2) = 4.1
 rem( 8.2, 4.1) = 0.0

except that this last one wouldn't be exactly zero but only within some 
tolerated distance from zero.  If you started with, say, pi and sqrt(2), this 
procedure would not stop until it had dropped far down into numbers in the 
tolerated noise level.

  I can think of no better way of handling more than two elements than 
repeating the above operation using the largest common factor found up to a 
point in an array, together with the array's next element.  Short of a matlab 
function designed for this, it sounds like using a common garden variety for-
loop to accomplish this feat is your best bet.  This algorithm does not appear 
to lend itself to any kind of vectorizaton that I can think of.

Roger Stafford