# Source code for tryalgo.freivalds

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""\
Test matrix product AB = C by Freivalds
jill-jênn vie et christoph dürr - 2015-2020
"""

# snip{
from random import randint
from sys import stdin

# snip}
__all__ = ["freivalds"]
# snip{

"""
function to read an integer from stdin
"""

"""
"""

# pylint: disable=redefined-outer-name
"""
"""
M = []
for _ in range(n):
assert len(row) == n
M.append(row)
return M

# pylint: disable=redefined-outer-name
def mult(M, v):
"""
function to multiply a matrix times a vector
"""
n = len(M)
return [sum(M[i][j] * v[j] for j in range(n)) for i in range(n)]

# pylint: disable=redefined-outer-name
[docs]def freivalds(A, B, C):
"""Tests matrix product AB=C by Freivalds

:param A: n by n numerical matrix
:param B: same
:param C: same
:returns: False with high probability if AB != C

:complexity:
:math:O(n^2)
"""
n = len(A)
x = [randint(0, 1000000) for j in range(n)]
return mult(A, mult(B, x)) == mult(C, x)

# pylint: disable=redefined-outer-name
if __name__ == "__main__":