Actually, it's not necessary to treat differently for
OrderedMonoid/noZeroDivisors. We can simply have
a : % * b : % ==
zero? a or zero? b => 0
construct! concat! [[[ta.Mn*tb.Mn, ta.Cf*tb.Cf]$Term
for tb in b] for ta in a]
we collect all the terms and let "construct" do the heavy lifting.
See my updated patch.
It's possible to do better though, for OrderedMonoid, we can do a
k-way merge, but we don't have such algorithm at hand.
My patch should already make this function much faster by
skipping allocation of temporary result of "+".
--
You received this message because you are subscribed to the Google Groups
"FriCAS - computer algebra system" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To view this discussion on the web visit
https://groups.google.com/d/msgid/fricas-devel/CAGBJN92Dn0Mb5OKZqA3Ckf68qMjmFUnHBomY_5FVAib3XgrWhQ%40mail.gmail.com.
diff --git a/src/algebra/mring.spad b/src/algebra/mring.spad
index 7fd7244a..bc216576 100644
--- a/src/algebra/mring.spad
+++ b/src/algebra/mring.spad
@@ -229,8 +229,8 @@ MonoidRing(R : Ring, M : Monoid) : MonoidRingCategory(R, M) == MRdefinition wher
termless(t1:Term, t2:Term):Boolean == smaller?(t1.k, t2.k)
- construct(x : List Term) : % ==
- xs : List Term := sort(termless, x)
+ construct!(x : List Term) : % ==
+ xs : List Term := sort!(termless, x)
res : List Term := empty()
-- find duplicates
while not empty? xs repeat
@@ -246,6 +246,8 @@ MonoidRing(R : Ring, M : Monoid) : MonoidRingCategory(R, M) == MRdefinition wher
res := cons (t1, res)
res
+ construct(x : List Term) : % == construct! copy x
+
if R has CommutativeRing then
f : M -> R
x : %
@@ -285,59 +287,10 @@ MonoidRing(R : Ring, M : Monoid) : MonoidRingCategory(R, M) == MRdefinition wher
if smaller?(t.Mn, m) then return 0
0
-
- if M has OrderedMonoid then
-
- -- we use that multiplying an ordered list of monoid elements
- -- by a single element respects the ordering
-
- if R has noZeroDivisors then
- a : % * b : % ==
- +/[[[ta.Mn*tb.Mn, ta.Cf*tb.Cf]$Term
- for tb in b ] for ta in reverse a]
- else
- a : % * b : % ==
- +/[[[ta.Mn*tb.Mn, r]$Term
- for tb in b | not zero?(r := ta.Cf*tb.Cf)]
- for ta in reverse a]
- else -- M hasn't OrderedMonoid
-
- -- we cannot assume that mutiplying an ordered list of
- -- monoid elements by a single element respects the ordering:
- -- we have to order and to collect equal terms
- ge : (Term, Term) -> Boolean
- ge(s, t) == not smaller? (s.Mn, t.Mn)
-
- sortAndAdd : List Term -> List Term
- sortAndAdd(liTe) == -- assume liTe not empty
- liTe := sort(ge, liTe)
- m : M := (first liTe).Mn
- cf : R := (first liTe).Cf
- res : List Term := []
- for te in rest liTe repeat
- if m = te.Mn then
- cf := cf + te.Cf
- else
- if not zero? cf then res := cons([m, cf]$Term, res)
- m := te.Mn
- cf := te.Cf
- if not zero? cf then res := cons([m, cf]$Term, res)
- reverse res
-
-
- if R has noZeroDivisors then
- a : % * b : % ==
- zero? a => a
- zero? b => b -- avoid calling sortAndAdd with []
- +/[sortAndAdd [[ta.Mn*tb.Mn, ta.Cf*tb.Cf]$Term
- for tb in b ] for ta in reverse a]
- else
- a : % * b : % ==
- zero? a => a
- zero? b => b -- avoid calling sortAndAdd with []
- +/[sortAndAdd [[ta.Mn*tb.Mn, r]$Term
- for tb in b | not zero?(r := ta.Cf*tb.Cf)]
- for ta in reverse a]
+ a : % * b : % ==
+ zero? a or zero? b => 0
+ construct! concat! [[[ta.Mn*tb.Mn, ta.Cf*tb.Cf]$Term
+ for tb in b] for ta in a]
else -- M hasn't OrderedSet
