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:
Consider the perturbation method:
definition for all n
(see (1) for derivation)
Consider the polynomial approximation:
)
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/0505036The basic idea is to use fast exponentiation instead of step by step iteration:
 = f(f(f( \ldots f(x) \ldots ))))
definitition of iteration
))
a property of iteration
What about calculating optimized versions of
and
and then combining them? Recursively of course:
 = x + c)
 = g(g(x)) = x + (c + c))
 = 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#^Going back to the equation (2) with
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
that does two iterations in one go, and
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
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
^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})
February 09, 2010, 03:23:59 AM
Giant structure
Mandelbulb3D Gallery
Dilber MC Theme by HarzeM