• February 27, 2021, 10:03:03 PM

Login with username, password and session length

Author Topic: (Question) iterating corners to find period  (Read 1314 times)

0 Members and 1 Guest are viewing this topic.

Offline quaz0r

  • Fractal Feline
  • **
  • Posts: 152
(Question) iterating corners to find period
« on: October 09, 2020, 10:28:18 AM »
http://www.mrob.com/pub/muency/period.html

im trying to figure out what the proper way to implement this is.  it sounds like we are checking to see when the points surround the origin.  first i tried just checking if each of four points occupy each quadrant, but that fails immediately.  he makes some weird statement about an odd number of vertices crossing one half of either axis, but i cant picture how 3 of 4 vertices can cross one half of one axis and surround the origin at the same time.  unless the vertices are allowed to criss-cross each other, is that supposed to count?   he goes on to say that you also get a rough estimate for the location of the root by the location of the origin with respect to the points when they surround it, which makes it sound like for example if you start with a square you more or less should have retained that shape.

Linkback: https://fractalforums.org/fractal-mathematics-and-new-theories/28/iterating-corners-to-find-period/3805/

Offline claude

  • 3f
  • ******
  • Posts: 1784
    • mathr.co.uk
Re: iterating corners to find period
« Reply #1 on: October 09, 2020, 11:15:40 AM »
the shape only gets folded by squaring if it surrounded the origin, but we stop then so don't have to worry about that
so the shape (probably, maybe, usually?) remains a loop that doesn't cross itself
if only one edge crosses the positive real axis (or any other ray from the origin to infinity), the other 3 edges must be wrapped around the origin
if three edges cross the positive real axis, and the 4th edge doesn't, again the shape must enclose the origin
the other 3 cases don't surround the origin (maybe try drawing some diagrams)

see also: https://en.wikipedia.org/wiki/Even%E2%80%93odd_rule "On a simple curve, the even–odd rule reduces to a decision algorithm for the point in polygon problem. "


for analytic functions like Mandelbrot iterations, ball arithmetic is usually superior than this method; and ball method can be extended to non-analytic functions using 2x2 Jacobian matrices

Offline marcm200

  • 3c
  • ***
  • Posts: 925
Re: iterating corners to find period
« Reply #2 on: October 09, 2020, 11:33:27 AM »
I tried this with period-2 (around -1+0i) and period-10 (value in image) and used a 4-polygon (lines). At the correct iteration the origin (cyan point) is enclosed. Quite interesting!



Offline quaz0r

  • Fractal Feline
  • **
  • Posts: 152
Re: iterating corners to find period
« Reply #3 on: October 09, 2020, 12:51:03 PM »
thanks for the replies.  is there a post on the forums that explains how to implement the ball method?  i remember implementing knighty's ball method for calculating an error estimate on the series approximation, but im not sure how to apply it to this.

Offline claude

  • 3f
  • ******
  • Posts: 1784
    • mathr.co.uk
Re: iterating corners to find period
« Reply #4 on: October 09, 2020, 02:50:59 PM »
The derivative is basically a scale factor applied to the ball radius (which starts at your desired region of interest), then you just check whether the distance to the origin is less than the radius of the scaled ball.  But I think knighty might have extended it with second derivatives, can't remember if I copy/pasted that into KF or if I just did the linear version....

Offline hobold

  • Fractal Fluff
  • *****
  • Posts: 397
Re: iterating corners to find period
« Reply #5 on: October 09, 2020, 03:23:43 PM »
he makes some weird statement about an odd number of vertices crossing one half of either axis

This is really a "point in polygon" test, namely the ray casting method: https://en.wikipedia.org/wiki/Point_in_polygon, with a half-axis as the ray.

Offline marcm200

  • 3c
  • ***
  • Posts: 925
Re: iterating corners to find period
« Reply #6 on: October 09, 2020, 03:32:41 PM »
A nice implementation of this odd-even algorithm has been done by Glauner et. al. https://github.com/pglauner/point_in_polygon with some special considerations in case one or more vertices lie on the axis-to-follow (U, S-form).

"A Simple and Correct Even-Odd Algorithm for the Point-in-Polygon Problem for Complex Polygons", Galetzka M, Glauner P. 2017.





Offline quaz0r

  • Fractal Feline
  • **
  • Posts: 152
