GCD

[Kent Karlsson]

I don't think preorders of any kind should be involved here.
Just the ordinary order on integers. No divisibility preorder (I'm not
sure how that is even defined, so how it could be natural beats me), no
absolute value.

I find the unaltered text Simon quoted to be fine as is.

But for those who like to be more precise (forgive the TeXese):


% Most of you may wish to stop reading at this point.



% I is the set of integers representable in the integral datatype.
% result_I may return "overflow" or the argument, as appropriate.

\begin{example}\atab
	  $gcd_I : I \times I \rightarrow I \cup \{\overflow, \infinitary\}$
\end{example}
\begin{example}\atab
	  $gcd_I(x,y)$
		\>$= result_I(\max\{v \in \ZZ ~~|~~ v|x $ and  $v|y\})$\\
		\>					\>if $x,y \in I$ and ($x \neq 0$ or  $y \neq 0$)\\
		\>$= \infinitary(\posinf)$	\>if $x = 0$ and $y = 0$
\end{example}

% There is no need to say "v>0" above, since there are always positive values in that
% set, and max picks the largest/greatest one.  0 has all integer values except(!) 0
% as divisors. So for gcd 0 0 (maximum, supremum really, of the intersection of the two
% sets of divisors) the result is really positive infinity, which should be the result
% returned when representable (recommendable for Haskell's Integer datatype). gcd will
% overflow for instances like gcd (minBound::Int) (minBound::Int). 

\begin{example}\atab\\
	  $lcm_I : I \times I \rightarrow I \cup \{\overflow\}$
\end{example}
\begin{example}\atab
	  $lcm_I(x,y)$
		\>$= result_I(\min\{v \in \ZZ ~~|~~ x|v $ and $ y|v $ and $ v > 0\})$\\
		\>			\>if $x,y \in I$ and $x \neq 0$ and $y \neq 0$\\
		\>$= 0$		\>if $x,y \in I$ and ($x = 0$ or  $y = 0$)
\end{example}

% the "v>0" is needed here, since the set here would otherwise always contain
% infinitely many negative values, and then minimum of that...




		Kind regards
		/kent k



> -----Original Message-----
> From: haskell-admin@haskell.org [mailto:haskell-admin@haskell.org]On
> Behalf Of S.M.Kahrs
> Sent: den 11 december 2001 11:21
> To: haskell@haskell.org
> Subject: Re: GCD
> 
> 
> The natural reading of 'greatest' is, of course,
> the greatest in the divisibility preorder (it's partial order
> on natural numbers but only a preorder on integers).
> Thus, gcd 0 0 = 0.
> 
> 3 and -3 are equivalent in that preoder.
> 
> Thus, an additional comment may be in order.
> 
> Stefan
> 
> _______________________________________________
> Haskell mailing list
> Haskell@haskell.org
> http://www.haskell.org/mailman/listinfo/haskell