1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
|
{-# LANGUAGE MagicHash #-}
{-# LANGUAGE MultiWayIf #-}
module Main (main) where
import GHC.Base
import GHC.Num.Integer
import Control.Monad
import System.Exit
main :: IO ()
main = do
let test a b = do
putStrLn $ "GCDE " ++ show a ++ " " ++ show b
let r@(g,x,y) = integerGcde a b
putStrLn $ " -> g = " ++ show g
putStrLn $ " -> x = " ++ show x
putStrLn $ " -> y = " ++ show y
let sign a | a >= 0 = 1
| otherwise = -1
let assert text cond term
| not cond = return ()
| term = return ()
| otherwise = do
putStrLn $ "FAILED: " ++ text
putStrLn $ "a*x + b*y = g"
putStrLn $ "a = " ++ show a
putStrLn $ "b = " ++ show b
putStrLn $ "x = " ++ show x
putStrLn $ "y = " ++ show y
putStrLn $ "g = " ++ show g
putStrLn $ "expected g = " ++ show (abs (integerGcd a b))
exitFailure
-- check properties
assert "g >= 0" True (g >= 0)
assert "a*x + b*y = g" True (a*x + b*y == g)
assert "g = abs (gcd a b)" True (g == abs (integerGcd a b))
if -- special cases
| a == 0 && b == 0 -> do
assert "a == 0 && b ==0 ==> g == 0" (a == 0 && b == 0) (g == 0)
| abs a == abs b -> do
assert "abs a == abs b ==> x == 0 && y == sign b && g == abs a"
(abs a == abs b) (x == 0 && y == sign b && g == abs a)
-- non special cases
| otherwise -> do
assert "b == 0 ==> x=sign a"
(b == 0)
(x == sign a)
assert "abs b == 2g ==> x=sign a"
(abs b == 2*g)
(x == sign a)
assert "b /= 0 ==> abs x <= abs b / 2*g"
(b /= 0)
(abs x <= abs b `div` 2 * g)
assert "a /= 0 ==> abs y <= abs a / 2*g"
(a /= 0)
(abs y <= abs a `div` 2 * g)
assert "a == 0 ==> y=sign b"
(a == 0)
(y == sign b)
assert "abs a == 2g ==> y==sign b"
(abs a == 2*g)
(y == sign b)
assert "x == 0 ==> g == abs b"
(x == 0)
(g == abs b)
nums =
[ 0
, 1
, 7
, 14
, 123
, 1230
, 123456789456789456789456789456789456789465789465456789465454645789
, 4 * 123456789456789456789456789456789456789465789465456789465454645789
, -1
, -123
, -123456789456789456789456789456789456789465789465456789465454645789
, 4567897897897897899789897897978978979789
, 2988348162058574136915891421498819466320163312926952423791023078876139
, 2351399303373464486466122544523690094744975233415544072992656881240319
, 5328841272400314897981163497728751426
, 32052182750761975518649228050096851724
]
forM_ nums $ \a ->
forM_ nums $ \b ->
test a b
-- see #15350
do
let a = 2
b = 2^65 + 1
test a b
test a (-b)
test (-a) b
test (-a) (-b)
test b a
test b (-a)
test (-b) a
test (-b) (-a)
|
