id summary reporter owner description type status priority milestone component version resolution keywords cc os architecture failure testcase blockedby blocking related differential
2270 gcd is specialised only for Int dons dons@galois.com "We have the general:
{{{
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)
}}}
And a specialisation for Int only:
{{{
{-# RULES
""gcd/Int->Int->Int"" gcd = gcdInt
#-}
gcdInt (I# a) (I# b) = g a b
where g 0# 0# = error ""GHC.Base.gcdInt: gcd 0 0 is undefined""
g 0# _ = I# absB
g _ 0# = I# absA
g _ _ = I# (gcdInt# absA absB
}}}
Thanks to the gcdInt# primop.
If we use Word here, or other Int types, we get the slow version (which is only 10x slower, surprisingly):
{{{
main = print . sumU
. mapU (gcd 2)
$ enumFromToU 0 (100000000 :: Word)
}}}
Comes out as:
{{{
time ./henning
150000002
./henning 25.73s user 0.05s system 99% cpu 25.936 total
}}}
Versus:
{{{
$ time ./henning
150000002
./henning 2.33s user 0.00s system 99% cpu 2.334 tota
}}}
So there are two things we can do here to improve the situation:
== Step 1: Add rules for getting from the other Int* types to gcdInt# ==
{{{
{-# RULES
""gcd/Int32->Int32->Int32"" gcd = gcdInt32
#-}
gcdInt32 :: Int32 -> Int32 -> Int32
gcdInt32 x y = fromIntegral ((gcd :: Int -> Int -> Int) (fromIntegral x) (fromIntegral y))
}}}
For example, takes the running time from 28 seconds to 2.4seconds, for:
{{{
main = print . sumU
. mapU (gcd 2)
$ enumFromToU 0 (100000000 :: Int32)
}}}
== Step 2: optionally add a gcdWord# ==
We could then also add a gcdWord# primop,or perhaps just following fromIntegral, and test
for negative first, then conditionally dispatch to gcdInt.
What do people think?" bug closed normal 6.12.1 libraries/base 6.8.2 duplicate rules, performance, double, gcd Unknown/Multiple Unknown/Multiple