Re: iterating corners to find period
« Reply #7 on: October 09, 2020, 05:35:14 PM »
if we say 3 of 4 vertices can cross one half of an axis and still surround the origin, are we referring to something like my image here?  i dont see what else it could be.  i guess that confused me since we are speaking in terms of vertices, this doesnt look like a box any more.  how about when munafo says you can derive a relative position of the root?  do you just forget about the original orientation of the points and let it be a square?  if so, what's the orientation?  like in my image, would you just let those points make a box, and the root is located toward the lower left corner?  or maybe the orientation changed and its near the upper right corner, or something else?

Offline marcm200

  • 3c
  • ***
  • Posts: 925
Re: iterating corners to find period
« Reply #8 on: October 09, 2020, 06:40:10 PM »
Is your image an iteration as described in the link? Or is it a drawn image by yourself? As claude pointed out, when the initial shape is not crossing edges, then it should'nt during iteration (squaring) unless it once enclosed the origin (not crossing), then afterwards it can. So if one does directly stop at the first origin-in-polygone event, this problem doesn't occur. I think the odd-number axis-crossings might be a general idea for larger polygones than 4 vertices - maybe the latter doesn't have 3 axis-crossings without edges crossing themselves (one could do a brute force placing of points above and below the axis in all combinations considering order to (dis)prove that).

Offline quaz0r

  • Fractal Feline
  • **
  • Posts: 152
Re: iterating corners to find period
« Reply #9 on: October 09, 2020, 06:50:55 PM »
ok i figured out a shape that doesnt cross itself.  i dont know whether one, having started out as a box, would actually encounter this though.

in general as far as this period finding method goes, can one extend this past the first period?  like say you surround the origin after 200 iterations, so you say 200 is your period.  then you keep iterating and surround the origin after 50 more iterations.  would that be the next closest mini you passed to get to your location, having a period of 50?

Offline gerrit

  • 3f
  • ******
  • Posts: 2333
Re: iterating corners to find period
« Reply #10 on: October 09, 2020, 08:18:11 PM »
1st order ball method:
Code: [Select]
function p  = findPeriodM3(c0,dx,dy,n,doCont,mpow)
% in ball centered on c0 find period (up to n) of nucleus
% use 1nd order Taylor ball
% M-power mpow set
% doCont = 0 normally

r0 = min(abs(dx),abs(dy));
z = c0*0;
r = (r0);
p = [];
maxR = 1e5;
az = abs(z);

for k=1:n
    r = (az+r).^mpow - az.^mpow + r0;
    z = z.^mpow + c0;
    az = abs(z);
    if(r>az)
        p = [p k];
        fprintf('findPeriodBallM3: N-period found: %d\n',k);
        if(~doCont)
            break;
        end
    end
    if(az>maxR | r>maxR)
        fprintf('Ball: escaping\n',k);
        break;
    end
end
2nd order ball method:
Code: [Select]
function [p c1] = findPeriodBall2(c0,dx,dy,n,doCont)
% in ball centered on c0 find period (up to n) of nucleus
% use 2nd order Taylor balls, always smaller than 1st order

r0 = min(abs(dx),abs(dy));
r0 = r0;
z = c0*0;
c1 = c0;
dz = 0*c0;
r = r0;
p = [];
maxR = 1e5;
az = abs(z);
adz = abs(dz);
minz = 1e16;
minIter = -1;

for k=1:n
    r = r.^2+2*(az+r0.*adz)*r + r0.^2.*adz.^2;
    dz = 2*z.*dz + 1;
    z = z.^2 + c0;
    az = abs(z);
    adz = abs(dz);
    if(double(az)<minz)
        minz = double(az);
        minIter = k;
    end
    if((r+r0*adz)>az)
        p = [p k];
        fprintf('Ball: N-period found: %d, atom: %d\n',k,minIter);
        if(~doCont)
            break;
        end
    end
    if(az>maxR | r>maxR)
        fprintf('Ball: escaping\n',k);
        break;
    end
end

Offline hobold

  • Fractal Fluff
  • *****
  • Posts: 397
Re: iterating corners to find period
« Reply #11 on: October 09, 2020, 08:33:27 PM »
ok i figured out a shape that doesnt cross itself.  i dont know whether one, having started out as a box, would actually encounter this though.
I don't think you can ever get a non-convex quadrangle when you start from a square that is wholly contained in one atom domain and do mandelbrot iterations to the corners. Only after the coordinate origin has landed inside the quadrangle can the quadrangle loose its original topology.

