Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings
This repository was archived by the owner on Feb 1, 2023. It is now read-only.

Commitc7be323

Browse files
author
Release Manager
committed
Trac #34791: move ProductTree and prod_with_derivative() to sage.rings.generic
The class `ProductTree` and the function `prod_with_derivative()` wereintroduced in #34303. Both are fully generic in principle, but theyremained in `hom_velusqrt.py` in the heat of the moment.We should move them to a more suitable place; it seems`sage.rings.generic` is an appropriate choice. Slight tweaks to`ProductTree` while we're at it.URL:https://trac.sagemath.org/34791Reported by: lorenzTicket author(s): Lorenz PannyReviewer(s): Kwankyu Lee
2 parents814d948 +c3dcb9b commitc7be323

File tree

3 files changed

+269
-193
lines changed

3 files changed

+269
-193
lines changed

‎src/doc/en/reference/rings/index.rst‎

Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -65,6 +65,14 @@ Ring Extensions
6565
sage/rings/ring_extension_morphism
6666

6767

68+
Generic Data Structures and Algorithms for Rings
69+
------------------------------------------------
70+
71+
..toctree::
72+
:maxdepth:1
73+
74+
sage/rings/generic
75+
6876
Utilities
6977
---------
7078

‎src/sage/rings/generic.py‎

