Path: news.mathworks.com!newsfeed-00.mathworks.com!newsfeed2.dallas1.level3.net!news.level3.com!postnews.google.com!w7g2000hsa.googlegroups.com!not-for-mail
From: Greg Heath <heath@alumni.brown.edu>
Newsgroups: comp.soft-sys.matlab
Subject: Re: Largest Common Factor
Date: Wed, 30 Apr 2008 09:04:56 -0700 (PDT)
Organization: http://groups.google.com
Lines: 63
Message-ID: <71d7fe46-7f8d-431e-9786-199c05f3ff9d@w7g2000hsa.googlegroups.com>
References: <7ebde538-62ed-4bba-aed4-15843490c573@24g2000hsh.googlegroups.com> 
NNTP-Posting-Host: 69.141.173.117
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
X-Trace: posting.google.com 1209571496 7951 127.0.0.1 (30 Apr 2008 16:04:56 GMT)
X-Complaints-To: groups-abuse@google.com
NNTP-Posting-Date: Wed, 30 Apr 2008 16:04:56 +0000 (UTC)
Complaints-To: groups-abuse@google.com
Injection-Info: w7g2000hsa.googlegroups.com; posting-host=69.141.173.117; 
User-Agent: G2/1.0
X-HTTP-UserAgent: Mozilla/4.0 (compatible; MSIE 6.0; Windows NT 5.1; 
Xref: news.mathworks.com comp.soft-sys.matlab:465965


On Apr 30, 7:12=A0am, "Roger Stafford"
<ellieandrogerxy...@mindspring.com.invalid> wrote:
> "Bruno Luong" <b.lu...@fogale.fr> wrote in message <fv959q$34q
>
> $...@fred.mathworks.com>...> I also think euclide's algorithm is a great i=
dea. 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
>
> -----------
> =A0 I would envision implementing Euclid's algorithm for arrays of non-int=
egers
> with something like the following. =A0Let x be a vector of values, not nec=
essarily
> integers and not necessarily of like sign, for which we wish to find the l=
argest
> common factor, f. =A0That is, we want the largest magnitude, f, such that =
all
> elements of x are integer multiples of f (ignoring round-off errors.) =A0F=
or this
> to work properly, the vector x should not contain any zero or nearly zero
> values - the multiples should be non-zero multiples.
>
> =A0tol =3D 1e-8;
> =A0f =3D x(1);
> =A0for k =3D 2:length(x)
> =A0 r =3D f;
> =A0 f =3D x(k);
> =A0 while abs(r) > tol
> =A0 =A0t =3D f;
> =A0 =A0f =3D r;
> =A0 =A0r =3D rem(t,f);
> =A0 end
> =A0end
> =A0f =3D abs(f); % This is the largest common factor of elements in x
>
> =A0 The value for 'tol' here is not necessarily optimum. =A0The best choic=
e 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. =A0It does have to be chosen
> carefully. =A0If it is too small, it will miss cases where a common factor=
 exists
> but gets overlooked because of accumulating round-off errors. =A0If it is =
too
> large, it will allow false, overly-large common factors to be admitted.
>
> Roger Stafford

Roger and Bruno,

Thanks. The application will be to overlay a uniform grid on a
nonuniform grid for the purposes of using the fft instead of a dft.

Greg