| 1 | (* Copyright (C) 1999-2006 Henry Cejtin, Matthew Fluet, Suresh |
| 2 | * Jagannathan, and Stephen Weeks. |
| 3 | * |
| 4 | * MLton is released under a BSD-style license. |
| 5 | * See the file MLton-LICENSE for details. |
| 6 | *) |
| 7 | |
| 8 | signature EUCLIDEAN_RING_STRUCTS = |
| 9 | sig |
| 10 | include RING_WITH_IDENTITY |
| 11 | |
| 12 | (* Two elements a, b are "unit equivalent" if there is a unit element u |
| 13 | * such that au = b. |
| 14 | *) |
| 15 | |
| 16 | val divMod: t * t -> t * t |
| 17 | val metric: t -> Pervasive.IntInf.int |
| 18 | (* Monics should be an (infinite) stream of all (except for zero and one) |
| 19 | * the representatives of the unit equivalence classes in nondecreasing |
| 20 | * order of metric. |
| 21 | *) |
| 22 | val monics: t Stream.t |
| 23 | (* Map an element to the representative of its unit equivalence class. *) |
| 24 | val unitEquivalent: t -> t |
| 25 | end |
| 26 | |
| 27 | signature EUCLIDEAN_RING = |
| 28 | sig |
| 29 | include EUCLIDEAN_RING_STRUCTS |
| 30 | |
| 31 | val div: t * t -> t |
| 32 | val divides: t * t -> bool |
| 33 | val extendedEuclid: t * t -> t * t * t |
| 34 | val extendedEuclidTerm: t * t * (t * t -> bool) -> t * t * t |
| 35 | val factor: t -> (t * Pervasive.Int.int) list |
| 36 | val gcd: t * t -> t |
| 37 | val isComposite: t -> bool |
| 38 | val isPrime: t -> bool |
| 39 | val lcm: t * t -> t |
| 40 | val primes: t Stream.t |
| 41 | val mod: t * t -> t |
| 42 | end |