Lines changed: 260 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,260 @@
1+
r"""
2+
Generic data structures and algorithms for rings
3+
4+
AUTHORS:
5+
6+
- Lorenz Panny (2022): :class:`ProductTree`, :func:`prod_with_derivative`
7+
"""
8+
9+
fromsage.misc.misc_cimportprod
10+
11+
12+
classProductTree:
13+
r"""
14+
A simple binary product tree, i.e., a tree of ring elements in
15+
which every node equals the product of its children.
16+
(In particular, the *root* equals the product of all *leaves*.)
17+
18+
Product trees are a very useful building block for fast computer
19+
algebra. For example, a quasilinear-time Discrete Fourier Transform
20+
(the famous *Fast* Fourier Transform) can be implemented as follows
21+
using the :meth:`remainders` method of this class::
22+
23+
sage: from sage.rings.generic import ProductTree
24+
sage: F = GF(65537)
25+
sage: a = F(1111)
26+
sage: assert a.multiplicative_order() == 1024
27+
sage: R.<x> = F[]
28+
sage: ms = [x - a^i for i in range(1024)] # roots of unity
29+
sage: ys = [F.random_element() for _ in range(1024)] # input vector
30+
sage: zs = ProductTree(ms).remainders(R(ys)) # compute FFT!
31+
sage: zs == [R(ys) % m for m in ms]
32+
True
33+
34+
This class encodes the tree as *layers*: Layer `0` is just a tuple
35+
of the leaves. Layer `i+1` is obtained from layer `i` by replacing
36+
each pair of two adjacent elements by their product, starting from
37+
the left. (If the length is odd, the unpaired element at the end is
38+
simply copied as is.) This iteration stops as soon as it yields a
39+
layer containing only a single element (the root).
40+
41+
.. NOTE::
42+
43+
Use this class if you need the :meth:`remainders` method.
44+
To compute just the product, :func:`prod` is likely faster.
45+
46+
INPUT:
47+
48+
- ``leaves`` -- an iterable of elements in a common ring
49+
50+
EXAMPLES::
51+
52+
sage: from sage.rings.generic import ProductTree
53+
sage: R.<x> = GF(101)[]
54+
sage: vs = [x - i for i in range(1,10)]
55+
sage: tree = ProductTree(vs)
56+
sage: tree.root()
57+
x^9 + 56*x^8 + 62*x^7 + 44*x^6 + 47*x^5 + 42*x^4 + 15*x^3 + 11*x^2 + 12*x + 13
58+
sage: tree.remainders(x^7 + x + 1)
59+
[3, 30, 70, 27, 58, 72, 98, 98, 23]
60+
sage: tree.remainders(x^100)
61+
[1, 1, 1, 1, 1, 1, 1, 1, 1]
62+
63+
::
64+
65+
sage: vs = prime_range(100)
66+
sage: tree = ProductTree(vs)
67+
sage: tree.root().factor()
68+
2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 * 23 * 29 * 31 * 37 * 41 * 43 * 47 * 53 * 59 * 61 * 67 * 71 * 73 * 79 * 83 * 89 * 97
69+
sage: tree.remainders(3599)
70+
[1, 2, 4, 1, 2, 11, 12, 8, 11, 3, 3, 10, 32, 30, 27, 48, 0, 0, 48, 49, 22, 44, 30, 39, 10]
71+
72+
We can access the individual layers of the tree::
73+
74+
sage: tree.layers
75+
[(2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97),
76+
(6, 35, 143, 323, 667, 1147, 1763, 2491, 3599, 4757, 5767, 7387, 97),
77+
(210, 46189, 765049, 4391633, 17120443, 42600829, 97),
78+
(9699690, 3359814435017, 729345064647247, 97),
79+
(32589158477190044730, 70746471270782959),
80+
(2305567963945518424753102147331756070,)]
81+
"""
82+
def__init__(self,leaves):
83+
r"""
84+
Initialize a product tree having the given ring elements
85+
as its leaves.
86+
87+
EXAMPLES::
88+
89+
sage: from sage.rings.generic import ProductTree
90+
sage: vs = prime_range(100)
91+
sage: tree = ProductTree(vs)
92+
"""
93+
V=tuple(leaves)
94+
self.layers= [V]
95+
whilelen(V)>1:
96+
V=tuple(prod(V[i:i+2])foriinrange(0,len(V),2))
97+
self.layers.append(V)
98+
99+
def__len__(self):
100+
r"""
101+
Return the number of leaves of this product tree.
102+
103+
EXAMPLES::
104+
105+
sage: from sage.rings.generic import ProductTree
106+
sage: R.<x> = GF(101)[]
107+
sage: vs = [x - i for i in range(1,10)]
108+
sage: tree = ProductTree(vs)
109+
sage: len(tree)
110+
9
111+
sage: len(tree) == len(vs)
112+
True
113+
sage: len(tree.remainders(x^2))
114+
9
115+
"""
116+
returnlen(self.layers[0])
117+
118+
def__iter__(self):
119+
r"""
120+
Return an iterator over the leaves of this product tree.
121+
122+
EXAMPLES::
123+
124+
sage: from sage.rings.generic import ProductTree
125+
sage: R.<x> = GF(101)[]
126+
sage: vs = [x - i for i in range(1,10)]
127+
sage: tree = ProductTree(vs)
128+
sage: next(iter(tree)) == vs[0]
129+
True
130+
sage: list(tree) == vs
131+
True
132+
"""
133+
returniter(self.layers[0])
134+
135+
defroot(self):
136+
r"""
137+
Return the value at the root of this product tree (i.e., the product of all leaves).
138+
139+
EXAMPLES::
140+
141+
sage: from sage.rings.generic import ProductTree
142+
sage: R.<x> = GF(101)[]
143+
sage: vs = [x - i for i in range(1,10)]
144+
sage: tree = ProductTree(vs)
145+
sage: tree.root()
146+
x^9 + 56*x^8 + 62*x^7 + 44*x^6 + 47*x^5 + 42*x^4 + 15*x^3 + 11*x^2 + 12*x + 13
147+
sage: tree.root() == prod(vs)
148+
True
149+
"""
150+
assertlen(self.layers[-1])==1
151+
returnself.layers[-1][0]
152+
153+
defleaves(self):
154+
r"""
155+
Return a tuple containing the leaves of this product tree.
156+
157+
EXAMPLES::
158+
159+
sage: from sage.rings.generic import ProductTree
160+
sage: R.<x> = GF(101)[]
161+
sage: vs = [x - i for i in range(1,10)]
162+
sage: tree = ProductTree(vs)
163+
sage: tree.leaves()
164+
(x + 100, x + 99, x + 98, ..., x + 93, x + 92)
165+
sage: tree.leaves() == tuple(vs)
166+
True
167+
"""
168+
returnself.layers[0]
169+
170+
defremainders(self,x):
171+
r"""
172+
Given a value `x`, return a list of all remainders of `x`
173+
modulo the leaves of this product tree.
174+
175+
The base ring must support the ``%`` operator for this
176+
method to work.
177+
178+
179+
INPUT:
180+
181+
- ``x`` -- an element of the base ring of this product tree
182+
183+
EXAMPLES::
184+
185+
sage: from sage.rings.generic import ProductTree
186+
sage: vs = prime_range(100)
187+
sage: tree = ProductTree(vs)
188+
sage: n = 1085749272377676749812331719267
189+
sage: tree.remainders(n)
190+
[1, 1, 2, 1, 9, 1, 7, 15, 8, 20, 15, 6, 27, 11, 2, 6, 0, 25, 49, 5, 51, 4, 19, 74, 13]
191+
sage: [n % v for v in vs]
192+
[1, 1, 2, 1, 9, 1, 7, 15, 8, 20, 15, 6, 27, 11, 2, 6, 0, 25, 49, 5, 51, 4, 19, 74, 13]
193+
"""
194+
X= [x]
195+
forVinreversed(self.layers):
196+
X= [X[i//2]%V[i]foriinrange(len(V))]
197+
returnX
198+
199+
200+
defprod_with_derivative(pairs):
201+
r"""
202+
Given an iterable of pairs `(f, \partial f)` of ring elements,
203+
return the pair `(\prod f, \partial \prod f)`, assuming `\partial`
204+
is an operator obeying the standard product rule.
205+
206+
This function is entirely algebraic, hence still works when the
207+
elements `f` and `\partial f` are all passed through some ring
208+
homomorphism first. One particularly useful instance of this is
209+
evaluating the derivative of a product of polynomials at a point
210+
without fully expanding the product; see the second example below.
211+
212+
INPUT:
213+
214+
- ``pairs`` -- an iterable of tuples `(f, \partial f)` of elements
215+
of a common ring
216+
217+
ALGORITHM: Repeated application of the product rule.
218+
219+
EXAMPLES::
220+
221+
sage: from sage.rings.generic import prod_with_derivative
222+
sage: R.<x> = ZZ[]
223+
sage: fs = [x^2 + 2*x + 3, 4*x + 5, 6*x^7 + 8*x + 9]
224+
sage: prod(fs)
225+
24*x^10 + 78*x^9 + 132*x^8 + 90*x^7 + 32*x^4 + 140*x^3 + 293*x^2 + 318*x + 135
226+
sage: prod(fs).derivative()
227+
240*x^9 + 702*x^8 + 1056*x^7 + 630*x^6 + 128*x^3 + 420*x^2 + 586*x + 318
228+
sage: F, dF = prod_with_derivative((f, f.derivative()) for f in fs)
229+
sage: F
230+
24*x^10 + 78*x^9 + 132*x^8 + 90*x^7 + 32*x^4 + 140*x^3 + 293*x^2 + 318*x + 135
231+
sage: dF
232+
240*x^9 + 702*x^8 + 1056*x^7 + 630*x^6 + 128*x^3 + 420*x^2 + 586*x + 318
233+
234+
The main reason for this function to exist is that it allows us to
235+
*evaluate* the derivative of a product of polynomials at a point
236+
`\alpha` without ever fully expanding the product *as a polynomial*::
237+
238+
sage: alpha = 42
239+
sage: F(alpha)
240+
442943981574522759
241+
sage: dF(alpha)
242+
104645261461514994
243+
sage: us = [f(alpha) for f in fs]
244+
sage: vs = [f.derivative()(alpha) for f in fs]
245+
sage: prod_with_derivative(zip(us, vs))
246+
(442943981574522759, 104645261461514994)
247+
"""
248+
class_aux:
249+
def__init__(self,f,df):
250+
self.f,self.df=f,df
251+
252+
def__mul__(self,other):
253+
return_aux(self.f*other.f,self.df*other.f+self.f*other.df)
254+
255+
def__iter__(self):
256+
yieldself.f
257+
yieldself.df
258+
259+
returntuple(prod(_aux(*tup)fortupinpairs))
260+

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp