A subroutine for gcd

Discussion in 'Perl Misc' started by gamo, Jul 17, 2006.

  1. gamo

    gamo Guest

    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";'
     
    gamo, Jul 17, 2006
    #1
    1. Advertising

  2. gamo <> 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
    Perl programming
    Fort Worth, Texas
     
    Tad McClellan, Jul 17, 2006
    #2
    1. Advertising

  3. On Mon, 17 Jul 2006 15:38:58 +0200, gamo <> 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,
     
    Michele Dondi, Jul 18, 2006
    #3
  4. gamo

    David Squire Guest

    Michele Dondi wrote:
    > On Mon, 17 Jul 2006 15:38:58 +0200, gamo <> 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
     
    David Squire, Jul 18, 2006
    #4
  5. gamo

    gamo Guest

    On Tue, 18 Jul 2006, Michele Dondi wrote:

    > On Mon, 17 Jul 2006 15:38:58 +0200, gamo <> 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,
     
    gamo, Jul 18, 2006
    #5
  6. On Tue, 18 Jul 2006 16:09:07 +0200, gamo <> 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),@_:mad:_):$n }

    Please notice the simmetry between the @_?...:$n construct and the
    $n?...:mad:_ 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, Jul 19, 2006
    #6
  7. On 19 Jul 2006 15:32:59 GMT, Glenn Jackman <> wrote:

    >> sub gcd { my $n=pop;@_?gcd($n?map gcd($n,$_%$n),@_:mad:_):$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),@_:mad:_):$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,
     
    Michele Dondi, Jul 21, 2006
    #7
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. adrin

    GCD of polynomials

    adrin, Jan 5, 2005, in forum: C++
    Replies:
    7
    Views:
    3,099
    Buster
    Jan 6, 2005
  2. Replies:
    3
    Views:
    491
    David Hilsee
    May 15, 2005
  3. lovecreatesbeauty

    How to write a small graceful gcd function?

    lovecreatesbeauty, Jul 15, 2006, in forum: C Programming
    Replies:
    73
    Views:
    1,590
    ozbear
    Jul 26, 2006
  4. sathyashrayan

    simple GCD, help

    sathyashrayan, Nov 18, 2006, in forum: C Programming
    Replies:
    7
    Views:
    351
    Spiros Bousbouras
    Nov 18, 2006
  5. hazal Ates

    .gcd method in ruby 1.8.7

    hazal Ates, Sep 8, 2010, in forum: Ruby
    Replies:
    8
    Views:
    157
    Quintus
    Sep 9, 2010
Loading...

Share This Page