Opened 7 years ago

Closed 18 months ago

#13630 closed enhancement (wontfix)

implement padic (x)gcd for fixed mod polynomials

Reported by: saraedum Owned by: roed
Priority: minor Milestone: sage-duplicate/invalid/wontfix
Component: padics Keywords: days71, sd87
Cc: Merged in:
Authors: Julian Rueth Reviewers: Aly Deines
Report Upstream: N/A Work issues:
Branch: u/saraedum/ticket/13630 (Commits) Commit: 183f87d47bc9b49f44dede2d733dc5fbebb39f6e
Dependencies: #13629, #13442, #13539, #13626, #13627 Stopgaps:

Description

Polynomials over the padics only implement an incorrect (x)gcd, see #13439. The attached patch provides a correct implementation for polynomials over fixed modulus rings.

Attachments (1)

trac_13630.patch (49.9 KB) - added by saraedum 7 years ago.

Download all attachments as: .zip

Change History (16)

comment:1 Changed 7 years ago by saraedum

  • Dependencies changed from #13629, #13442 to #13629, #13442, #13539

comment:2 Changed 7 years ago by saraedum

  • Dependencies changed from #13629, #13442, #13539 to #13629, #13442, #13539, #13626, #13627

Changed 7 years ago by saraedum

comment:3 Changed 6 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:4 Changed 5 years ago by niles

  • Branch set to u/niles/ticket/13630
  • Created changed from 10/19/12 23:45:12 to 10/19/12 23:45:12
  • Modified changed from 08/13/13 15:35:53 to 08/13/13 15:35:53

comment:5 Changed 5 years ago by niles

  • Commit set to c4b37439dbe880ab0ad871d512d49edf30eaaf94

rebased to sage 6.0 and converted to git branch; no other changes

merges cleanly in local repository in spite of what trac says


Last 10 new commits:

e3315d8Trac #13626: implemented gcd for padics
c3df981Trac #13441: refactored gcd to not use _gcd calls anymore
aab8e2eMerge branch 'ticket/13441' into ticket/13626
5b6e9c6Trac #13628: refactored xgcd to not use _xgcd calls anymore.
f66e7a2Merge branch 'ticket/13628' into ticket/13627
da9b384Trac #13627: implemented xgcd for padics
861d698Trac #13629: rings can provide _xgcd_univariate_polynomial for xgcd computations
b7fcb0bMerge branch 'ticket/13629' into ticket/13630
b3eee8aTrac #13442: rings can provide _gcd_univariate_polynomial for polynomial factorization
abc6b02Merge branch 'ticket/13442' into ticket/13630

comment:6 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:7 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:8 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:9 Changed 3 years ago by saraedum

  • Branch changed from u/niles/ticket/13630 to u/saraedum/ticket/13630

comment:10 Changed 3 years ago by aly.deines

  • Commit changed from c4b37439dbe880ab0ad871d512d49edf30eaaf94 to 183f87d47bc9b49f44dede2d733dc5fbebb39f6e
  • Reviewers set to Aly Deines

Some of the doctests aren't passing. It looks like everything is correct, formatting just needs to be updated.

aly@aly-laptop:~/Sage/sage$ ./sage -t src/sage/rings/padics/generic_nodes.py 
too few successful tests, not using stored timings
Running doctests with ID 2016-03-22-09-42-58-fac8bd3c.
Git branch: ticket/13630
Using --optional=ccache,mpir,python2,sage
Doctesting 1 file.
sage -t src/sage/rings/padics/generic_nodes.py
**********************************************************************
File "src/sage/rings/padics/generic_nodes.py", line 284, in sage.rings.padics.generic_nodes.pAdicFixedModRingGeneric._gcd_univariate_polynomial
Failed example:
    (t^3).gcd( t^5 )
Expected:
    ((1 + O(3^20))*t^3, 20)
Got:
    ((1 + O(3^20))*t^3 + (O(3^20))*t^2 + (O(3^20))*t + (O(3^20)), 20)