That is because the four corners either correlate nicely with one another (because they are all inside the same atom domain), or they do not correlate at all. In the latter case, the prerequisites for the period finding method were not true from the beginning, because the corners were not all within the same atom domain.

But yes, point in polygon tests have their own set of prerequisites. The ray casting method in particular can be made to be very robust, though.

Offline quaz0r

  • Fractal Feline
  • **
  • Posts: 152
Re: iterating corners to find period
« Reply #12 on: October 09, 2020, 09:59:49 PM »
gerrit, thanks for the ball code, i'll check it out.

ok, i implemented the polygon method as stated, simply checking for when 1 or 3 of 4 edges cross the positive half of the real axis.  i had originally wondered if maybe you could keep going with this, and get a series of lowering periods representing the minis you passed, all the way back to the top.  so here i set the iteration counter back to 0 when the origin in polygon test triggers, and continue on until the period found equals 1.  i have no idea if this is actually meaningful or useful data, i just envisioned if maybe you could do something like this to automatically find a path of minis from a zoomed in location back out to the top, for use with perturbation?

as a test, starting zoomed out and then just zooming straight into a series of minis of minis i get this output:

1
3  1
6  2  1
9  9  4  5  2  2  1
18  15  6  10  2  1
36  30  7  1
36  36  99  4  3  15  2  1
302  22  216  33  3  19  9  3  5  1
500  2  2  10  59  16  2  1
1188  560  8  5  3  1

i notice sometimes it goes from lower to higher but overall looks about like what i expected.  so then my question then is still if this is actually useful or not really? :)  i was envisioning maybe using the size of the polygon at each period as an estimate for where to start with root finding steps for that period, find the nuclei, and use as a series of references?

Offline marcm200

  • 3c
  • ***
  • Posts: 925
Re: iterating corners to find period
« Reply #13 on: October 10, 2020, 08:15:21 AM »
The following is an experimental idea I had last night. I haven't actually implemented anything yet as there are some wobbly inferences drawn, so any input is welcome.

Suppose I want to perform the capturing iterations with a square. 3 corners are individual complex points, one is a small complex interval (the "fat" point).

  • iterations are performed exact, the individual points probably with a rationally complex number type, the fat point's with IA
  • by construction, the fat point will always be an axis-parallel rectangle (wobbly: will it ever not grow larger than the 2-square due to rounding and warping?)
  • if at some iteration the fat region straddles an axis and in particular if it had devoured the origin - the whole process is discarded and nothing deduced (wobbly: will it ever not devour the origin before polygon-capturing it?)
  • One finds the convex hull of all points (I think this is the set of the iterates of the 3 individual starting points and 1-4 of the current fat region's corners and should be fairly quick to determine)
  • if the convex hull captured the origin, any 4-point polygon with an arbitrary choice of a point from the fat region and the iterates of the other 3 would have captured the origin (wobbly)
  • as the fat region contains the iterates of the starting fat square, it is as if one had computed numerours 4-point polygons at once, which all capture the origin and hence have the same period
  • therefore the initial area-bearing fat point is fully inside (or at the boundary) of one specific hyperbolic component
  • wobbly: what happens if the initial four points are not in the same component? (no capturing, edge-crossing, fast growing polygon area?

If that all panned out, one could use this to arrive at a reliable lower bound on the area of the Mset. But it kind of sounds too good to be true - as I learnt from my ongoing matrix calculations (determinant of a large, 116x116 matrix with symbolic polynomial entries), there is no shortcut most of the times around the complexity of a problem.



xx
"Time Span"

Started by cricke49 on Fractal Image Gallery

0 Replies
803 Views
Last post August 02, 2018, 07:05:21 AM
by cricke49
clip
A new style of fractal imagery using fractal neural style transfer

Started by iRyanBell on Fractal Image Gallery

3 Replies
698 Views
Last post October 03, 2020, 10:50:39 PM
by Jimw338
xx
Birdie Style

Started by gannjondal on Fractal Image Gallery

1 Replies
813 Views
Last post May 08, 2018, 02:39:37 PM
by who8mypnuts
xx
Possible to evaluate z = z^2+c without iterating?

Started by AxiomVerge on Noob's Corner

4 Replies
249 Views
Last post December 09, 2020, 10:56:26 PM
by AxiomVerge
clip
Neural Style Transfer with Fractal Art

Started by reallybigname on Other Artforms

1 Replies
667 Views
Last post July 20, 2019, 04:25:41 PM
by reallybigname