Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
Greatest commmon divisor

Subject: Greatest commmon divisor

From: Feng

Date: 12 Dec, 2008 21:21:02

Message: 1 of 14

Hi, any one know how can get the gcd for an array. The function gcd() in matlabe will give result for a array.
for example I want to get 2 for the array A= [10 2 10 -4 2 0];
Is there any function to do that? or how can I do that?

Thanks

Subject: Greatest commmon divisor

From: Feng

Date: 12 Dec, 2008 21:29:02

Message: 2 of 14

"Feng" <nclxin@hotmail.com> wrote in message <ghukju$ksu$1@fred.mathworks.com>...
> Hi, any one know how can get the gcd for an array. The function gcd() in matlabe > will give result for two scalar numbers.
> for example I want to get 2 for the array A= [10 2 10 -4 2 0];
> Is there any function to do that? or how can I do that?
>
> Thanks

Subject: Greatest commmon divisor

From: Roger Stafford

Date: 12 Dec, 2008 21:47:02

Message: 3 of 14

"Feng" <nclxin@hotmail.com> wrote in message <ghul2u$rfp$1@fred.mathworks.com>...
> "Feng" <nclxin@hotmail.com> wrote in message <ghukju$ksu$1@fred.mathworks.com>...
> > Hi, any one know how can get the gcd for an array. The function gcd() in matlabe > will give result for two scalar numbers.
> > for example I want to get 2 for the array A= [10 2 10 -4 2 0];
> > Is there any function to do that? or how can I do that?
> >
> > Thanks

  You could always use an old-fashioned for-loop:

c = A(1);
for k = 2:length(A)
 c = gcd(c,A(k));
end

Roger Stafford

Subject: Greatest commmon divisor

From: Loren Shure

Date: 16 Dec, 2008 01:38:23

Message: 4 of 14

In article <ghukju$ksu$1@fred.mathworks.com>, nclxin@hotmail.com says...
> Hi, any one know how can get the gcd for an array. The function gcd() in matlabe will give result for a array.
> for example I want to get 2 for the array A= [10 2 10 -4 2 0];
> Is there any function to do that? or how can I do that?
>
> Thanks
>

Check out the function arrayfun

--
Loren
http://blogs.mathworks.com/loren

Subject: Greatest commmon divisor

From: Bruno Luong

Date: 16 Dec, 2008 05:51:02

Message: 5 of 14

Loren Shure <loren@mathworks.com> wrote in message <MPG.23b0d09e505fb8f4989907@news.mathworks.com>...
> >
>
> Check out the function arrayfun
>

I can't see how arrayfun would be used here. I rather stick with Roger's for-loop solution.

Bruno

Subject: Greatest commmon divisor

From: Jos

Date: 16 Dec, 2008 07:54:05

Message: 6 of 14

"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <ghum4l$d95$1@fred.mathworks.com>...
> "Feng" <nclxin@hotmail.com> wrote in message <ghul2u$rfp$1@fred.mathworks.com>...
> > "Feng" <nclxin@hotmail.com> wrote in message <ghukju$ksu$1@fred.mathworks.com>...
> > > Hi, any one know how can get the gcd for an array. The function gcd() in matlabe > will give result for two scalar numbers.
> > > for example I want to get 2 for the array A= [10 2 10 -4 2 0];
> > > Is there any function to do that? or how can I do that?
> > >
> > > Thanks
>
> You could always use an old-fashioned for-loop:
>
> c = A(1);
> for k = 2:length(A)
> c = gcd(c,A(k));
> end
>
> Roger Stafford


What about

min(gcd(A(1:end-1),A(2:end)))

Jos

Subject: Greatest commmon divisor

From: Jos

Date: 16 Dec, 2008 07:59:07

Message: 7 of 14

"Jos " <#10584@fileexchange.com> wrote in message <gi7mqt$87b$1@fred.mathworks.com>...
> "Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <ghum4l$d95$1@fred.mathworks.com>...
> > "Feng" <nclxin@hotmail.com> wrote in message <ghul2u$rfp$1@fred.mathworks.com>...
> > > "Feng" <nclxin@hotmail.com> wrote in message <ghukju$ksu$1@fred.mathworks.com>...
> > > > Hi, any one know how can get the gcd for an array. The function gcd() in matlabe > will give result for two scalar numbers.
> > > > for example I want to get 2 for the array A= [10 2 10 -4 2 0];
> > > > Is there any function to do that? or how can I do that?
> > > >
> > > > Thanks
> >
> > You could always use an old-fashioned for-loop:
> >
> > c = A(1);
> > for k = 2:length(A)
> > c = gcd(c,A(k));
> > end
> >
> > Roger Stafford
>
>
> What about
>
> min(gcd(A(1:end-1),A(2:end)))
>
> Jos

On second thoughts, you have to remove the zeros first, otherwise something like
A = [x 0 0 y]
will always give 0, instead of gcd(x,y)

Jos

Subject: Greatest commmon divisor

From: Bruno Luong

Date: 16 Dec, 2008 08:09:06

Message: 8 of 14


>
> min(gcd(A(1:end-1),A(2:end)))
>

Jos, this does not work

