pyrival.linear_algebra

pyrival.linear_algebra.matrix

pyrival.linear_algebra.matrix.eye(m)

returns an indentity matrix of order m

pyrival.linear_algebra.matrix.mat_add(*mat)

pyrival.linear_algebra.matrix.mat_inv(A)

pyrival.linear_algebra.matrix.mat_mul(A, B)

pyrival.linear_algebra.matrix.mat_pow(mat, power)

returns mat**power

pyrival.linear_algebra.matrix.mat_sub(A, B)

pyrival.linear_algebra.matrix.minor(mat, i, j)

pyrival.linear_algebra.matrix.transpose(mat)

pyrival.linear_algebra.matrix.vec_mul(mat, vec)

pyrival.linear_algebra.max_xor

Maximizes xor of values in a list (works with big integers)

Example: >>>> A = [10**20, 3, 6, 4] >>>> I = max_xor(A) >>>> xor = 0 >>>> for i in I: …. xor ^= A[i] …. >>>> xor 100000000000000000007

pyrival.linear_algebra.max_xor.max_xor(A)

Input: List A of non-negative integers Output: I such that xor(A[i] for i in I) is maximized

pyrival.linear_algebra.multivariable_crt

pyrival.linear_algebra.multivariable_crt.extended_gcd(a, b)

returns gcd(a, b), s, r s.t. a * s + b * r == gcd(a, b)

pyrival.linear_algebra.multivariable_crt.gcd(x, y)

greatest common divisor of x and y

pyrival.linear_algebra.multivariable_crt.is_sol(A, x, b, m)

checks if Ax = b mod m

pyrival.linear_algebra.multivariable_crt.mat_mul(A, B)

pyrival.linear_algebra.multivariable_crt.mat_sub(A, B)

pyrival.linear_algebra.multivariable_crt.mcrt(A, b, m)

returns x s.t. Ax = b mod m

pyrival.linear_algebra.multivariable_crt.modinv(a, m)

returns the modular inverse of a w.r.t. to m

pyrival.linear_algebra.multivariable_crt.pivot(A, m)

returns the pivot of A and m