**********************************************************************
File "src/sage/rings/padics/generic_nodes.py", line 368, in sage.rings.padics.generic_nodes.pAdicFixedModRingGeneric._xgcd_univariate_polynomial
Failed example:
    (t^3).xgcd( t^5 )
Expected:
    ((1 + O(3^20))*t^3, 20, (1 + O(3^20)), 0)
Got:
    ((1 + O(3^20))*t^3 + (O(3^20))*t^2 + (O(3^20))*t + (O(3^20)),
     20,
     (1 + O(3^20)),
     0)
**********************************************************************
2 items had failures:
   1 of  34 in sage.rings.padics.generic_nodes.pAdicFixedModRingGeneric._gcd_univariate_polynomial
   1 of  36 in sage.rings.padics.generic_nodes.pAdicFixedModRingGeneric._xgcd_univariate_polynomial
    [110 tests, 2 failures, 0.16 s]
----------------------------------------------------------------------
sage -t src/sage/rings/padics/generic_nodes.py  # 2 doctests failed
----------------------------------------------------------------------
Total time for all tests: 0.2 seconds
    cpu time: 0.2 seconds
    cumulative wall time: 0.2 seconds

aly@aly-laptop:~/Sage/sage$ ./sage -t src/sage/rings/padics/padic_generic.py 
too few successful tests, not using stored timings
Running doctests with ID 2016-03-22-09-44-46-93337901.
Git branch: ticket/13630
Using --optional=ccache,mpir,python2,sage
Doctesting 1 file.
sage -t src/sage/rings/padics/padic_generic.py
**********************************************************************
File "src/sage/rings/padics/padic_generic.py", line 368, in sage.rings.padics.padic_generic.pAdicGeneric.__xgcd_shift
Failed example:
    R._pAdicGeneric__xgcd_shift(R(3),19, 20)
Expected:
    O(3^20)
Got:
    3^20 + O(3^20)
**********************************************************************
File "src/sage/rings/padics/padic_generic.py", line 530, in sage.rings.padics.padic_generic.pAdicGeneric.__xgcd_univariate_polynomial_fixed
Failed example:
    S._pAdicGeneric__xgcd_univariate_polynomial_fixed(t,t)
Expected:
    ((1 + O(3))*t, 1, (1 + O(3))*t, 1, (1 + O(3)), 0)
Got:
    ((1 + O(3))*t + (O(3)), 1, (1 + O(3))*t + (O(3)), 1, (1 + O(3)), 0)
**********************************************************************
File "src/sage/rings/padics/padic_generic.py", line 552, in sage.rings.padics.padic_generic.pAdicGeneric.__xgcd_univariate_polynomial_fixed
Failed example:
    S._pAdicGeneric__xgcd_univariate_polynomial_fixed(g,g.derivative())
Expected:
    ((1 + O(3^2))*t^2 + (1 + O(3^2))*t + (1 + O(3^2)), 1, (3 + O(3^2))*t^2 + (3 + O(3^2))*t + (3 + O(3^2)), 2, (2*3 + O(3^2))*t + (2*3 + O(3^2)), (1 + O(3^2))*t^2)
Got:
    ((1 + O(3^2))*t^2 + (1 + O(3^2))*t + (1 + O(3^2)),
     1,
     (3 + O(3^2))*t^2 + (3 + O(3^2))*t + (3 + O(3^2)),
     2,
     (2*3 + O(3^2))*t + (2*3 + O(3^2)),
     (1 + O(3^2))*t^2 + (O(3^2))*t + (O(3^2)))
**********************************************************************
File "src/sage/rings/padics/padic_generic.py", line 566, in sage.rings.padics.padic_generic.pAdicGeneric.__xgcd_univariate_polynomial_fixed
Failed example:
    S._pAdicGeneric__xgcd_univariate_polynomial_fixed(g,g.derivative())