A=[15 30 20]

gcd is 5, not 10

Bruno

Subject: Greatest commmon divisor

From: Roger Stafford

Date: 16 Dec, 2008 08:16:05

Message: 9 of 14

"Jos " <#10584@fileexchange.com> wrote in message <gi7mqt$87b$1@fred.mathworks.com>...
> What about
>
> min(gcd(A(1:end-1),A(2:end)))
>
> Jos

  I don't think that would work, Jos, even with zeros eliminated. Let A = [15,21,35]. Then gcd(A(1:end-1),A(2:end)) would yield [3,7] but the minimum of these is not the gcd of the three combined quantities. The greatest common factor of all three is simply 1, not this minimum.

Roger Stafford

Subject: Greatest commmon divisor

From: Jos

Date: 16 Dec, 2008 10:04:03

Message: 10 of 14

"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <gi7o45$297$1@fred.mathworks.com>...
> "Jos " <#10584@fileexchange.com> wrote in message <gi7mqt$87b$1@fred.mathworks.com>...
> > What about
> >
> > min(gcd(A(1:end-1),A(2:end)))
> >
> > Jos
>
> I don't think that would work, Jos, even with zeros eliminated. Let A = [15,21,35]. Then gcd(A(1:end-1),A(2:end)) would yield [3,7] but the minimum of these is not the gcd of the three combined quantities. The greatest common factor of all three is simply 1, not this minimum.
>
> Roger Stafford

Yep, you and Bruno are right, of course. I was just wondering why Loren suggested arrayfun, and so I was looking for a function that could do this.

Jos

Subject: Greatest commmon divisor

From: Loren Shure

Date: 16 Dec, 2008 15:16:09

Message: 11 of 14

In article <gi7uei$22l$1@fred.mathworks.com>, #10584@fileexchange.com
says...
> "Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <gi7o45$297$1@fred.mathworks.com>...
> > "Jos " <#10584@fileexchange.com> wrote in message <gi7mqt$87b$1@fred.mathworks.com>...
> > > What about
> > >
> > > min(gcd(A(1:end-1),A(2:end)))
> > >
> > > Jos
> >
> > I don't think that would work, Jos, even with zeros eliminated. Let A = [15,21,35]. Then gcd(A(1:end-1),A(2:end)) would yield [3,7] but the minimum of these is not the gcd of the three combined quantities. The greatest common factor of all three is simply 1, not this minimum.
> >
> > Roger Stafford
>
> Yep, you and Bruno are right, of course. I was just wondering why Loren suggested arrayfun, and so I was looking for a function that could do this.
>
> Jos
>
>

Perhaps I misread the problem. I thought the OP wanted GCD of each
"pair" of points in 2 arrays. Probably read too fast...

--
Loren
http://blogs.mathworks.com/loren

Subject: Greatest commmon divisor

From: Alice

Date: 26 Jun, 2014 14:57:10

Message: 12 of 14

All the suggestions here will be terribly inefficient for large numbers. Built in gcd functions use sophisticated algorithms to cut down the time to compute. Note that

gcd(a,b,c) = gcd(gcd(a,b),gcd(b,c))

and go from there.

"Feng" <nclxin@hotmail.com> wrote in message <ghukju$ksu$1@fred.mathworks.com>...
> Hi, any one know how can get the gcd for an array. The function gcd() in matlabe will give result for a array.
> for example I want to get 2 for the array A= [10 2 10 -4 2 0];
> Is there any function to do that? or how can I do that?
>
> Thanks

Subject: Greatest commmon divisor

From: Bruno Luong

Date: 26 Jun, 2014 19:57:09

Message: 13 of 14

"Alice" wrote in message <lohcc6$979$1@newscl01ah.mathworks.com>...
> All the suggestions here will be terribly inefficient for large numbers. Built in gcd functions use sophisticated algorithms to cut down the time to compute. Note that
>
> gcd(a,b,c) = gcd(gcd(a,b),gcd(b,c))
>
> and go from there.

Any example to backup your claim of exploiting the above is significant faster than using the simpler relation

gcd(a,b,c) = gcd(gcd(a,b),c) % ?

Bruno

Subject: Greatest commmon divisor

From: Shashank

Date: 12 Nov, 2014 20:27:06

Message: 14 of 14

"Feng" <nclxin@hotmail.com> wrote in message <ghukju$ksu$1@fred.mathworks.com>...
> Hi, any one know how can get the gcd for an array. The function gcd() in matlabe will give result for a array.
> for example I want to get 2 for the array A= [10 2 10 -4 2 0];
> Is there any function to do that? or how can I do that?
>
> Thanks


% GCD OF list of Nos using Eucledian Alogorithm
function GCD= GCD(n);
x=1;
p=n;
while(size(n,2))>=2
    p= n(:,size(n,2)-1:size(n,2));
    n=n(1,1:size(n,2)-2);
    x=1;
    while(x~=0)
    x= max(p)-min(p);
    p = [x,min(p)];
    end
    n=[n,max(p)];
    p= [];
end
fprintf(' The GCD OF Nos is = %d ',min(n))

Tags for this Thread

No tags are associated with this thread.

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us