gcd

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|

gcd

Steven Chaplin
I had a look at the gcd definition in GHC 6.10.1
ghc-6.10.1/libraries/base/GHC/Real.lhs

-- | @'gcd' x y@ is the greatest (positive) integer that divides both
@x@
-- and @y@; for example @'gcd' (-3) 6@ = @3@, @'gcd' (-3) (-6)@ = @3@,
-- @'gcd' 0 4@ = @4@.  @'gcd' 0 0@ raises a runtime error.
gcd             :: (Integral a) => a -> a -> a
gcd 0 0         =  error "Prelude.gcd: gcd 0 0 is undefined"
gcd x y         =  gcd' (abs x) (abs y)
                   where gcd' a 0  =  a
                         gcd' a b  =  gcd' b (a `rem` b)

Why is gcd 0 0 undefined?

http://en.wikipedia.org/wiki/Greatest_common_divisor says:
"It is useful to define gcd(0, 0) = 0 and lcm(0, 0) = 0 because then the
natural numbers become a complete distributive lattice with gcd as meet
and lcm as join operation. This extension of the definition is also
compatible with the generalization for commutative rings given below."

An added advantage, for haskell, of defining gcd 0 0 = 0 is that gcd
would change from being a partial function to a total function.

Regards,
Steve



Reply | Threaded
Open this post in threaded view
|

gcd

Daniel Carrera-4
I'm just another Haskell beginner, but what Steve says makes sense.
Perhaps something like this:

gcd a b | b == 0    = a
         | b < 0     = gcd (-b) a
         | otherwise = gcd b (a `rem` b)

Daniel.

Steve wrote:

> I had a look at the gcd definition in GHC 6.10.1
> ghc-6.10.1/libraries/base/GHC/Real.lhs
>
> -- | @'gcd' x y@ is the greatest (positive) integer that divides both
> @x@
> -- and @y@; for example @'gcd' (-3) 6@ = @3@, @'gcd' (-3) (-6)@ = @3@,
> -- @'gcd' 0 4@ = @4@.  @'gcd' 0 0@ raises a runtime error.
> gcd             :: (Integral a) => a -> a -> a
> gcd 0 0         =  error "Prelude.gcd: gcd 0 0 is undefined"
> gcd x y         =  gcd' (abs x) (abs y)
>                    where gcd' a 0  =  a
>                          gcd' a b  =  gcd' b (a `rem` b)
>
> Why is gcd 0 0 undefined?
>
> http://en.wikipedia.org/wiki/Greatest_common_divisor says:
> "It is useful to define gcd(0, 0) = 0 and lcm(0, 0) = 0 because then the
> natural numbers become a complete distributive lattice with gcd as meet
> and lcm as join operation. This extension of the definition is also
> compatible with the generalization for commutative rings given below."
>
> An added advantage, for haskell, of defining gcd 0 0 = 0 is that gcd
> would change from being a partial function to a total function.
>
> Regards,
> Steve
>
>
>
> _______________________________________________
> Beginners mailing list
> [hidden email]
> http://www.haskell.org/mailman/listinfo/beginners
>

Reply | Threaded
Open this post in threaded view
|

gcd

Daniel Fischer-4
Am Freitag 01 Mai 2009 22:28:12 schrieb Daniel Carrera:
> I'm just another Haskell beginner, but what Steve says makes sense.

Yes, it's something I've often been annoyed by.
It's a wart (rather an error) in the Haskell report
http://haskell.org/onlinereport/basic.html#sect6.4.2
where it's specified that gcd 0 0 shall raise a runtime error. I hope that gets fixed in
the next standard.

> Perhaps something like this:
>
> gcd a b | b == 0    = a
>
>          | b < 0     = gcd (-b) a
>          | otherwise = gcd b (a `rem` b)
>
> Daniel.

No, that would check for negative numbers in each iteration. Just remove the line

gcd 0 0         =  error "Prelude.gcd: gcd 0 0 is undefined"

and everything's fine.

