ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Fri, 18 Mar 2011 10:51:30 +0100symbolic calculus on doubling points in elliptic curveshttps://ask.sagemath.org/question/8007/symbolic-calculus-on-doubling-points-in-elliptic-curves/Suppose I have a polynomial $f(x)$ and i need to compute $f(f(x))$
how do i do this ??
i also need to compute $f(f(f(x)))$ and so on, is there an easy way of doing this ?
Example: If $f(x)=x^2+nx$ then $f(f(x))=...=x^4 + 2n x^3+(n^2+n) x^2+ n x$ and the computations become difficult when trying to compute say $f(f(f(f(f(x)))))$
Thu, 17 Mar 2011 22:06:08 +0100https://ask.sagemath.org/question/8007/symbolic-calculus-on-doubling-points-in-elliptic-curves/Answer by Felix Lawrence for <p>Suppose I have a polynomial $f(x)$ and i need to compute $f(f(x))$</p>
<p>how do i do this ??</p>
<p>i also need to compute $f(f(f(x)))$ and so on, is there an easy way of doing this ?</p>
<p>Example: If $f(x)=x^2+nx$ then $f(f(x))=...=x^4 + 2n x^3+(n^2+n) x^2+ n x$ and the computations become difficult when trying to compute say $f(f(f(f(f(x)))))$</p>
https://ask.sagemath.org/question/8007/symbolic-calculus-on-doubling-points-in-elliptic-curves/?answer=12198#post-id-12198In the next version of sage (4.7) you will be able to use the functions `self_compose` and `nest` to do this. Use `nest` when you want to find $f(f(...f(x)...))$ for known $x$, and use `self_compose` when you want a function that has not been evaluated.
In the meantime you'll need to define them yourself:
def nest(f, n, x):
"""Return `f(f(...f(x)...))`, where the composition occurs n times."""
for i in xrange(n):
x = f(x)
return x
def self_compose(f, n):
"""Return the function `f` composed with itself `n` times."""
return lambda x: nest(f, n, x)
For usage examples and more documentation, see [the patch](http://trac.sagemath.org/sage_trac/attachment/ticket/7742/trac_7742-add-compose-etc_v2.1.patch) that adds this functionality. There is one example which is very similar to yours:
sage: def f(x): return x^2 + 1
sage: x = var('x')
sage: nest(f, 3, x)
((x^2 + 1)^2 + 1)^2 + 1
Thu, 17 Mar 2011 22:31:13 +0100https://ask.sagemath.org/question/8007/symbolic-calculus-on-doubling-points-in-elliptic-curves/?answer=12198#post-id-12198Comment by Felix Lawrence for <p>In the next version of sage (4.7) you will be able to use the functions <code>self_compose</code> and <code>nest</code> to do this. Use <code>nest</code> when you want to find $f(f(...f(x)...))$ for known $x$, and use <code>self_compose</code> when you want a function that has not been evaluated.</p>
<p>In the meantime you'll need to define them yourself:</p>
<pre><code>def nest(f, n, x):
"""Return `f(f(...f(x)...))`, where the composition occurs n times."""
for i in xrange(n):
x = f(x)
return x
def self_compose(f, n):
"""Return the function `f` composed with itself `n` times."""
return lambda x: nest(f, n, x)
</code></pre>
<p>For usage examples and more documentation, see <a href="http://trac.sagemath.org/sage_trac/attachment/ticket/7742/trac_7742-add-compose-etc_v2.1.patch">the patch</a> that adds this functionality. There is one example which is very similar to yours:</p>
<pre><code> sage: def f(x): return x^2 + 1
sage: x = var('x')
sage: nest(f, 3, x)
((x^2 + 1)^2 + 1)^2 + 1
</code></pre>
https://ask.sagemath.org/question/8007/symbolic-calculus-on-doubling-points-in-elliptic-curves/?comment=21970#post-id-21970probably because it was merged 9 hours ago ;-)Fri, 18 Mar 2011 00:05:54 +0100https://ask.sagemath.org/question/8007/symbolic-calculus-on-doubling-points-in-elliptic-curves/?comment=21970#post-id-21970Comment by kcrisman for <p>In the next version of sage (4.7) you will be able to use the functions <code>self_compose</code> and <code>nest</code> to do this. Use <code>nest</code> when you want to find $f(f(...f(x)...))$ for known $x$, and use <code>self_compose</code> when you want a function that has not been evaluated.</p>
<p>In the meantime you'll need to define them yourself:</p>
<pre><code>def nest(f, n, x):
"""Return `f(f(...f(x)...))`, where the composition occurs n times."""
for i in xrange(n):
x = f(x)
return x
def self_compose(f, n):
"""Return the function `f` composed with itself `n` times."""
return lambda x: nest(f, n, x)
</code></pre>
<p>For usage examples and more documentation, see <a href="http://trac.sagemath.org/sage_trac/attachment/ticket/7742/trac_7742-add-compose-etc_v2.1.patch">the patch</a> that adds this functionality. There is one example which is very similar to yours:</p>
<pre><code> sage: def f(x): return x^2 + 1
sage: x = var('x')
sage: nest(f, 3, x)
((x^2 + 1)^2 + 1)^2 + 1
</code></pre>
https://ask.sagemath.org/question/8007/symbolic-calculus-on-doubling-points-in-elliptic-curves/?comment=21971#post-id-21971Cool to know about! How come I didn't know that?Thu, 17 Mar 2011 23:31:04 +0100https://ask.sagemath.org/question/8007/symbolic-calculus-on-doubling-points-in-elliptic-curves/?comment=21971#post-id-21971Answer by manenir for <p>Suppose I have a polynomial $f(x)$ and i need to compute $f(f(x))$</p>
<p>how do i do this ??</p>
<p>i also need to compute $f(f(f(x)))$ and so on, is there an easy way of doing this ?</p>
<p>Example: If $f(x)=x^2+nx$ then $f(f(x))=...=x^4 + 2n x^3+(n^2+n) x^2+ n x$ and the computations become difficult when trying to compute say $f(f(f(f(f(x)))))$</p>
https://ask.sagemath.org/question/8007/symbolic-calculus-on-doubling-points-in-elliptic-curves/?answer=12200#post-id-12200Dear John, your help is greatly appreciated :) One further question : What i want to do is exactly what you have descibed at the end, but with an expression of the form $\frac{f(a)}{g(a)}$ where $f,g$ are polynomials in $a$ (and with coefficients in $Z[m])$ instead of just a polynomial $f(a)$. So when I define say
$$f=\frac{(a^2-m^2)^2}{a^3-m}$$ what Sage notebook gives is
1/256*a^13/(a^2 - 4*m)^2 - 1/8*a^11*m/(a^2 - 4*m)^2 + 7/4*a^9*m^2/(a^2 -
4*m)^2 - 14*a^7*m^3/(a^2 - 4*m)^2 + 70*a^5*m^4/(a^2 - 4*m)^2 -
1/2*a^7*m/(a^2 - 4*m)^2 - 224*a^3*m^5/(a^2 - 4*m)^2 + 8*a^5*m^2/(a^2 -
4*m)^2 + 448*a*m^6/(a^2 - 4*m)^2 - 48*a^3*m^3/(a^2 - 4*m)^2 -
512*m^7/((a^2 - 4*m)^2*a) + 128*a*m^4/(a^2 - 4*m)^2 + 256*m^8/((a^2 -
4*m)^2*a^3) - 128*m^5/((a^2 - 4*m)^2*a) + 16*a*m^2/(a^2 - 4*m)^2
That seems rather incomprehensible as it computes the final expression in disctinct fractions. Is there any way to format this in a nice latexed expression of the form ''polynomial over (other)polynomial'' where both polynomials will be factored ?
thanx !Fri, 18 Mar 2011 01:40:51 +0100https://ask.sagemath.org/question/8007/symbolic-calculus-on-doubling-points-in-elliptic-curves/?answer=12200#post-id-12200Comment by John Palmieri for <p>Dear John, your help is greatly appreciated :) One further question : What i want to do is exactly what you have descibed at the end, but with an expression of the form $\frac{f(a)}{g(a)}$ where $f,g$ are polynomials in $a$ (and with coefficients in $Z[m])$ instead of just a polynomial $f(a)$. So when I define say
$$f=\frac{(a^2-m^2)^2}{a^3-m}$$ what Sage notebook gives is </p>
<p>1/256<em>a^13/(a^2 - 4</em>m)^2 - 1/8<em>a^11</em>m/(a^2 - 4<em>m)^2 + 7/4</em>a^9<em>m^2/(a^2 -
4</em>m)^2 - 14<em>a^7</em>m^3/(a^2 - 4<em>m)^2 + 70</em>a^5<em>m^4/(a^2 - 4</em>m)^2 -
1/2<em>a^7</em>m/(a^2 - 4<em>m)^2 - 224</em>a^3<em>m^5/(a^2 - 4</em>m)^2 + 8<em>a^5</em>m^2/(a^2 -
4<em>m)^2 + 448</em>a<em>m^6/(a^2 - 4</em>m)^2 - 48<em>a^3</em>m^3/(a^2 - 4<em>m)^2 -
512</em>m^7/((a^2 - 4<em>m)^2</em>a) + 128<em>a</em>m^4/(a^2 - 4<em>m)^2 + 256</em>m^8/((a^2 -
4<em>m)^2</em>a^3) - 128<em>m^5/((a^2 - 4</em>m)^2<em>a) + 16</em>a<em>m^2/(a^2 - 4</em>m)^2</p>
<p>That seems rather incomprehensible as it computes the final expression in disctinct fractions. Is there any way to format this in a nice latexed expression of the form ''polynomial over (other)polynomial'' where both polynomials will be factored ?</p>
<p>thanx !</p>
https://ask.sagemath.org/question/8007/symbolic-calculus-on-doubling-points-in-elliptic-curves/?comment=21966#post-id-21966If you set g=f(f(a)), then you could use g.rational_expand() or g.rational_simplify(), or g.numerator().factor() and g.denominator().factor(). Basically, do g=f(f(a)), type "g." and hit the TAB key to see what all of the many options, and hope that something looks right.Fri, 18 Mar 2011 10:51:30 +0100https://ask.sagemath.org/question/8007/symbolic-calculus-on-doubling-points-in-elliptic-curves/?comment=21966#post-id-21966Comment by kcrisman for <p>Dear John, your help is greatly appreciated :) One further question : What i want to do is exactly what you have descibed at the end, but with an expression of the form $\frac{f(a)}{g(a)}$ where $f,g$ are polynomials in $a$ (and with coefficients in $Z[m])$ instead of just a polynomial $f(a)$. So when I define say
$$f=\frac{(a^2-m^2)^2}{a^3-m}$$ what Sage notebook gives is </p>
<p>1/256<em>a^13/(a^2 - 4</em>m)^2 - 1/8<em>a^11</em>m/(a^2 - 4<em>m)^2 + 7/4</em>a^9<em>m^2/(a^2 -
4</em>m)^2 - 14<em>a^7</em>m^3/(a^2 - 4<em>m)^2 + 70</em>a^5<em>m^4/(a^2 - 4</em>m)^2 -
1/2<em>a^7</em>m/(a^2 - 4<em>m)^2 - 224</em>a^3<em>m^5/(a^2 - 4</em>m)^2 + 8<em>a^5</em>m^2/(a^2 -
4<em>m)^2 + 448</em>a<em>m^6/(a^2 - 4</em>m)^2 - 48<em>a^3</em>m^3/(a^2 - 4<em>m)^2 -
512</em>m^7/((a^2 - 4<em>m)^2</em>a) + 128<em>a</em>m^4/(a^2 - 4<em>m)^2 + 256</em>m^8/((a^2 -
4<em>m)^2</em>a^3) - 128<em>m^5/((a^2 - 4</em>m)^2<em>a) + 16</em>a<em>m^2/(a^2 - 4</em>m)^2</p>
<p>That seems rather incomprehensible as it computes the final expression in disctinct fractions. Is there any way to format this in a nice latexed expression of the form ''polynomial over (other)polynomial'' where both polynomials will be factored ?</p>
<p>thanx !</p>
https://ask.sagemath.org/question/8007/symbolic-calculus-on-doubling-points-in-elliptic-curves/?comment=21967#post-id-21967You are right, this is a separate question. You may want to try f.expand() or f.[some other method that sounds plausible].Fri, 18 Mar 2011 08:13:03 +0100https://ask.sagemath.org/question/8007/symbolic-calculus-on-doubling-points-in-elliptic-curves/?comment=21967#post-id-21967Answer by John Palmieri for <p>Suppose I have a polynomial $f(x)$ and i need to compute $f(f(x))$</p>
<p>how do i do this ??</p>
<p>i also need to compute $f(f(f(x)))$ and so on, is there an easy way of doing this ?</p>
<p>Example: If $f(x)=x^2+nx$ then $f(f(x))=...=x^4 + 2n x^3+(n^2+n) x^2+ n x$ and the computations become difficult when trying to compute say $f(f(f(f(f(x)))))$</p>
https://ask.sagemath.org/question/8007/symbolic-calculus-on-doubling-points-in-elliptic-curves/?answer=12199#post-id-12199How are you defining `f`? This works for me:
sage: R = GF(2)['y']
sage: R.inject_variables()
Defining y
sage: f = y^2 + y + 1
sage: f(f(y))
y^4 + y + 1
Edit: if you want to do something like `f(y) = y^2 + ny`, then you need two variables, and you could make one a polynomial variable, one a symbolic variable. Make sure that the symbolic one comes after the polynomial one, alphabetically:
sage: var('m')
sage: R = QQ['a']
sage: R.inject_variables()
sage: f = a^2 + m*a
sage: f(f(a))
(a^2 + a*m)^2 + (a^2 + a*m)*m
sage: f(f(a)).expand()
a^4 + 2*a^3*m + a^2*m^2 + a^2*m + a*m^2
Then
sage: f(f(f(f(f(a))))).expand()
works, but gives a very long expression.
(You need the polynomial generator to come alphabetically before the symbolic variable because `f` depends on two variables, and when you call `f(3)`, for example, it chooses to substitute the 3 for the first of the variables. You want to substitute `f(a)` for `a` by default, so make sure `a` comes before `m`.)
Thu, 17 Mar 2011 23:01:32 +0100https://ask.sagemath.org/question/8007/symbolic-calculus-on-doubling-points-in-elliptic-curves/?answer=12199#post-id-12199Comment by manenir for <p>How are you defining <code>f</code>? This works for me:</p>
<pre><code>sage: R = GF(2)['y']
sage: R.inject_variables()
Defining y
sage: f = y^2 + y + 1
sage: f(f(y))
y^4 + y + 1
</code></pre>
<p>Edit: if you want to do something like <code>f(y) = y^2 + ny</code>, then you need two variables, and you could make one a polynomial variable, one a symbolic variable. Make sure that the symbolic one comes after the polynomial one, alphabetically:</p>
<pre><code>sage: var('m')
sage: R = QQ['a']
sage: R.inject_variables()
sage: f = a^2 + m*a
sage: f(f(a))
(a^2 + a*m)^2 + (a^2 + a*m)*m
sage: f(f(a)).expand()
a^4 + 2*a^3*m + a^2*m^2 + a^2*m + a*m^2
</code></pre>
<p>Then</p>
<pre><code>sage: f(f(f(f(f(a))))).expand()
</code></pre>
<p>works, but gives a very long expression.</p>
<p>(You need the polynomial generator to come alphabetically before the symbolic variable because <code>f</code> depends on two variables, and when you call <code>f(3)</code>, for example, it chooses to substitute the 3 for the first of the variables. You want to substitute <code>f(a)</code> for <code>a</code> by default, so make sure <code>a</code> comes before <code>m</code>.)</p>
https://ask.sagemath.org/question/8007/symbolic-calculus-on-doubling-points-in-elliptic-curves/?comment=21969#post-id-21969Fri, 18 Mar 2011 01:23:08 +0100https://ask.sagemath.org/question/8007/symbolic-calculus-on-doubling-points-in-elliptic-curves/?comment=21969#post-id-21969