Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Perl > Perl Misc > A subroutine for gcd

Reply
Thread Tools

A subroutine for gcd

 
 
gamo
Guest
Posts: n/a
 
      07-17-2006

Does anyone knows how to write a sub for gcd?
Any chances that will be include in the core like sort or like UBASIC?
TIA

--
http://www.telecable.es/personales/gamo/
Sólo hay 10 tipos de personas, las que saben binario y las que no
perl -e 'print 111_111_111**2,"\n";'
 
Reply With Quote
 
 
 
 
Tad McClellan
Guest
Posts: n/a
 
      07-17-2006
gamo <(E-Mail Removed)> wrote:

> This message is in MIME format.



Please do not post messages in MIME format...


> while the remaining parts are likely unreadable without MIME-aware tools.



.... because parts are likely unreadable without MIME-aware tools.


> Does anyone knows how to write a sub for gcd?



That depends on what gcd means.


> Any chances that will be include in the core like sort



If it might mean Greatest Common Denominator, then there is virtually
no chance of it being included in the core.

Things that can be done with modules don't need to be in the core.


--
Tad McClellan SGML consulting
http://www.velocityreviews.com/forums/(E-Mail Removed) Perl programming
Fort Worth, Texas
 
Reply With Quote
 
 
 
 
Michele Dondi
Guest
Posts: n/a
 
      07-18-2006
On Mon, 17 Jul 2006 15:38:58 +0200, gamo <(E-Mail Removed)> wrote:

>Does anyone knows how to write a sub for gcd?


Yes I know!

Ok, now I know you don't believe me...

sub gcd { $_[1]?gcd($_[1],$_[0]%$_[1]):$_[0] }


Michele
--
{$_=pack'B8'x25,unpack'A8'x32,$a^=sub{pop^pop}->(map substr
(($a||=join'',map--$|x$_,(unpack'w',unpack'u','G^<R<Y]*YB='
..'KYU;*EVH[.FHF2W+#"\Z*5TI/ER<Z`S(G.DZZ9OX0Z')=~/./g)x2,$_,
256),7,249);s/[^\w,]/ /g;$ \=/^J/?$/:"\r";print,redo}#JAPH,
 
Reply With Quote
 
David Squire
Guest
Posts: n/a
 
      07-18-2006
Michele Dondi wrote:
> On Mon, 17 Jul 2006 15:38:58 +0200, gamo <(E-Mail Removed)> wrote:
>
>> Does anyone knows how to write a sub for gcd?

>
> Yes I know!
>
> Ok, now I know you don't believe me...
>
> sub gcd { $_[1]?gcd($_[1],$_[0]%$_[1]):$_[0] }


Good old Euclid. If you want to read about why it works, see
http://mathworld.wolfram.com/EuclideanAlgorithm.html


DS
 
Reply With Quote
 
gamo
Guest
Posts: n/a
 
      07-18-2006
On Tue, 18 Jul 2006, Michele Dondi wrote:

> On Mon, 17 Jul 2006 15:38:58 +0200, gamo <(E-Mail Removed)> wrote:
>
> >Does anyone knows how to write a sub for gcd?

>
> Yes I know!
>
> Ok, now I know you don't believe me...
>
> sub gcd { $_[1]?gcd($_[1],$_[0]%$_[1]):$_[0] }
>

I belive you, but it is just a gcd of a PAIR of numbers.

I find this in the ToolBox module

sub gcd {
use integer;
my $gcd = shift || 1;
while (@_) {
my $next = shift;
while($next) {
my $r = $gcd % $next;
$r += $next if $r < 0;
$gcd = $next;
$next = $r;
}
}
no integer;
return $gcd;
}

Cheers,

 
Reply With Quote
 
Michele Dondi
Guest
Posts: n/a
 
      07-19-2006
On Tue, 18 Jul 2006 16:09:07 +0200, gamo <(E-Mail Removed)> wrote:

>> >Does anyone knows how to write a sub for gcd?

^^^^^^^^^^^^^
^^^^^^^^^^^^^

>> Yes I know!
>>
>> Ok, now I know you don't believe me...
>>
>> sub gcd { $_[1]?gcd($_[1],$_[0]%$_[1]):$_[0] }
>>

>I belive you, but it is just a gcd of a PAIR of numbers.


First of all with the information you supplied (see above!) it may
have been whatever. I *guessed* you were referring to the Greatest
Common Divisor, and supplied *a* sub for the most obvious case that
occurred to me. BTW, you do know that amongst other things

gcd(n,a,b,...) = gcd(gcd(n,a),b,...) = gcd(gcd(n,a),gcd(n,b),...),

don't you? Well, the following will work for any *positive* number of
arguments.

sub gcd { my $n=pop;@_?gcd($n?map gcd($n,$_%$n),@_:@_):$n }

Please notice the simmetry between the @_?...:$n construct and the
$n?...:@_ one. Isn't it amazing?

>I find this in the ToolBox module
>
>sub gcd {


Well, if you had it, why are you asking in the first place?!? Note:
this will work for *any* number of arguments.


Michele
--
{$_=pack'B8'x25,unpack'A8'x32,$a^=sub{pop^pop}->(map substr
(($a||=join'',map--$|x$_,(unpack'w',unpack'u','G^<R<Y]*YB='
..'KYU;*EVH[.FHF2W+#"\Z*5TI/ER<Z`S(G.DZZ9OX0Z')=~/./g)x2,$_,
256),7,249);s/[^\w,]/ /g;$ \=/^J/?$/:"\r";print,redo}#JAPH,
 
Reply With Quote
 
Michele Dondi
Guest
Posts: n/a
 
      07-21-2006
On 19 Jul 2006 15:32:59 GMT, Glenn Jackman <(E-Mail Removed)> wrote:

>> sub gcd { my $n=pop;@_?gcd($n?map gcd($n,$_%$n),@_:@_):$n }

> ^^^^^^...............^^^^^^^^^^^^^
>Do you mean $n=shift ?


No, I mean pop().

$ cat gcd.pl
#!/usr/bin/perl -l

use strict;
use warnings;

sub gcd { my $n=pop;@_?gcd($n?map gcd($n,$_%$n),@_:@_):$n }

print gcd split while <>;

__END__
$ ./gcd.pl
10 15 20
5
222 294 822 336
6
$ perl -lpi.bak -e 's/pop/shift/' gcd.pl
$ ./gcd.pl
10 15 20
Deep recursion on subroutine "main::gcd" at ./gcd.pl line 6, <> line
1.


Michele
--
{$_=pack'B8'x25,unpack'A8'x32,$a^=sub{pop^pop}->(map substr
(($a||=join'',map--$|x$_,(unpack'w',unpack'u','G^<R<Y]*YB='
..'KYU;*EVH[.FHF2W+#"\Z*5TI/ER<Z`S(G.DZZ9OX0Z')=~/./g)x2,$_,
256),7,249);s/[^\w,]/ /g;$ \=/^J/?$/:"\r";print,redo}#JAPH,
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
use one subroutine's variable value in another subroutine inside a module. king Perl Misc 5 04-29-2007 06:39 AM
How to write a small graceful gcd function? lovecreatesbeauty C Programming 73 07-26-2006 02:02 AM
plz tell me how 2 find GCD(greater common diviser) mudasirk@gmail.com C++ 3 05-15-2005 06:30 PM
GCD of polynomials adrin C++ 7 01-06-2005 05:53 PM
gcd -*-*-///-*-*- Computer Support 3 11-28-2003 12:20 AM



Advertisments