diff options
| author | dos-reis <gdr@axiomatics.org> | 2011-02-25 23:56:54 +0000 |
|---|---|---|
| committer | dos-reis <gdr@axiomatics.org> | 2011-02-25 23:56:54 +0000 |
| commit | 0ee1ea72c939e760c274f2eaff8afa73a629ae60 (patch) | |
| tree | 05eb85f57186c9ab468b787c1f0b24120f92b938 /src/algebra | |
| parent | b71fd7a811c516e8ca2a8a3f4ad578e9f637596b (diff) | |
| download | open-axiom-0ee1ea72c939e760c274f2eaff8afa73a629ae60.tar.gz | |
* algebra/fmod.spad.pamphlet (IntegerMod): Simplify implementation.
Diffstat (limited to 'src/algebra')
| -rw-r--r-- | src/algebra/fmod.spad.pamphlet | 123 |
1 files changed, 53 insertions, 70 deletions
diff --git a/src/algebra/fmod.spad.pamphlet b/src/algebra/fmod.spad.pamphlet index bcbbd597..b40501f5 100644 --- a/src/algebra/fmod.spad.pamphlet +++ b/src/algebra/fmod.spad.pamphlet @@ -27,77 +27,60 @@ IntegerMod(p:PositiveInteger): Join(CommutativeRing, Finite, ConvertibleTo Integer, StepThrough) == add - size() == p + Rep == Integer + size() == p characteristic == p - lookup x == (zero? x => p; (convert(x)@Integer) :: PositiveInteger) - --- Code is duplicated for the optimizer to kick in. - if p <= convert(max()$SingleInteger)@Integer then - Rep:= SingleInteger - q := p::SingleInteger - - bloodyCompiler: Integer -> % - bloodyCompiler n == positiveRemainder(n, p)$Integer :: Rep - - convert(x:%):Integer == convert(x)$Rep - coerce(x):OutputForm == coerce(x)$Rep - coerce(n:Integer):% == bloodyCompiler n - 0 == 0$Rep - 1 == 1$Rep - init == 0$Rep - nextItem(n) == - m:=n+1 - m=0 => "failed" - m - x = y == x =$Rep y - x:% * y:% == mulmod(x, y, q) - n:Integer * x:% == mulmod(bloodyCompiler n, x, q) - x + y == addmod(x, y, q) - x - y == submod(x, y, q) - random() == random(q)$Rep - index a == positiveRemainder(a::%, q) - - x == (zero? x => 0; q -$Rep x) - - x:% ** n:NonNegativeInteger == - n < p => powmod(x, n::Rep, q) - powmod(convert(x)@Integer, n, p)$Integer :: Rep - - recip x == - (c1, c2, g) := extendedEuclidean(x, q)$Rep - not one? g => "failed" - positiveRemainder(c1, q) - - before?(x,y) == before?(x,y)$Rep - - else - Rep:= Integer - - convert(x:%):Integer == convert(x)$Rep - coerce(n:Integer):% == positiveRemainder(n::Rep, p) - coerce(x):OutputForm == coerce(x)$Rep - 0 == 0$Rep - 1 == 1$Rep - init == 0$Rep - nextItem(n) == - m:=n+1 - m=0 => "failed" - m - x = y == x =$Rep y - x:% * y:% == mulmod(x, y, p) - n:Integer * x:% == mulmod(positiveRemainder(n::Rep, p), x, p) - x + y == addmod(x, y, p) - x - y == submod(x, y, p) - random() == random(p)$Rep - index a == positiveRemainder(a::Rep, p) - - x == (zero? x => 0; p -$Rep x) - x:% ** n:NonNegativeInteger == powmod(x, n::Rep, p) - - recip x == - (c1, c2, g) := extendedEuclidean(x, p)$Rep - not one? g => "failed" - positiveRemainder(c1, p) - - before?(x,y) == before?(x,y)$Rep + lookup x == + zero? x => p + rep(x)::PositiveInteger + + convert(x: %): Integer == rep x + coerce(n: Integer): % == per positiveRemainder(n,p) + coerce(x): OutputForm == rep(x)::OutputForm + 0 == per(0$Rep) + 1 == per(1$Rep) + init == 0 + nextItem(n) == + m := n+1 + m = 0 => "failed" + m + + zero? x == rep x = 0 + one? x == rep x = 1 + + x = y == + rep x = rep y + + x:% * y:% == + per mulmod(rep x,rep y,p) + + n:Integer * x:% == + per mulmod(positiveRemainder(n, p), rep x, p) + + x + y == + per addmod(rep x,rep y,p) + + x - y == + per submod(rep x,rep y,p) + + random() == per random(p)$Rep + + index a == + per positiveRemainder(a,p) + + -x == + zero? rep x => 0 + per(p - rep x) + + x:% ** n:NonNegativeInteger == + per powmod(rep x, n, p) + + recip x == + (c1, c2, g) := extendedEuclidean(rep x, p)$Rep + not one? g => "failed" + per positiveRemainder(c1, p) + + before?(x,y) == before?(rep x,rep y) @ \section{License} |