Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

implement padic (x)gcd for fixed mod polynomials #13630

Closed
saraedum opened this issue Oct 19, 2012 · 14 comments
Closed

implement padic (x)gcd for fixed mod polynomials #13630

saraedum opened this issue Oct 19, 2012 · 14 comments
Assignees
@roed314
Labels
c: padics r: wontfix t: enhancement

Comments

@saraedum
Copy link
Member

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.

Depends on #13629
Depends on #13442
Depends on #13539
Depends on #13626
Depends on #13627

Component: padics

Keywords: days71, sd87

Author: Julian Rueth

Branch/Commit: u/saraedum/ticket/13630 @ 183f87d

Reviewer: Aly Deines

Issue created by migration from https://trac.sagemath.org/ticket/13630
@saraedum saraedum added this to the sage-5.11 milestone Oct 19, 2012
@saraedum
Copy link
Member Author

Changed dependencies from #13629, #13442 to #13629, #13442, #13539

@saraedum
Copy link
Member Author

Changed dependencies from #13629, #13442, #13539 to #13629, #13442, #13539, #13626, #13627

@saraedum
Copy link
Member Author

Attachment: trac_13630.patch.gz

@jdemeyer jdemeyer modified the milestones: sage-5.11, sage-5.12 Aug 13, 2013
@nilesjohnson
Copy link
Mannequin

nilesjohnson mannequin commented Jan 28, 2014

Branch: u/niles/ticket/13630

@nilesjohnson
Copy link
Mannequin

nilesjohnson mannequin commented Jan 28, 2014

comment:5

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

@nilesjohnson
Copy link
Mannequin

nilesjohnson mannequin commented Jan 28, 2014

Commit: c4b3743

@sagetrac-vbraun-spam sagetrac-vbraun-spam mannequin modified the milestones: sage-6.1, sage-6.2 Jan 30, 2014
@sagetrac-vbraun-spam sagetrac-vbraun-spam mannequin modified the milestones: sage-6.2, sage-6.3 May 6, 2014
@sagetrac-vbraun-spam sagetrac-vbraun-spam mannequin modified the milestones: sage-6.3, sage-6.4 Aug 10, 2014
@saraedum
Copy link
Member Author

Changed branch from u/niles/ticket/13630 to u/saraedum/ticket/13630

@adeines
Copy link
Mannequin

adeines mannequin commented Mar 22, 2016

comment:10

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

@adeines
Copy link
Mannequin

adeines mannequin commented Mar 22, 2016

Reviewer: Aly Deines

@adeines
Copy link
Mannequin

adeines mannequin commented Mar 22, 2016

Changed commit from c4b3743 to 183f87d

@adeines
Copy link
Mannequin

adeines mannequin commented Mar 23, 2016

Changed keywords from none to sd71

@adeines
Copy link
Mannequin

adeines mannequin commented Mar 23, 2016

Changed keywords from sd71 to days71

@saraedum
Copy link
Member Author

comment:13

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

@saraedum
Copy link
Member Author

Changed keywords from days71 to days71, sd87

@saraedum saraedum removed this from the sage-6.4 milestone Jul 21, 2017
@embray embray closed this as completed Dec 12, 2017
@saraedum saraedum mentioned this issue Dec 29, 2022
Open
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@roed314 roed314

Labels
c: padics r: wontfix t: enhancement
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
4 participants
@roed314 @saraedum @embray @jdemeyer