finding a p-cycle of a real function

[Avril Coghlan]

Dear SAGE users and developers,

Is it possible for me to find a p-cycle of a real function using SAGE?

For example, the sequence x_{n+1} = x_{n}^2 - 1.76, x_{0} =0 (n = 0,1,2...) has a three-cycle, so it alternates indefinitely between three numbers (approximately 1.3, 0.0, and -1.8).

How can I find this three-cycle, or any p-cycle, using SAGE?

I would be very grateful for any advice.

Kind Regards,
Avril

Avril Coghlan
Cork, Ireland

[D. S. McNeil]

Warning: I haven't thought this through, but the ideas might be useful.

It looks like you'd call something a 3-cycle if for some x_0 we had
f(f(f(x_0))) == x_0, right? Then we should be able to do this
numerically, with some caveats:

# can't remember the slick way, so brute force
def iter_apply(f0, n):
fs = [f0()]
for i in xrange(n-1):
last = fs[-1]
fs.append(f0(last))
return fs

def find_pcycles(f0, n):
fs = iter_apply(f0, n)
req = fs[-1] == x # defining equation of the cycle
roots = req.roots(ring=RR)
for root, mult in roots:
yield [fi(x=root) for fi in fs]

which gives

sage: f(x) = x^2-1.76
sage:
sage: p1 = list(find_pcycles(f, 1))
sage: p1
[[-0.917744687875782], [1.91774468787578]]
sage: f(p1[0][0])
-0.917744687875783
sage: f(p1[1][0])
1.91774468787578
sage: list(find_pcycles(f, 2))
[[0.504987562112089, -1.50498756211209], [-0.917744687875783,
-0.917744687875782], [-1.50498756211209, 0.504987562112089],
[1.91774468787578, 1.91774468787578]]
sage: list(find_pcycles(f, 3))
[[1.33560128916886, 0.0238308036295167, -1.75943209279837],
[1.27545967679486, -0.133202612870350, -1.74225706392451],
[-0.917744687875783, -0.917744687875782, -0.917744687875783],
[-1.74225706392451, 1.27545967679486, -0.133202612870348],
[-1.75943209279837, 1.33560128916886, 0.0238308036295143],
[-0.133202612870349, -1.74225706392451, 1.27545967679486],
[0.0238308036295150, -1.75943209279837, 1.33560128916886],
[1.91774468787578, 1.91774468787578, 1.91774468787578]]

Note that this says [-0.917744687875783, -0.917744687875782,
-0.917744687875783] is a 3-cycle, which it kind of is..

Anyway, maybe playing off of something like that would help?

Doug

[John Cremona]

Numerical precision issues would make it preferable (surely?) to use
exact arithmetic by replacing 1.76 by 176/100.

Do you know the standard trick (as used for instance in the Pollard
rho method of factorization) which avoids storing lots of terms of the
sequence and instead runs two variables through the sequence
simultaneously, starting at the same point, but with one sequence
applying the iteration twice? then you just have to check when the
two values coincide.

Details left to the reader, or see
http://en.wikipedia.org/wiki/Floyd%27s_cycle-finding_algorithm#Tortoise_and_hare

John

> --
> To post to this group, send email to sage-s...@googlegroups.com
> To unsubscribe from this group, send email to sage-support...@googlegroups.com
> For more options, visit this group at http://groups.google.com/group/sage-support
> URL: http://www.sagemath.org

[Avril Coghlan]

Thank you very much to both of you for your help with this, that is
great, I appreciate it a lot.

On Feb 11, 9:43 pm, John Cremona <john.crem...@gmail.com> wrote:
> Numerical precision issues would make it preferable (surely?) to use
> exact arithmetic by replacing 1.76 by 176/100.
>
> Do you know the standard trick (as used for instance in the Pollard
> rho method of factorization) which avoids storing lots of terms of the
> sequence and instead runs two variables through the sequence
> simultaneously, starting at the same point, but with one sequence
> applying the iteration twice?  then you just have to check when the
> two values coincide.
>

> Details left to the reader, or seehttp://en.wikipedia.org/wiki/Floyd%27s_cycle-finding_algorithm#Tortoi...