← Back to branch summary

~dinko-metalac/calculus-app2/trunk

« back to all changes in this revision

Viewing changes to lib/py/sympy/polys/euclidtools.py

  • Committer: dinko.metalac at gmail
  • Date: 2015-04-14 13:28:14 UTC
  • Revision ID: dinko.metalac@gmail.com-20150414132814-j25k3qd7sq3warup
new sympy

Show diffs side-by-side

added added

removed removed

Lines of Context:
lib/py/sympy/polys/euclidtools.py
1
1
"""Euclidean algorithms, GCDs, LCMs and polynomial remainder sequences. """
2
2
 
 
3
from __future__ import print_function, division
 
4
 
3
5
from sympy.polys.densebasic import (
4
6
    dup_strip, dmp_raise,
5
7
    dmp_zero, dmp_one, dmp_ground,
48
50
 
49
51
from sympy.polys.polyconfig import query
50
52
 
51
 
from sympy.utilities import cythonized
52
 
 
53
53
from sympy.ntheory import nextprime
54
54
 
 
55
from sympy.core.compatibility import xrange
 
56
 
55
57
 
56
58
def dup_half_gcdex(f, g, K):
57
59
    """
72
74
    (-1/5*x + 3/5, x + 1)
73
75
 
74
76
    """
75
 
    if not (K.has_Field or not K.is_Exact):
 
77
    if not K.has_Field:
76
78
        raise DomainError("can't compute half extended GCD over %s" % K)
77
79
 
78
80
    a, b = [K.one], []
311
313
        raise MultivariatePolynomialError(f, g)
312
314
 
313
315
 
314
 
@cythonized("n,m,d,k")
315
316
def dup_inner_subresultants(f, g, K):
316
317
    """
317
318
    Subresultant PRS algorithm in `K[x]`.
395
396
    return dup_inner_subresultants(f, g, K)[0]
396
397
 
397
398
 
398
 
@cythonized("s,i,du,dv,dw")
399
399
def dup_prs_resultant(f, g, K):
400
400
    """
401
401
    Resultant algorithm in `K[x]` using subresultant PRS.
442
442
    i = dup_degree(R[-2])
443
443
 
444
444
    res = dup_LC(R[-1], K)**i
445
 
 
446
445
    res = K.quo(res*p, q)
447
446
 
448
447
    return res, R
467
466
    return dup_prs_resultant(f, g, K)[0]
468
467
 
469
468
 
470
 
@cythonized("u,v,n,m,d,k")
471
469
def dmp_inner_subresultants(f, g, u, K):
472
470
    """
473
471
    Subresultant PRS algorithm in `K[X]`.
546
544
    return R, B, D
547
545
 
548
546
 
549
 
@cythonized("u")
550
547
def dmp_subresultants(f, g, u, K):
551
548
    """
552
549
    Computes subresultant PRS of two polynomials in `K[X]`.
570
567
    return dmp_inner_subresultants(f, g, u, K)[0]
571
568
 
572
569
 
573
 
@cythonized("u,v,s,i,d,du,dv,dw")
574
570
def dmp_prs_resultant(f, g, u, K):
575
571
    """
576
572
    Resultant algorithm in `K[X]` using subresultant PRS.
642
638
    return res, R
643
639
 
644
640
 
645
 
@cythonized("u,v,n,m,N,M,B")
646
641
def dmp_zz_modular_resultant(f, g, p, u, K):
647
642
    """
648
643
    Compute resultant of `f` and `g` modulo a prime `p`.
721
716
    return gf_int(gf_crt([r, R], [P, p], K), P*p)
722
717
 
723
718
 
724
 
@cythonized("u,v,n,m")
725
719
def dmp_zz_collins_resultant(f, g, u, K):
726
720
    """
727
721
    Collins's modular resultant algorithm in `Z[X]`.
781
775
    return r
782
776
 
783
777
 
784
 
@cythonized("u,n,m")
785
778
def dmp_qq_collins_resultant(f, g, u, K0):
786
779
    """
787
780
    Collins's modular resultant algorithm in `Q[X]`.
821
814
    return dmp_quo_ground(r, c, u - 1, K0)
822
815
 
823
816
 
824
 
@cythonized("u")
825
817
def dmp_resultant(f, g, u, K, includePRS=False):
826
818
    """
827
819
    Computes resultant of two polynomials in `K[X]`.
855
847
    return dmp_prs_resultant(f, g, u, K)[0]
856
848
 
857
849
 
858
 
@cythonized("d,s")
859
850
def dup_discriminant(f, K):
860
851
    """
861
852
    Computes discriminant of a polynomial in `K[x]`.
883
874
        return K.quo(r, c*K(s))
884
875
 
885
876
 
886
 
@cythonized("u,v,d,s")
887
877
def dmp_discriminant(f, u, K):
888
878
    """
889
879
    Computes discriminant of a polynomial in `K[X]`.
945
935
        return None
946
936
 
947
937
 
948
 
@cythonized("u")
949
938
def _dmp_rr_trivial_gcd(f, g, u, K):
950
939
    """Handle trivial cases in GCD algorithm over a ring. """
951
940
    zero_f = dmp_zero_p(f, u)
969
958
        return None
970
959
 
971
960
 
972
 
@cythonized("u")
973
961
def _dmp_ff_trivial_gcd(f, g, u, K):
974
962
    """Handle trivial cases in GCD algorithm over a field. """
975
963
    zero_f = dmp_zero_p(f, u)
991
979
        return None
992
980
 
993
981
 
994
 
@cythonized("u,v,df,dg")
995
982
def _dmp_simplify_gcd(f, g, u, K):
996
983
    """Try to eliminate `x_0` from GCD computation in `K[X]`. """
997
984
    df = dmp_degree(f, u)
1092
1079
    return h, cff, cfg
1093
1080
 
1094
1081
 
1095
 
@cythonized("u")
1096
1082
def dmp_rr_prs_gcd(f, g, u, K):
1097
1083
    """
1098
1084
    Computes polynomial GCD using subresultants over a ring.
1139
1125
    return h, cff, cfg
1140
1126
 
1141
1127
 
1142
 
@cythonized("u")
1143
1128
def dmp_ff_prs_gcd(f, g, u, K):
1144
1129
    """
1145
1130
    Computes polynomial GCD using subresultants over a field.
1202
1187
    return f
1203
1188
 
1204
1189
 
1205
 
@cythonized("i,df,dg")
1206
1190
def dup_zz_heu_gcd(f, g, K):
1207
1191
    """
1208
1192
    Heuristic polynomial GCD in `Z[x]`.
1260
1244
            2*min(f_norm // abs(dup_LC(f, K)),
1261
1245
                  g_norm // abs(dup_LC(g, K))) + 2)
1262
1246
 
1263
 
    for i in range(0, HEU_GCD_MAX):
 
1247
    for i in xrange(0, HEU_GCD_MAX):
1264
1248
        ff = dup_eval(f, x, K)
1265
1249
        gg = dup_eval(g, x, K)
1266
1250
 
1309
1293
    raise HeuristicGCDFailed('no luck')
1310
1294
 
1311
1295
 
1312
 
@cythonized("v")
1313
1296
def _dmp_zz_gcd_interpolate(h, x, v, K):
1314
1297
    """Interpolate polynomial GCD from integer GCD. """
1315
1298
    f = []
1327
1310
        return f
1328
1311
 
1329
1312
 
1330
 
@cythonized("u,v,i,dg,df")
1331
1313
def dmp_zz_heu_gcd(f, g, u, K):
1332
1314
    """
1333
1315
    Heuristic polynomial GCD in `Z[X]`.
1387
1369
            2*min(f_norm // abs(dmp_ground_LC(f, u, K)),
1388
1370
                  g_norm // abs(dmp_ground_LC(g, u, K))) + 2)
1389
1371
 
1390
 
    for i in range(0, HEU_GCD_MAX):
 
1372
    for i in xrange(0, HEU_GCD_MAX):
1391
1373
        ff = dmp_eval(f, x, u, K)
1392
1374
        gg = dmp_eval(g, x, u, K)
1393
1375
 
1484
1466
    return h, cff, cfg
1485
1467
 
1486
1468
 
1487
 
@cythonized("u")
1488
1469
def dmp_qq_heu_gcd(f, g, u, K0):
1489
1470
    """
1490
1471
    Heuristic polynomial GCD in `Q[X]`.
1551
1532
    (x - 1, x + 1, x - 2)
1552
1533
 
1553
1534
    """
1554
 
    if K.has_Field or not K.is_Exact:
 
1535
    if not K.is_Exact:
 
1536
        try:
 
1537
            exact = K.get_exact()
 
1538
        except DomainError:
 
1539
            return [K.one], f, g
 
1540
 
 
1541
        f = dup_convert(f, K, exact)
 
1542
        g = dup_convert(g, K, exact)
 
1543
 
 
1544
        h, cff, cfg = dup_inner_gcd(f, g, exact)
 
1545
 
 
1546
        h = dup_convert(h, exact, K)
 
1547
        cff = dup_convert(cff, exact, K)
 
1548
        cfg = dup_convert(cfg, exact, K)
 
1549
 
 
1550
        return h, cff, cfg
 
1551
    elif K.has_Field:
1555
1552
        if K.is_QQ and query('USE_HEU_GCD'):
1556
1553
            try:
1557
1554
                return dup_qq_heu_gcd(f, g, K)
1569
1566
        return dup_rr_prs_gcd(f, g, K)
1570
1567
 
1571
1568
 
1572
 
@cythonized("u")
1573
1569
def _dmp_inner_gcd(f, g, u, K):
1574
1570
    """Helper function for `dmp_inner_gcd()`. """
1575
 
    if K.has_Field or not K.is_Exact:
 
1571
    if not K.is_Exact:
 
1572
        try:
 
1573
            exact = K.get_exact()
 
1574
        except DomainError:
 
1575
            return dmp_one(u, K), f, g
 
1576
 
 
1577
        f = dmp_convert(f, u, K, exact)
 
1578
        g = dmp_convert(g, u, K, exact)
 
1579
 
 
1580
        h, cff, cfg = _dmp_inner_gcd(f, g, u, exact)
 
1581
 
 
1582
        h = dmp_convert(h, u, exact, K)
 
1583
        cff = dmp_convert(cff, u, exact, K)
 
1584
        cfg = dmp_convert(cfg, u, exact, K)
 
1585
 
 
1586
        return h, cff, cfg
 
1587
    elif K.has_Field:
1576
1588
        if K.is_QQ and query('USE_HEU_GCD'):
1577
1589
            try:
1578
1590
                return dmp_qq_heu_gcd(f, g, u, K)
1590
1602
        return dmp_rr_prs_gcd(f, g, u, K)
1591
1603
 
1592
1604
 
1593
 
@cythonized("u")
1594
1605
def dmp_inner_gcd(f, g, u, K):
1595
1606
    """
1596
1607
    Computes polynomial GCD and cofactors of `f` and `g` in `K[X]`.
1639
1650
    return dup_inner_gcd(f, g, K)[0]
1640
1651
 
1641
1652
 
1642
 
@cythonized("u")
1643
1653
def dmp_gcd(f, g, u, K):
1644
1654
    """
1645
1655
    Computes polynomial GCD of `f` and `g` in `K[X]`.
1722
1732
    x**3 - 2*x**2 - x + 2
1723
1733
 
1724
1734
    """
1725
 
    if K.has_Field or not K.is_Exact:
 
1735
    if K.has_Field:
1726
1736
        return dup_ff_lcm(f, g, K)
1727
1737
    else:
1728
1738
        return dup_rr_lcm(f, g, K)
1729
1739
 
1730
1740
 
1731
 
@cythonized("u")
1732
1741
def dmp_rr_lcm(f, g, u, K):
1733
1742
    """
1734
1743
    Computes polynomial LCM over a ring in `K[X]`.
1757
1766
    return dmp_mul_ground(h, c, u, K)
1758
1767
 
1759
1768
 
1760
 
@cythonized("u")
1761
1769
def dmp_ff_lcm(f, g, u, K):
1762
1770
    """
1763
1771
    Computes polynomial LCM over a field in `K[X]`.
1781
1789
    return dmp_ground_monic(h, u, K)
1782
1790
 
1783
1791
 
1784
 
@cythonized("u")
1785
1792
def dmp_lcm(f, g, u, K):
1786
1793
    """
1787
1794
    Computes polynomial LCM of `f` and `g` in `K[X]`.
1802
1809
    if not u:
1803
1810
        return dup_lcm(f, g, K)
1804
1811
 
1805
 
    if K.has_Field or not K.is_Exact:
 
1812
    if K.has_Field:
1806
1813
        return dmp_ff_lcm(f, g, u, K)
1807
1814
    else:
1808
1815
        return dmp_rr_lcm(f, g, u, K)
1809
1816
 
1810
1817
 
1811
 
@cythonized("u,v")
1812
1818
def dmp_content(f, u, K):
1813
1819
    """
1814
1820
    Returns GCD of multivariate coefficients.
1840
1846
        return cont
1841
1847
 
1842
1848
 
1843
 
@cythonized("u,v")
1844
1849
def dmp_primitive(f, u, K):
1845
1850
    """
1846
1851
    Returns multivariate content and a primitive polynomial.
1907
1912
    _, p, q = dmp_inner_gcd(f, g, u, K)
1908
1913
 
1909
1914
    if K0 is not None:
 
1915
        _, cp, cq = K.cofactors(cp, cq)
 
1916
 
1910
1917
        p = dmp_convert(p, u, K, K0)
1911
1918
        q = dmp_convert(q, u, K, K0)
1912
1919