Print Page - giant leaps? fast exponentiation for iteration

EDIT: there's a fatal flaw that I didn't spot earlier: iterating F gives F^n which can be accelerated; but the (n+1)th coefficients for the power series in d_0 depend on the (n)th Z value, so in fact there are a whole family of functions not just one, and F_n(F_{n-1}(...(F_2(F_1(d_0)))...)) is definitely not the same as F_1^N(d_0), and so the acceleration of F^n is irrelevant... oops!

Consider the iteration:

$Z_0 = C$
$Z_{n+1} = Z_{n}^2 + C$

Consider the perturbation method:

$\delta_n = z_{n} - Z_{n}$ definition for all n
$\delta_{n+1} = 2 Z_n \delta_n + \delta_n^2 + \delta_0$ (see (1) for derivation)

Consider the polynomial approximation:

$\delta_n = a_{1,n} \delta_0 + a_{2,n} \delta_0^2 + a_{3,n} \delta_0^3 + ...$
$a_{1,0} = 1$
$a_{k,0} = 0, k \gt 1$
$a_{k,n+1} = F_{k,1}(\{a_{m,n} : 1 \le m \le k \})$ where F_{k,1} can be determined algebraically (2)

So far, so SFT. Now I got inspired by this paper: "Parabolic Julia Sets are Polynomial Time Computable" Mark Braverman http://arxiv.org/abs/math.DS/0505036

The basic idea is to use fast exponentiation instead of step by step iteration:

$f^n(x) = f(f(f( \ldots f(x) \ldots )))$ definitition of iteration
$f^{n+m} = f^n(f^m(x))$ a property of iteration

What about calculating optimized versions of $f^n$ and $f^m$ and then combining them? Recursively of course:

$g(x) = x + c$
$g^2(x) = g(g(x)) = x + (c + c)$
$g^4(x) = g^2(g^2(x)) = x + ((c + c) + (c + c))$

Non-powers-of-two could be handled like this: http://hackage.haskell.org/packages/archive/base/latest/doc/html/src/GHC-Real.html#^ (http://hackage.haskell.org/packages/archive/base/latest/doc/html/src/GHC-Real.html#^)

Going back to the equation (2) with $F_{k,1}$ determining the next values of the approximating polynomial coefficients from the previous ones is simple algebraic manipulation: substituting a polynomial into a polynomial gives another polynomial (you need to collect up like terms)

So, what about calculating $F_{k,2}$ that does two iterations in one go, and $F_{k,4}$ that does four iterations in one go, and so on?

If it can be determined that the approximation with 3 terms is good for say 1337 iterations, you'd only need to calculate $F_{k,s}$ for k = 1,2,3 and s = 1,2,4,8,16,32,64,128,256,512,1024. If you don't know in advance how many iterations its good for, you could keep doubling the number of iterations until it goes bad, then binary search.

As far as I can tell, this reduces the workload from O(N) to O(log N), keeping K fixed (I think it's O(K^2) keeping N fixed).

Anyone fancy implementing this (or already implemented it?) and seeing if the constant factors outweigh the potential gain?

(1) derivation of perturbation method
$z_{n+1} = z_{n}^2 + C + \delta_0 = (Z_{n} + \delta_n)^2 + C + \delta_0 = Z_{n}^2 + 2 Z_n \delta_n + \delta_n^2 + C + \delta_0 = Z_{n+1} + 2 Z_n \delta_n + \delta_n^2 + \delta_0 = Z_{n+1} + \delta_{n+1}$

Welcome to Fractal Forums

Fractal Math, Chaos Theory & Research => Mandelbrot & Julia Set => Topic started by: claude on September 26, 2013, 01:09:36 AM