## Probability and Computing - Mitzenmacher, Upfal


```python
import numpy as np
from sympy import poly
from sympy.abc import x
```

Define two polynomials:
- $F$ is a product of monomials
- $G$ is in canonical form


```python
F = poly((x + 1) * (x - 2) * (x + 3) * (x - 4) * (x + 5) * (x - 6))
G = poly(x**6 - 7 * x**3 + 25)
```

Want to check if $F \equiv G$ without converting $F$ to canonical form.


```python
def polycheck(F: 'poly', G: 'poly', δ: int, k: int, replacement: bool) -> bool:
    """Randomized algorithm for verifying whether F and G are equivalent.
    
    If F ≡ G, then the algo always computes the correct answer.
    If F ≢ G, then the algo can compute the wrong answer by
        finding r s.t. r is the root of F(x) - G(x) = 0,
        which, by FTA, can happen at most in d / (δ * d) cases,
        meaning that the prob. of error (in one iter) is <= 1/δ.
        
    If sampling is performed WITH replacement, then iterations are independent,
        therefore, the probability of error becomes <= (1/δ)**k
        i.e. exponentially small in the number of trials.
    If sampling is performed WITHOUT replacement, we get a tighter bound <= (1/δ)**k,
        since the error now consists of the event "finding k distinct roots",
        which is much stronger.
    
    Args:
        F, G: sympy polynomials.
        δ: upper bound for the sample space.
        k: number of iterations (trials).
        replacement: whether to perform sampling with or without replacement.
    
    Returns:
        True if F,G are found to be equivalent, otherwise False.
    """
    d = max(F.degree(), G.degree())
    space = np.arange(1, δ * d + 1)  # {1, ..., δ * d}

    # choose values uniformly at random from the sample space
    rs = np.random.choice(space, replace=replacement, size=k)

    for r in rs:
        if F(r) != G(r):
            return False
    
    return True
```


```python
polycheck(F, G, δ=100, k=10, replacement=False)
```

ae1796b3c9f7eea1f75acb0dcf57a865320eeca0
ipynb
Jupyter Notebook
src/polycheck.ipynb
alexandru-dinu/notebooks
7e963f482158db8f86efa3a706ad2b85f82241e2
MIT
src/polycheck.ipynb
alexandru-dinu/notebooks
7e963f482158db8f86efa3a706ad2b85f82241e2
MIT
2021-01-11T19:24:10.000Z
2021-01-11T19:24:10.000Z
src/polycheck.ipynb
alexandru-dinu/notebooks
7e963f482158db8f86efa3a706ad2b85f82241e2
MIT
Qwen/Qwen-72B
1. YES
2. YES