Expected:
    ((1 + O(3^15))*t + (2 + 2*3 + O(3^15)), 10, (3^5 + O(3^15))*t + (2*3^5 + 2*3^6 + O(3^15)), 15, (3 + 3^2 + 3^6 + 2*3^7 + 2*3^9 + 2*3^10 + 2*3^11 + 3^13 + O(3^15))*t + (3^5 + 2*3^7 + 2*3^8 + 2*3^9 + 3^11 + 3^12 + 3^13 + O(3^15)), (2 + 3 + 2*3^2 + 2*3^3 + 2*3^4 + 3^5 + 2*3^7 + 2*3^11 + 3^12 + 2*3^13 + 3^14 + O(3^15))*t^2 + (1 + 3 + 2*3^4 + 3^7 + 2*3^8 + 3^9 + 3^10 + 2*3^11 + 2*3^12 + 2*3^13 + O(3^15))*t)
Got:
    ((1 + O(3^15))*t + (2 + 2*3 + O(3^15)),
     10,
     (3^5 + O(3^15))*t + (2*3^5 + 2*3^6 + O(3^15)),
     15,
     (3 + 3^2 + 3^6 + 2*3^7 + 2*3^9 + 2*3^10 + 2*3^11 + 3^13 + O(3^15))*t + (3^5 + 2*3^7 + 2*3^8 + 2*3^9 + 3^11 + 3^12 + 3^13 + O(3^15)),
     (2 + 3 + 2*3^2 + 2*3^3 + 2*3^4 + 3^5 + 2*3^7 + 2*3^11 + 3^12 + 2*3^13 + 3^14 + O(3^15))*t^2 + (1 + 3 + 2*3^4 + 3^7 + 2*3^8 + 3^9 + 3^10 + 2*3^11 + 2*3^12 + 2*3^13 + O(3^15))*t + (O(3^15)))
**********************************************************************
File "src/sage/rings/padics/padic_generic.py", line 574, in sage.rings.padics.padic_generic.pAdicGeneric.__xgcd_univariate_polynomial_fixed
Failed example:
    S._pAdicGeneric__xgcd_univariate_polynomial_fixed(g,g.derivative())
Expected:
    ((1 + O(3^30))*t + (2 + 2*3 + O(3^30)), 25, (3^5 + O(3^30))*t + (2*3^5 + 2*3^6 + O(3^30)), 30, (3 + 3^2 + 3^6 + 2*3^7 + 2*3^9 + 2*3^10 + 2*3^13 + 3^15 + 3^16 + 3^17 + 3^18 + 2*3^19 + 2*3^20 + 3^21 + 3^22 + 3^23 + 2*3^24 + 2*3^28 + O(3^30))*t + (3^5 + 2*3^7 + 2*3^8 + 2*3^9 + 3^11 + 3^12 + 3^13 + 3^15 + 2*3^16 + 3^17 + 3^18 + 3^23 + 2*3^25 + 2*3^26 + 2*3^27 + 3^29 + O(3^30)), (2 + 3 + 2*3^2 + 2*3^3 + 2*3^4 + 3^5 + 2*3^7 + 2*3^10 + 2*3^11 + 2*3^13 + 3^14 + 3^15 + 3^16 + 3^17 + 3^20 + 3^21 + 3^22 + 2*3^24 + 2*3^25 + 2*3^26 + 2*3^28 + O(3^30))*t^2 + (1 + 3 + 2*3^4 + 3^7 + 2*3^8 + 3^9 + 2*3^10 + 3^11 + 2*3^15 + 2*3^16 + 2*3^17 + 3^18 + 2*3^19 + 3^20 + 3^21 + 2*3^23 + 3^24 + 3^27 + 2*3^28 + 2*3^29 + O(3^30))*t)
