A subroutine for gcd

[gamo]

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

 

[Tad McClellan]

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.

 

[Michele Dondi]

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

 

[David Squire]

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]

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]

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

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

 

[Michele Dondi]

^^^^^^...............^^^^^^^^^^^^^
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