Did I find the right examples for you? yes no      Crawl my project      Python Jobs

All Samples(11)  |  Call(8)  |  Derive(0)  |  Import(3)
Chinese Remainder Theorem.

The moduli in m are assumed to be pairwise coprime.  The output
is then an integer f, such that f = v_i mod m_i for each pair out
of v and m. If ``symmetric`` is False a positive integer will be
returned, else \|f\| will be less than or equal to the LCM of the
moduli, and thus f may be negative.

If the moduli are not co-prime the correct result will be returned
if/when the test of the result is found to be incorrect. This result(more...)

        def crt(m, v, symmetric=False, check=True):
    r"""Chinese Remainder Theorem.

    The moduli in m are assumed to be pairwise coprime.  The output
    is then an integer f, such that f = v_i mod m_i for each pair out
    of v and m. If ``symmetric`` is False a positive integer will be
    returned, else \|f\| will be less than or equal to the LCM of the
    moduli, and thus f may be negative.

    If the moduli are not co-prime the correct result will be returned
    if/when the test of the result is found to be incorrect. This result
    will be None if there is no solution.

    The keyword ``check`` can be set to False if it is known that the moduli
    are coprime.

    As an example consider a set of residues ``U = [49, 76, 65]``
    and a set of moduli ``M = [99, 97, 95]``. Then we have::

       >>> from sympy.ntheory.modular import crt, solve_congruence

       >>> crt([99, 97, 95], [49, 76, 65])
       (639985, 912285)

    This is the correct result because::

       >>> [639985 % m for m in [99, 97, 95]]
       [49, 76, 65]

    If the moduli are not co-prime, you may receive an incorrect result
    if you use ``check=False``:

       >>> crt([12, 6, 17], [3, 4, 2], check=False)
       (954, 1224)
       >>> [954 % m for m in [12, 6, 17]]
       [6, 0, 2]
       >>> crt([12, 6, 17], [3, 4, 2]) is None
       True
       >>> crt([3, 6], [2, 5])
       (5, 6)

    Note: the order of gf_crt's arguments is reversed relative to crt,
    and that solve_congruence takes residue, modulus pairs.

    Programmer's note: rather than checking that all pairs of moduli share
    no GCD (an O(n**2) test) and rather than factoring all moduli and seeing
    that there is no factor in common, a check that the result gives the
    indicated residuals is performed -- an O(n) operation.

    See Also
    ========

    solve_congruence
    sympy.polys.galoistools.gf_crt : low level crt routine used by this routine
    """
    if check:
        m = list(map(as_int, m))
        v = list(map(as_int, v))

    result = gf_crt(v, m, ZZ)
    mm = prod(m)

    if check:
        if not all(v % m == result % m for v, m in zip(v, m)):
            result = solve_congruence(*list(zip(v, m)),
                    check=False, symmetric=symmetric)
            if result is None:
                return result
            result, mm = result

    if symmetric:
        return symmetric_residue(result, mm), mm
    return result, mm
        


src/s/y/sympy-0.7.5/sympy/ntheory/tests/test_ntheory.py   sympy(Download)
from sympy.ntheory.primetest import _mr_safe_helper, mr
from sympy.ntheory.bbp_pi import pi_hex_digits
from sympy.ntheory.modular import crt, crt1, crt2, solve_congruence
 
from sympy.polys.domains import ZZ
    def mcrt(m, v, r, symmetric=False):
        assert crt(m, v, symmetric)[0] == r
        mm, e, s = crt1(m)
        assert crt2(m, v, mm, e, s, symmetric) == (r, mm)
 
    mcrt([2, 3, 5], [-1, -1, -1], 2*3*5 - 1, False)
 
    assert crt([656, 350], [811, 133], symmetric=True) == (-56917, 114800)
 
 

src/s/y/sympy-HEAD/sympy/ntheory/tests/test_ntheory.py   sympy(Download)
from sympy.ntheory.primetest import _mr_safe_helper, mr
from sympy.ntheory.bbp_pi import pi_hex_digits
from sympy.ntheory.modular import crt, crt1, crt2, solve_congruence
 
from sympy.utilities.pytest import raises
    def mcrt(m, v, r, symmetric=False):
        assert crt(m, v, symmetric)[0] == r
        mm, e, s = crt1(m)
        assert crt2(m, v, mm, e, s, symmetric) == (r, mm)
 
    mcrt([2, 3, 5], [-1, -1, -1], 2*3*5 - 1, False)
 
    assert crt([656, 350], [811, 133], symmetric=True) == (-56917, 114800)
 
 

src/s/y/sympy-polys-HEAD/sympy/ntheory/tests/test_ntheory.py   sympy-polys(Download)
from sympy import factorial as fac
 
from sympy.ntheory.modular import crt, crt1, crt2
 
def test_trailing():
def test_crt():
    assert crt([2, 3, 5], [0, 0, 0]) == 0
    assert crt([2, 3, 5], [1, 1, 1]) == 1
 
    assert crt([2, 3, 5], [-1, -1, -1], True) == -1
    assert crt([2, 3, 5], [-1, -1, -1], False) == 2*3*5 - 1