Hello, in extension of what Qian provided, I've tried to remove recursion also in other places of the gbintern code.
https://github.com/hemmecke/fricas/commits/no-gb-recursion I'd like to commit that to the svn repo. Can someone please review the attached patch? Ralf -- 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 post to this group, send email to [email protected]. Visit this group at https://groups.google.com/group/fricas-devel. For more options, visit https://groups.google.com/d/optout.
From 8bc1e6b6b6a444a9dfcca921fc337395ffac6347 Mon Sep 17 00:00:00 2001 From: Ralf Hemmecke <[email protected]> Date: Wed, 13 Sep 2017 23:26:13 +0200 Subject: avoid recursion in critical pair list update --- src/algebra/gbintern.spad | 38 ++++++++++++++++++++------------------ 1 file changed, 20 insertions(+), 18 deletions(-) diff --git a/src/algebra/gbintern.spad b/src/algebra/gbintern.spad index 0003336..2345cbd 100644 --- a/src/algebra/gbintern.spad +++ b/src/algebra/gbintern.spad @@ -166,10 +166,7 @@ GroebnerInternalPackage(Dom, Expon, VarSet, Dpol) : T == C where --- erase multiple of e in D2 using crit M critMonD1(e : Expon, D2 : List(critPair))== - empty?(D2) => [] - x := first(D2) - critM(e, x.lcmfij) => critMonD1(e, rest(D2)) - cons(x, critMonD1(e, rest(D2))) + [x for x in D2 | not critM(e, x.lcmfij)] ---------------------------- @@ -191,38 +188,43 @@ GroebnerInternalPackage(Dom, Expon, VarSet, Dpol) : T == C where cT1 => critMTonD1(D1) cons(f1, critMTonD1(D1)) + ----------------------------- --- erase elements in D fullfilling crit B critBonD(h : Dpol, D : List(critPair))== - empty?(D) => [] - x := first(D) - critB(degree(h), x.lcmfij, degree(x.poli), degree(x.polj)) => - critBonD(h, rest(D)) - cons(x, critBonD(h, rest(D))) + d := degree(h) + [x for x in D | not critB(d, x.lcmfij, degree(x.poli), degree(x.polj))] ----------------------------- --- concat F and h and erase multiples of h in F updatF(h : Dpol, deg : NNI, F : List(sugarPol)) == - empty?(F) => [[deg, h]] - f1 := first(F) - critM(degree(h), degree(f1.pol)) => updatF(h, deg, rest(F)) - cons(f1, updatF(h, deg, rest(F))) + d := degree h + concat!([f for f in F | not critM(d, degree(f.pol))], [deg, h]$sugarPol) ----------------------------- - --- concat ordered critical pair lists D1 and D2 + --- merge ordered critical pair lists D1 and D2 updatD(D1 : List(critPair), D2 : List(critPair)) == empty?(D1) => D2 empty?(D2) => D1 - dl1 := first(D1) - dl2 := first(D2) - critpOrder(dl1, dl2) => cons(dl1, updatD(D1.rest, D2)) - cons(dl2, updatD(D1, D2.rest)) + res: List(critPair) := [] + while not empty? D1 and not empty? D2 repeat + dl1 := first D1 + dl2 := first D2 + if critpOrder(dl1, dl2) then + res := cons(dl1, res) + D1 := rest D1 + else + res := cons(dl2, res) + D2 := rest D2 + for e in D1 repeat res := cons(e, res) + for e in D2 repeat res := cons(e, res) + reverse! res ----------------------------- -- 2.7.4