Got:
    ((1 + O(3^30))*t + (2 + 2*3 + O(3^30)),
     25,
     (3^5 + O(3^30))*t + (2*3^5 + 2*3^6 + O(3^30)),
     30,
     (3 + 3^2 + 3^6 + 2*3^7 + 2*3^9 + 2*3^10 + 2*3^13 + 3^15 + 3^16 + 3^17 + 3^18 + 2*3^19 + 2*3^20 + 3^21 + 3^22 + 3^23 + 2*3^24 + 2*3^28 + O(3^30))*t + (3^5 + 2*3^7 + 2*3^8 + 2*3^9 + 3^11 + 3^12 + 3^13 + 3^15 + 2*3^16 + 3^17 + 3^18 + 3^23 + 2*3^25 + 2*3^26 + 2*3^27 + 3^29 + O(3^30)),
     (2 + 3 + 2*3^2 + 2*3^3 + 2*3^4 + 3^5 + 2*3^7 + 2*3^10 + 2*3^11 + 2*3^13 + 3^14 + 3^15 + 3^16 + 3^17 + 3^20 + 3^21 + 3^22 + 2*3^24 + 2*3^25 + 2*3^26 + 2*3^28 + O(3^30))*t^2 + (1 + 3 + 2*3^4 + 3^7 + 2*3^8 + 3^9 + 2*3^10 + 3^11 + 2*3^15 + 2*3^16 + 2*3^17 + 3^18 + 2*3^19 + 3^20 + 3^21 + 2*3^23 + 3^24 + 3^27 + 2*3^28 + 2*3^29 + O(3^30))*t + (O(3^30)))
**********************************************************************
File "src/sage/rings/padics/padic_generic.py", line 592, in sage.rings.padics.padic_generic.pAdicGeneric.__xgcd_univariate_polynomial_fixed
Failed example:
    S._pAdicGeneric__xgcd_univariate_polynomial_fixed(f.change_ring(S), g.change_ring(S))
Expected:
    ((1 + O(3^6))*t + (3 + 2*3^3 + 3^5 + O(3^6)), 3, (1 + O(3^6))*t + (3 + 2*3^3 + 3^5 + O(3^6)), 3, (3^5 + O(3^6))*t^3 + (2*3^4 + 2*3^5 + O(3^6))*t^2 + (3^2 + 3^3 + 2*3^4 + 2*3^5 + O(3^6))*t + (2 + 3 + 2*3^2 + 3^3 + O(3^6)), (3^5 + O(3^6))*t)
Got:
    ((1 + O(3^6))*t + (3 + 2*3^3 + 3^5 + O(3^6)),
     3,
     (1 + O(3^6))*t + (3 + 2*3^3 + 3^5 + O(3^6)),
     3,
     (3^5 + O(3^6))*t^3 + (2*3^4 + 2*3^5 + O(3^6))*t^2 + (3^2 + 3^3 + 2*3^4 + 2*3^5 + O(3^6))*t + (2 + 3 + 2*3^2 + 3^3 + O(3^6)),
     (3^5 + O(3^6))*t + (O(3^6)))
**********************************************************************
2 items had failures:
   1 of   6 in sage.rings.padics.padic_generic.pAdicGeneric.__xgcd_shift
   5 of  70 in sage.rings.padics.padic_generic.pAdicGeneric.__xgcd_univariate_polynomial_fixed
    [206 tests, 6 failures, 0.37 s]
----------------------------------------------------------------------
sage -t src/sage/rings/padics/padic_generic.py  # 6 doctests failed
----------------------------------------------------------------------
Total time for all tests: 0.4 seconds
    cpu time: 0.4 seconds
    cumulative wall time: 0.4 seconds


New commits:

183f87dMerge branch 'develop' into t/13630/ticket/13630

comment:11 Changed 3 years ago by aly.deines

  • Keywords sd71 added

comment:12 Changed 3 years ago by aly.deines

  • Keywords days71 added; sd71 removed

comment:13 Changed 22 months ago by saraedum

  • Keywords sd87 added
  • Milestone changed from sage-6.4 to sage-duplicate/invalid/wontfix
  • Status changed from new to needs_review

This should not be done in this way. Let's reopen a new ticket for that.

comment:14 Changed 22 months ago by saraedum

  • Status changed from needs_review to positive_review

comment:15 Changed 18 months ago by embray

  • Resolution set to wontfix
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.