Spaces:
Sleeping
Sleeping
File size: 5,124 Bytes
6a86ad5 |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 |
"""
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)
|