>
> Steve wrote:
> > I had a look at the gcd definition in GHC 6.10.1
> > ghc-6.10.1/libraries/base/GHC/Real.lhs
> >
> > -- | @'gcd' x y@ is the greatest (positive) integer that divides both
> > @x@
> > -- and @y@; for example @'gcd' (-3) 6@ = @3@, @'gcd' (-3) (-6)@ = @3@,
> > -- @'gcd' 0 4@ = @4@.  @'gcd' 0 0@ raises a runtime error.
> > gcd             :: (Integral a) => a -> a -> a
> > gcd 0 0         =  error "Prelude.gcd: gcd 0 0 is undefined"
> > gcd x y         =  gcd' (abs x) (abs y)
> >                    where gcd' a 0  =  a
> >                          gcd' a b  =  gcd' b (a `rem` b)
> >
> > Why is gcd 0 0 undefined?
> >
> > http://en.wikipedia.org/wiki/Greatest_common_divisor says:
> > "It is useful to define gcd(0, 0) = 0 and lcm(0, 0) = 0 because then the
> > natural numbers become a complete distributive lattice with gcd as meet
> > and lcm as join operation. This extension of the definition is also
> > compatible with the generalization for commutative rings given below."
> >
> > An added advantage, for haskell, of defining gcd 0 0 = 0 is that gcd
> > would change from being a partial function to a total function.
> >
> > Regards,
> > Steve

Reply | Threaded
Open this post in threaded view
|

gcd

Steven Chaplin
In reply to this post by Steven Chaplin
On Fri, 2009-05-01 at 16:19 +0200, Peter Verswyvelen wrote:
> I suggest you forward this to the Haskell Cafe, since it's not really
> a beginners question, it's a really good question :)

Thanks for the advice, I've reposted the question to the Haskell Cafe.
Steve

> On Fri, May 1, 2009 at 4:19 PM, Steve <[hidden email]>
> wrote:
>         I had a look at the gcd definition in GHC 6.10.1
>         ghc-6.10.1/libraries/base/GHC/Real.lhs
>        
>         -- | @'gcd' x y@ is the greatest (positive) integer that
>         divides both
>         @x@
>         -- and @y@; for example @'gcd' (-3) 6@ = @3@, @'gcd' (-3)
>         (-6)@ = @3@,
>         -- @'gcd' 0 4@ = @4@.  @'gcd' 0 0@ raises a runtime error.
>         gcd             :: (Integral a) => a -> a -> a
>         gcd 0 0         =  error "Prelude.gcd: gcd 0 0 is undefined"
>         gcd x y         =  gcd' (abs x) (abs y)
>                           where gcd' a 0  =  a
>                                 gcd' a b  =  gcd' b (a `rem` b)
>        
>         Why is gcd 0 0 undefined?
>        
>         http://en.wikipedia.org/wiki/Greatest_common_divisor says:
>         "It is useful to define gcd(0, 0) = 0 and lcm(0, 0) = 0
>         because then the
>         natural numbers become a complete distributive lattice with
>         gcd as meet
>         and lcm as join operation. This extension of the definition is
>         also
>         compatible with the generalization for commutative rings given
>         below."
>        
>         An added advantage, for haskell, of defining gcd 0 0 = 0 is
>         that gcd
>         would change from being a partial function to a total
>         function.
>        
>         Regards,
>         Steve
>        
>        
>        
>         _______________________________________________
>         Beginners mailing list
>         [hidden email]
>         http://www.haskell.org/mailman/listinfo/beginners
>
>

Reply | Threaded
Open this post in threaded view
|

gcd

Daniel Fischer-4
Am Samstag 02 Mai 2009 04:08:16 schrieb Steve:
> On Fri, 2009-05-01 at 16:19 +0200, Peter Verswyvelen wrote:
> > I suggest you forward this to the Haskell Cafe, since it's not really
> > a beginners question, it's a really good question :)

I know that wasn't meant as it was written, but ouch.