Spaces:
Sleeping
Sleeping
| """ | |
| Recurrences | |
| """ | |
| from sympy.core import S, sympify | |
| from sympy.utilities.iterables import iterable | |
| from sympy.utilities.misc import as_int | |
| def linrec(coeffs, init, n): | |
| r""" | |
| Evaluation of univariate linear recurrences of homogeneous type | |
| having coefficients independent of the recurrence variable. | |
| Parameters | |
| ========== | |
| coeffs : iterable | |
| Coefficients of the recurrence | |
| init : iterable | |
| Initial values of the recurrence | |
| n : Integer | |
| Point of evaluation for the recurrence | |
| Notes | |
| ===== | |
| Let `y(n)` be the recurrence of given type, ``c`` be the sequence | |
| of coefficients, ``b`` be the sequence of initial/base values of the | |
| recurrence and ``k`` (equal to ``len(c)``) be the order of recurrence. | |
| Then, | |
| .. math :: y(n) = \begin{cases} b_n & 0 \le n < k \\ | |
| c_0 y(n-1) + c_1 y(n-2) + \cdots + c_{k-1} y(n-k) & n \ge k | |
| \end{cases} | |
| Let `x_0, x_1, \ldots, x_n` be a sequence and consider the transformation | |
| that maps each polynomial `f(x)` to `T(f(x))` where each power `x^i` is | |
| replaced by the corresponding value `x_i`. The sequence is then a solution | |
| of the recurrence if and only if `T(x^i p(x)) = 0` for each `i \ge 0` where | |
| `p(x) = x^k - c_0 x^(k-1) - \cdots - c_{k-1}` is the characteristic | |
| polynomial. | |
| Then `T(f(x)p(x)) = 0` for each polynomial `f(x)` (as it is a linear | |
| combination of powers `x^i`). Now, if `x^n` is congruent to | |
| `g(x) = a_0 x^0 + a_1 x^1 + \cdots + a_{k-1} x^{k-1}` modulo `p(x)`, then | |
| `T(x^n) = x_n` is equal to | |
| `T(g(x)) = a_0 x_0 + a_1 x_1 + \cdots + a_{k-1} x_{k-1}`. | |
| Computation of `x^n`, | |
| given `x^k = c_0 x^{k-1} + c_1 x^{k-2} + \cdots + c_{k-1}` | |
| is performed using exponentiation by squaring (refer to [1_]) with | |
| an additional reduction step performed to retain only first `k` powers | |
| of `x` in the representation of `x^n`. | |
| Examples | |
| ======== | |
| >>> from sympy.discrete.recurrences import linrec | |
| >>> from sympy.abc import x, y, z | |
| >>> linrec(coeffs=[1, 1], init=[0, 1], n=10) | |
| 55 | |
| >>> linrec(coeffs=[1, 1], init=[x, y], n=10) | |
| 34*x + 55*y | |
| >>> linrec(coeffs=[x, y], init=[0, 1], n=5) | |
| x**2*y + x*(x**3 + 2*x*y) + y**2 | |
| >>> linrec(coeffs=[1, 2, 3, 0, 0, 4], init=[x, y, z], n=16) | |
| 13576*x + 5676*y + 2356*z | |
| References | |
| ========== | |
| .. [1] https://en.wikipedia.org/wiki/Exponentiation_by_squaring | |
| .. [2] https://en.wikipedia.org/w/index.php?title=Modular_exponentiation§ion=6#Matrices | |
| See Also | |
| ======== | |
| sympy.polys.agca.extensions.ExtensionElement.__pow__ | |
| """ | |
| if not coeffs: | |
| return S.Zero | |
| if not iterable(coeffs): | |
| raise TypeError("Expected a sequence of coefficients for" | |
| " the recurrence") | |
| if not iterable(init): | |
| raise TypeError("Expected a sequence of values for the initialization" | |
| " of the recurrence") | |
| n = as_int(n) | |
| if n < 0: | |
| raise ValueError("Point of evaluation of recurrence must be a " | |
| "non-negative integer") | |
| c = [sympify(arg) for arg in coeffs] | |
| b = [sympify(arg) for arg in init] | |
| k = len(c) | |
| if len(b) > k: | |
| raise TypeError("Count of initial values should not exceed the " | |
| "order of the recurrence") | |
| else: | |
| b += [S.Zero]*(k - len(b)) # remaining initial values default to zero | |
| if n < k: | |
| return b[n] | |
| terms = [u*v for u, v in zip(linrec_coeffs(c, n), b)] | |
| return sum(terms[:-1], terms[-1]) | |
| def linrec_coeffs(c, n): | |
| r""" | |
| Compute the coefficients of n'th term in linear recursion | |
| sequence defined by c. | |
| `x^k = c_0 x^{k-1} + c_1 x^{k-2} + \cdots + c_{k-1}`. | |
| It computes the coefficients by using binary exponentiation. | |
| This function is used by `linrec` and `_eval_pow_by_cayley`. | |
| Parameters | |
| ========== | |
| c = coefficients of the divisor polynomial | |
| n = exponent of x, so dividend is x^n | |
| """ | |
| k = len(c) | |
| def _square_and_reduce(u, offset): | |
| # squares `(u_0 + u_1 x + u_2 x^2 + \cdots + u_{k-1} x^k)` (and | |
| # multiplies by `x` if offset is 1) and reduces the above result of | |
| # length upto `2k` to `k` using the characteristic equation of the | |
| # recurrence given by, `x^k = c_0 x^{k-1} + c_1 x^{k-2} + \cdots + c_{k-1}` | |
| w = [S.Zero]*(2*len(u) - 1 + offset) | |
| for i, p in enumerate(u): | |
| for j, q in enumerate(u): | |
| w[offset + i + j] += p*q | |
| for j in range(len(w) - 1, k - 1, -1): | |
| for i in range(k): | |
| w[j - i - 1] += w[j]*c[i] | |
| return w[:k] | |
| def _final_coeffs(n): | |
| # computes the final coefficient list - `cf` corresponding to the | |
| # point at which recurrence is to be evalauted - `n`, such that, | |
| # `y(n) = cf_0 y(k-1) + cf_1 y(k-2) + \cdots + cf_{k-1} y(0)` | |
| if n < k: | |
| return [S.Zero]*n + [S.One] + [S.Zero]*(k - n - 1) | |
| else: | |
| return _square_and_reduce(_final_coeffs(n // 2), n % 2) | |
| return _final_coeffs(n) | |