| 1 | test_mgcd = ->
|
| 2 | logout("testing mgcd\n")
|
| 3 | for i in [1...100]
|
| 4 | a = mint(i)
|
| 5 | for j in [1...100]
|
| 6 | b = mint(j)
|
| 7 | c = mgcd(a, b)
|
| 8 | d = egcd(a, b)
|
| 9 | if (mcmp(c, d) != 0)
|
| 10 | throw new Error("test_mgcd failed")
|
| 11 | logout("ok\n")
|
| 12 |
|
| 13 | # Euclid's algorithm
|
| 14 |
|
| 15 | egcd = (a, b) ->
|
| 16 | sign_ = 0
|
| 17 | if (MZERO(b))
|
| 18 | stop("divide by zero")
|
| 19 | #b = mcopy(b)
|
| 20 | if (MZERO(a))
|
| 21 | return b
|
| 22 | sign_ = MSIGN(b)
|
| 23 | #a = mcopy(a)
|
| 24 | while (!MZERO(b))
|
| 25 | c = mmod(a, b)
|
| 26 | #mfree(a)
|
| 27 | a = b
|
| 28 | b = c
|
| 29 | a = setSignTo(a,sign_)
|
| 30 | return a
|
| 31 |
|