Hello,
Something is wrong with Ratio in ghc-0.29.
I mean the efficiency.
It looses too much on the large numbers.
In the below example, my home-made addition (and cancellation)
for Fraction Integer win 10 times in speed
- with NO optimisation.
------------------------------------------------------
Possible reason:
in Prelude (+) for Ratio, before applying
reduce (x*y'+x'*y) (y*y')
it worths to pre-cancel things by gcd(y,y')
------------------------------------------------------
- see the below script for addFr and D.Knuth
"The art of the programming".
In the benchmark, nSum costs near the same as nSum'.
This means that the small fractions are good.
And gSum takes 10 time more than gSum' - probably because of
the above cancellation policy. For in gSum the number sizes grow
much more than in nSum.
Sergey Mechveliani
[EMAIL PROTECTED]
------------------------------------------------------------------
------------------------------------------------------------------
-- comparing Fraction - Ratio
main = let ns = [1..500]
rns = reverse ns
xs = zipWith (%) ns rns :: [Rational]
xs' = zipWith (canF "") ns rns :: [Fraction Integer]
gSum = foldl (+) (0%1) xs
gSum' = foldl addFr (zeroFr 0) xs'
nSum = foldl (+) 0 (map numerator xs )
nSum' = foldl (+) 0 (map num xs')
in
writeFile "result" (show gSum) -- gSum' nSum nSum'
------------------------------------------------------------------
addFr :: (GCDRing a,Fractional a) =>
Fraction a -> Fraction a -> Fraction a
addFr (n1:/d1) (n2:/d2) =
let
zr = zero d1
in
case (n1==zr, n2==zr)
of
(True,_ ) -> n2:/d2
(_ ,True) -> n1:/d1
_ -> let g = gcD [d1,d2]
dd1 = d1/g
dd2 = d2/g
n = n1*dd2+n2*dd1
gg = gcD [n,g]
in
canF "i" (n/gg) ((dd1*dd2)*(g/gg))
------------------------------------------------------------------
-- canF is for bringing the intermediate result to the canonical
-- fraction.
-- mode = "g" means to cancel the pair by gcd.
-- "i" by canonical invertible,
-- "" by both.
canF :: GCDRing a => String -> a -> a -> Fraction a
canF mode n d =
let
(zr,un) = (zero d,unity d)
g = gcD [n,d]
cancel a b dv = if dv==un then a:/b
else (divide a dv):/(divide b dv)
in
case (n==zr,d==zr)
of
(_ , True) -> error "(canF n d): zero d \n"
(True, _ ) -> zr:/un
_ ->
(case mode of
"g" -> cancel n d g
"i" -> cancel n d (canInv d)
"" -> let
(n':/d') = cancel n d g
in
cancel n' d' (canInv d')
_ ->
error( "(canFr mode fraction): mode "++
"== \"\" | \"g\" | \"i\" expected \n"
)
)
