Velocity Reviews

Velocity Reviews (http://www.velocityreviews.com/forums/index.php)
-   Perl Misc (http://www.velocityreviews.com/forums/f67-perl-misc.html)
-   -   A subroutine for gcd (http://www.velocityreviews.com/forums/t899032-a-subroutine-for-gcd.html)

gamo 07-17-2006 01:38 PM

A subroutine for gcd
 

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";'

Tad McClellan 07-17-2006 03:37 PM

Re: A subroutine for gcd
 
gamo <gamo@telecable.es> 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
tadmc@augustmail.com Perl programming
Fort Worth, Texas

Michele Dondi 07-18-2006 10:27 AM

Re: A subroutine for gcd
 
On Mon, 17 Jul 2006 15:38:58 +0200, gamo <gamo@telecable.es> 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,

David Squire 07-18-2006 10:50 AM

Re: A subroutine for gcd
 
Michele Dondi wrote:
> On Mon, 17 Jul 2006 15:38:58 +0200, gamo <gamo@telecable.es> 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

gamo 07-18-2006 02:09 PM

Re: A subroutine for gcd
 
On Tue, 18 Jul 2006, Michele Dondi wrote:

> On Mon, 17 Jul 2006 15:38:58 +0200, gamo <gamo@telecable.es> 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,


Michele Dondi 07-19-2006 03:16 PM

Re: A subroutine for gcd
 
On Tue, 18 Jul 2006 16:09:07 +0200, gamo <gamo@telecable.es> 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,

Michele Dondi 07-21-2006 10:23 AM

Re: A subroutine for gcd
 
On 19 Jul 2006 15:32:59 GMT, Glenn Jackman <glennj@ncf.ca> 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,


All times are GMT. The time now is 10:08 PM.

Powered by vBulletin®. Copyright ©2000 - 2014, vBulletin Solutions, Inc.
SEO by vBSEO ©2010, Crawlability, Inc.