Path: news.mathworks.com!not-for-mail
From: "Bruno Luong" <b.luong@fogale.fr>
Newsgroups: comp.soft-sys.matlab
Subject: Re: Largest Common Factor
Date: Wed, 30 Apr 2008 10:42:02 +0000 (UTC)
Organization: FOGALE nanotech
Lines: 50
Message-ID: <fv9idq$ek8$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: "Bruno Luong" <b.luong@fogale.fr>
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 1209552122 14984 172.30.248.35 (30 Apr 2008 10:42:02 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Wed, 30 Apr 2008 10:42:02 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 390839
Xref: news.mathworks.com comp.soft-sys.matlab:465900


"Bruno Luong" <b.luong@fogale.fr> wrote in message
<fv959q$34q$1@fred.mathworks.com>...
> "Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid>
> wrote in message <fv8j8a$2j8$1@fred.mathworks.com>...
> 
> > 
> >   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.
> 
> 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

Here is a code of the above idea:

asize=100;
maxa=10;
myeps=1e-10; % small number
% generate asize array, multiple of 4.1
a=4.1*(1+round(rand(1,asize)*(maxa-1)));

% The engine!

aworking=a;
while 1
    [p imin]=min(aworking);
    irest=[1:imin-1 imin+1:length(aworking)];
    arest=mod(aworking(irest),p);
    arest(abs(arest)<myeps)=nan; % lock
    if any(abs(arest))
        aworking(irest)=arest;
    else
        break
    end
end
disp(p);