Re: Proposal: Make gcd total
On 29 May 2011 01:21, wren ng thornton wrote:
On 5/28/11 8:38 AM, Daniel Fischer wrote:
(By the way, non-negative, like the current positive, is not entirely true, for bounded signed integer types [with twos' complement representation], gcd minBound minBound = gcd minBound 0 = minBound< 0, should that special case be mentioned or should we ignore it like we currently do?)
That's a sticky issue, but one that needs to be documented. Given that the result is always positive with the exception of gcd 0 0, gcd minBound minBound, gcd minBound 0, and gcd 0 minBound, I think these corner cases should be specifically enumerated.
There is a difference: gcd 0 0 follows from a general rule, but the minBound ones are the sort of corner wierdness we get for using fixed-size types. (That is, the former should be mentioned as a non-obvious consequence, the latter as an exception/bug.) Incidentally, gcd (minBound::Int) n currently gives negative results for quite a few values of n.
On Sunday 29 May 2011 12:54:17, Ross Paterson wrote:
On 29 May 2011 01:21, wren ng thornton wrote:
On 5/28/11 8:38 AM, Daniel Fischer wrote:
(By the way, non-negative, like the current positive, is not entirely true, for bounded signed integer types [with twos' complement representation], gcd minBound minBound = gcd minBound 0 = minBound< 0, should that special case be mentioned or should we ignore it like we currently do?)
That's a sticky issue, but one that needs to be documented. Given that the result is always positive with the exception of gcd 0 0, gcd minBound minBound, gcd minBound 0, and gcd 0 minBound, I think these corner cases should be specifically enumerated.
There is a difference: gcd 0 0 follows from a general rule, but the minBound ones are the sort of corner wierdness we get for using fixed-size types. (That is, the former should be mentioned as a non-obvious consequence, the latter as an exception/bug.)
Right.
Incidentally, gcd (minBound::Int) n currently gives negative results for quite a few values of n.
Unless GHC's rewriter kicks in, which rewrites gcd :: Int -> Int -> Int to use GMP's gcd on Integer, in which case only the cases gcd x y = ±minBound produce a negative result with the final fromIntegral (another instance of optimisations changing the behaviour and producing 'better' results than the unoptimised version). Unfortunately, there are no rewrite rules for Int8, ..., Int64, so you'll always get lots of negative results for gcd minBound n on those types. Probably we should change gcd x y = gcd' (abs x) (abs y) to gcd x y = abs (gcd' (abs x) (abs y)) or gcd x y = abs (gcd' x y) to reduce the negative results to those cases where the positive gcd cannot be represented by the type in question.
On 5/29/11 6:54 AM, Ross Paterson wrote:
On 29 May 2011 01:21, wren ng thornton wrote:
On 5/28/11 8:38 AM, Daniel Fischer wrote:
(By the way, non-negative, like the current positive, is not entirely true, for bounded signed integer types [with twos' complement representation], gcd minBound minBound = gcd minBound 0 = minBound< 0, should that special case be mentioned or should we ignore it like we currently do?)
That's a sticky issue, but one that needs to be documented. Given that the result is always positive with the exception of gcd 0 0, gcd minBound minBound, gcd minBound 0, and gcd 0 minBound, I think these corner cases should be specifically enumerated.
There is a difference: gcd 0 0 follows from a general rule, but the minBound ones are the sort of corner wierdness we get for using fixed-size types. (That is, the former should be mentioned as a non-obvious consequence, the latter as an exception/bug.)
Right. /me notices that Daniel Fischer gave the same response. Bugs, especially, need to be documented so that people can use the library with full knowledge of its abilities and limitations. Non-obvious consequences (which are still relevant or intriguing) are best documented because they save reasoning time, and may lead to deeper thinking. -- Live well, ~wren
participants (3)
-
Daniel Fischer -
Ross Paterson -
wren ng thornton