Earlier, i presented a benchmark to compare the Int vs Integer
performance.
It has to be improved.
For, increasing d from proposed d = 40 on, brings in the numbers
that may be large enough to spoil the test.
The enclosed script contains a slight modification - mostly, max'
instead of sum. This settles everything.
------------------
Sergey Mechveliani
[EMAIL PROTECTED]
--------------------------------------------------------------------
-- choose d from [100..9000] and switch Z = Int,Integer
type Z = Integer
main = -- compute extendedGCD x y = (g,u,v)
-- for many x,y and find maximum [abs (g+u+v)]
let
d = 200 :: Z
(n,m) = (5000,10000) :: (Z,Z)
ns = [n..(n+d)]
ms = [m..(m+d)]
pairs = [(x,y)| x<-ns, y<-ms] -- (d+1)^2 of pairs
tripls = map (\ (x,y)->(x,y,gcdE x y)) pairs
rs = map (\ (_,_,(g,u,v))-> abs (g+u+v)) tripls
max' [x] = x
max' (x:y:xs) = if x<y then max' (y:xs) else max' (x:xs)
-- boo = all test tripls -- this tests gcdE
in
putStr (shows (max' rs) "\n")
test (x,y,(d,u,v)) = d==(u*x+v*y) && d==(gcd x y)
-- gcdE x y -> (d,u,v): d = gcd(x,y) = u*x + v*y
gcdE :: Integral a => a -> a -> (a,a,a)
gcdE 0 y = (y,0,1)
gcdE x y = g (1,0,x) (0,1,y)
where
g (u1,u2,u3) (v1,v2,v3) =
if v3==0 then (u3,u1,u2)
else
case quotRem u3 v3
of
(q,r) -> g (v1,v2,v3) (u1-q*v1, u2-q*v2, r)
