Julia sets: True shape and escape time

  • 104 Replies
  • 3111 Views

0 Members and 1 Guest are viewing this topic.

Offline marcm200

  • *
  • Fractal Frogurt
  • ******
  • Posts: 485
« Reply #90 on: November 09, 2019, 07:11:59 PM »
"2+6+13"

z^4+A*z+c with
A=-0.40283203125+0.162109375*i
c=0.3046875+0.8125*i

at level 16 with a period-2 attracting cycle (yellow), period 6 (green) and period 13 (turquois). Upper right is a small point-sampled comparison.

Since the gray enclosed shape shrunk substantially during refinement level increase, it was still possible to use long double precision even at level 16 where the whole 2-square would have called for float128. This saved a lot of computation time (from earlier images long double is about 10 times faster than float128).

Offline marcm200

  • *
  • Fractal Frogurt
  • ******
  • Posts: 485
« Reply #91 on: November 11, 2019, 04:10:24 PM »
"The tiniest immediate basin ever"

z^4+A*z+c with
A=0.2431640625-0.00439453125*i
c=0.58203125-1.0078125*i

A period-4 cycle (bright green = immediate basin, pale green: attraction basin), but very interesting is the turquois period-3 cycle: Two immediate basins are readily visible (bright cyan), but the third one is so tiny (red arrow, bottom right), I had to upload the 8K-image here (already downscaled 16-fold tw.). During further downsizing that tiny blob will vanish soon.

This must easily be the tiniest immediate basin I've encountered thus far. When I first saw it in the pointsampled version (upper right) I wasn't sure whether black would emerge in the TSA there and hence if the whole cycle could be detected at decent levels. But luckily level 17 and float128 were enough.


Offline marcm200

  • *
  • Fractal Frogurt
  • ******
  • Posts: 485
« Reply #92 on: November 20, 2019, 08:08:08 PM »
"Cell-mapped periodic points"

The TSA by design constructs interior regions as large as possible. So when black emerges, the immediate basins show very roughly where the periodic points lie. I was interested to see if one could narrow their position down.

If I recall correctly (I hope I'll find the reference again), every orbit of an attracted point comes arbitrarily close to every periodic point in its cycle. So, for the cell-mapped version that means every interior square in an immediate basin has a path to every periodic point.

So I implemented a quick (by coding time, not by running time that is) routine, that finds the intersection of all cell-mapped orbits of interior points of the immediate basins of a cycle.

The right part of the image below depicts the evolution of the cubic set of the article where the periodic fix points lie (red), left is the immediate basin.

The TSA outputs for the two fix points:
Code: [Select]
lower fix point [-0.0078125..0.0078125] x [-0.44921875..-0.4296875]*i
upper fix point [-0.0078125..0.0078125] x [0.53515625..0.55078125]*i

A numerical analysis (Newton) of z=f(z) showed values which are quite a good match:
Code: [Select]
attract 4.9406564584124654418e-324,-0.43944253312498643416
attract 0,0.54401695734564481377

Next step is to check for longer cycles.


Online pauldelbrot

  • *
  • 3f
  • ******
  • Posts: 1510
« Reply #93 on: November 20, 2019, 09:36:01 PM »
The right part of the image below depicts the evolution of the cubic set of the article where the periodic fix points lie (red), left is the immediate basin.

Erm ... what image below?

Offline marcm200

  • *
  • Fractal Frogurt
  • ******
  • Posts: 485
« Reply #94 on: November 20, 2019, 09:56:54 PM »
Sorry for the mistake. Here's the image.

Offline marcm200

  • *
  • Fractal Frogurt
  • ******
  • Posts: 485
« Reply #95 on: November 21, 2019, 03:27:16 PM »
"Cell-mapped periodic points #2"

Cubic polynomial, 2 attracting cycles of length 6 and 9. The red squares in the immediate basins (bright colors) contain the detected periodic points.

For the algorithm, phrased as in the article, it holds: For any cycle, the union of the red complex intervals in the cycle's immediate basins contains all the periodic points of the cycle.

So it is not necessary to fully compute the intersection of all orbits, currrently I terminate the process if the initial set (the first (arbitrarily chosen) point's orbit) has been reduced to about 1% of its initial cardinality.

A comparison with the numerical orbits of the polynomial's critical points (max it 25000) reveals the hoped-for match:

Period-6 cycle:
Code: [Select]
TSA output numerical: point in cp's orbit
#0 [0.35595703125..0.36468505859375] x [0.76910400390625..0.77447509765625] 0.35806310244,0.771240453
#1 [-0.361328125..-0.3431396484375] x [0.1356201171875..0.1561279296875] -0.34873345455,0.141900593
#2 [-0.518310546875..-0.50946044921875] x [0.15673828125..0.1668701171875] -0.51591852327,0.163937456
#3 [0.57232666015625..0.57611083984375] x [0.30615234375..0.3118896484375] 0.57369312764,0.310472064
#4 [0.6099853515625..0.6114501953125] x [0.291748046875..0.2939453125] 0.61105635813,0.292288557
#5 [0.39971923828125..0.40350341796875] x [0.81243896484375..0.8145751953125] 0.40267394036,0.813829816

Period-9 cycle:
Code: [Select]
TSA output numerical: point in cp's orbit
#0 [0.338134765625..0.35565185546875] x [-0.1561279296875..-0.1370849609375] 0.3474067645 -0.1459788657
#1 [0.519287109375..0.5245361328125] x [0.5142822265625..0.51910400390625] 0.5217326829 0.516825955
#2 [0.2291259765625..0.2340087890625] x [-0.2855224609375..-0.281005859375] 0.2312489379 -0.2831529157
#3 [0.33465576171875..0.343505859375] x [-0.35772705078125..-0.3485107421875] 0.3388952498 -0.3535984611
#4 [0.00201416015625..0.0115966796875] x [0.70263671875..0.71319580078125] 0.0066389227 0.7075494489
#5 [0.04693603515625..0.0489501953125] x [0.786865234375..0.788818359375] 0.0481154131 0.7877877953
#6 [0.57147216796875..0.5732421875] x [0.517822265625..0.51953125] 0.5724749423 0.5186421988
#7 [-0.007568359375..-0.0037841796875] x [0.8074951171875..0.81146240234375] -0.0056160678 0.8097480094
#8 [0.5604248046875..0.56134033203125] x [0.4923095703125..0.49322509765625] 0.560850095 0.492687769

Currently I encountered always exactly as many red regions (geometrically disjoint) as there are periodic points. However, I cannot prove that this will always be the case if the whole intersection set is computed.

Terminating prematurely (1% rule) I think it might very well be possible that there are extraneous red regions which vanish when continuing the calculation further.

Next step now is to optimize and extend it to 3D.


Offline Adam Majewski

  • *
  • Fractal Feline
  • **
  • Posts: 194
« Reply #96 on: November 21, 2019, 05:55:24 PM »
How do you find such intereseting examples ? ( period 6 and 9)

Offline marcm200

  • *
  • Fractal Frogurt
  • ******
  • Posts: 485
« Reply #97 on: November 22, 2019, 10:04:13 AM »
How do you find such intereseting examples ? ( period 6 and 9)

I'm running from time to time an A,c-parameter space walk (brute force) in a rather wide grid (-2..+2 in ~0,01 or larger steps) for the family z^n+A*z+c, adding a small random dyadic fraction to the 4d coordinates to get variation.

Following numerically the orbits of the critical points with a rather high max it of 25000 it's possible to get the number of attracting cycles and their length to some accuaracy level in a decent time. If those A,c-parameter pairs pass some filters (mostly sum of length of cycles and diversity) I scan through small overview pictures manually.

Then I use interesting A,c pairs (shape-wise or from the filter values) and some small deviations from it to compute level 10-12 TSA images, as sets wiith similar shapes can show a different dynamical behaviour w.r.t. the level at which interior cells emerge.

I'll take the fastest one and see how many cycles can be detected up to level 18-19.


Offline marcm200

  • *
  • Fractal Frogurt
  • ******
  • Posts: 485
« Reply #98 on: November 29, 2019, 04:20:27 PM »
My favourite shape lately. Quartic polynomial, 3 attracting cycles of length 2,2,4.

The upper turquois immediate basin (period 2) shows actually 2 regions whose union contains the periodic point - the larger black rectangle has next to its lower left corner an additional point. So what I mentioned earlier actually happens: extraneous regions if not all orbits are used for constructing the intersection to the fullest.

The positions of the periodic points in the red period-2 cycle could not be shrunk as far as in the others. Maybe that's due to the very limited number of orbits followed, or maybe the dynamics of that cycle is different from the other - all orbits first circling around the periodic point and then falling in?.

Constructing the full intersection of all orbits is computationally too expensive. Therefore and because any orbit by itself is an approximation of the periodic points' location, I decided to use a heuristic approach instead.

Starting with the geometric center of a circumferenced rectangle and hopping through the Fatou components of a cycle iteratively - the first approximation is an orbit that lies (hopefully) closer to the periodic points and has fewer orbit points than starting at the basin's border (and then usinge stop criteria like a 90% cardinality decrease or following a fixed number of orbits which do not discard cells).

Lately I got the impression that one gets often a smaller periodic region identified when using an early exit at a higher refinement level than intersecting all orbits at a lower one. So that goes nicely with the heuristic.

Offline gerson

  • *
  • Fractal Furball
  • ***
  • Posts: 233
« Reply #99 on: November 29, 2019, 08:23:44 PM »
Using Fractal Zoomer to do Reply #98 image.
80 iterations

Offline Adam Majewski

  • *
  • Fractal Feline
  • **
  • Posts: 194
« Reply #100 on: November 29, 2019, 08:44:27 PM »
I'm running from time to time an A,c-parameter space walk (brute force)

WHat is the reason for : 2^-25  ?

Offline marcm200

  • *
  • Fractal Frogurt
  • ******
  • Posts: 485
« Reply #101 on: November 29, 2019, 09:19:46 PM »
WHat is the reason for : 2^-25  ?
When I started with this article back in March this year, my initial formulas were z^2+c and z^2+c*z.

In expanded form with real coordinates: z=(x+i*y) and c=(d+e*i):

( x▓-y▓ + d, 2xy + e )
or ( d*x + x▓ - e*y - y▓ , e*x + d*y + 2x*y )

To accurately represent a sum, the widest two terms can be apart is 53 bits (mantissa precision for C++ double) and all other must lie in this range.

The smallest non-zero value of x,y is "axis range / pixel count", i.e. 4 (escape radius of 2, hence axis -2..+2) divided by 2^refinement level.

So for x^2 this goes to 2^-26 as the lowest possible value for x. And since d,e are multiplied with x in the 2nd formula, the same goes for d and e. As I do not like to work "on the edge" I used a buffer of 1-2 bits and came to the lowest value of 2^-25 for d,e (and refinement level limit of 27 which is currently outside a reasonable range).

For the 1st formula z^2+c, the seed value could go as little as 2^-48 (stated in the article) as it is only added.

For long double and float128 one could go lower in both formulas, but I haven't explored that.


Offline marcm200

  • *
  • Fractal Frogurt
  • ******
  • Posts: 485
« Reply #102 on: December 01, 2019, 09:46:16 PM »
"Local version"

Although the Figueiredo algorithm is global in nature - one needs to have an escape radius that contains the whole Julia set - there are regions where a local version suffices.

The immediate basins of a periodic cycle only iterate to one another. If those basins are contained within a rectangle, one can detect bounded cells using an escape radius that is too low to encompass the whole filled-in Julia set - if a cell within the rectangle has no path to the outside it is clearly bounded.

Here's a quadratic example with a period-14 cycle, where a point-sampled image served as a way to estimate the region of the periodic points (left, blue rectangle) and an area that does not contain all (lower, red rectangle).

Then I computed those two regions with the localTSA to see whether black cells can be detected (right images).

As expected/hoped when analyzing only the inside of the immediate basin circumferencing blue rectangle, the cycle could be detected (immediate basins = bright yellow). The negative control did not show any interior cells (lower).

A comparison between the fully TSA computed set (not shown) with the 2-step-approach: first localTSA restricted to the immediate-basin containing rectangle, and then followed by judging the rest of the image with the correct escape radius of 2 (2nd image). Both images are luckily bit-identical.

Notes:
  • The localTSA can by design only detect interior cells, but not escaping ones as the imposed rectangle clearly is not a valid escape criterion for all cells.
  • Since every attraction basin has a path to every immediate basin some of those attraction ones - if contained in the rectangle of interest, will also be (partially) identified, but most won't.
  • The trampoline-like shape is because I judge cells directly as white that leave with a single iteration the valid escape radius of 2.
  • This approach exploiting the containedness of the immediate basins is computationally faster than checking for every pixel whether it is part of an invariant set.


Offline marcm200

  • *
  • Fractal Frogurt
  • ******
  • Posts: 485
« Reply #103 on: December 03, 2019, 01:34:33 PM »
"TSApredictor"

A cubic set z^3+A*z+c with two cycles: period-2 (middle image, lower part) and period-23 (upper) (the longest cycle I've found so far).
c=(1146224-9497150*i) * 2^-25
A=(58726672+344588*i) * 2^-25

The small cycle is early detectable at refinement level 12 (classicTSA, left image).

For the 23-cycle I estimated the location of its periodic points and computed [-0.0625..0.40625] x [0.4140625,0.8828125]*i with the localTSA from levels 15 to 18. At level 18 black emerges in that region - and this took not even 2 hours in total.

The localTSA can be used to predict when black will emerge in the full TSA as they both use the same interior cell detection method. That would help a lot in my still ongoing quest for a level-20/21 image with new information.

I'm currently trying to integrate all the manual steps into a single "TSApredictor" tool.

Technical details:
  • The given rectangle of interest is internally expanded to fit the vertices of the (low-resolution) reverse cell graph.
  • The pale green non-immediate basins emerge because of this enlargement.
  • TSA images were computed in the 4-square and then cropped out. So refinement level 18 here corresponds to the same resolution as level 17 with the standard range 2.
  • I used a new memory structure that allocates - like in the 3D case - only streaks of gray. Most of the white does not occupy memory.
  • Colors of cycles are not identical among programs.

Offline marcm200

  • *
  • Fractal Frogurt
  • ******
  • Posts: 485
« Reply #104 on: Yesterday at 06:53:59 PM »
"fastTSApredictor and a parameter-space walk"

z4+A*z+c with period-2, period-4 and period-8 cycles.

Through a brute-force parameter-walk I encountered an interesting 3-armed set, revealing the north and south arms to be quite different. Currently at level 17, only the period-2 one emerged (upper row, yellow-backgrounded).

The TSApredictor claims no interior cells for the other two cycles up to level 23. Using the c-parameter-space for the above formula (values in the images) I selected close-by seeds and analyzed those as well.

For one the predictions were (set contained in the 2-square): level 12 for period-2, level 15 for period-4 and level 16 for period-8 - at which the cycles luckily really were found (large image = final result; upper row with white background = evolution).

I'll release the predictor code when the documentation is finished.


Algorithmic details:
Recap: Placing a rectangle around the periodic points of a cycle enclosing its immediate basins traps the periodic points' orbit. Checking all cells therein whether they have a path to outside the rectangle leaves one with interior cells if the resolution is high enough.

The TSApredictor tool had to meet two criteria: Fast computation (at most a few minutes for level 18, I do not want to spend much time on it) and correctness in the affirmative: If it finds interior at a refinement level, the claim "At that level or earlier black will be found by the fullTSA" should hold.

This approach becomes pretty costly once reaching higher levels, especially when using float128, so I am restricting the judging process to small neighbourhoods around the cells that contain the numerically found periodic points. The idea being, that the dynamics there is tame, so orbits do not deviate much and (hopefulyl) land in the neighbourhood of the iterated-to next cycle point.

This reduces the number of pixels to compute quite a bit.

It will lead to false negative results if an orbit leaves those neighbourhoods but still remains in the immediate basins (it would be identified judging all enclosed pixels though). But for only minutes of computation that's acceptable, especially since I'm mostly not focused on a specific seed value but rather on an interesting feature of a set so I can use nearby values which often exhibit easier dynamics (parameter-space walk).


clip
3d Julia sets: True shape

Started by marcm200 on Image Threads

23 Replies
567 Views
Last post November 28, 2019, 01:41:42 PM
by marcm200
clip
True-shape based C++ oracle for the int-/exterior of Julia sets

Started by marcm200 on Programming

6 Replies
233 Views
Last post August 23, 2019, 10:47:10 AM
by marcm200
clip
3D M-set for tricomplex numbers: Escape time and shape change?

Started by marcm200 on Fractal Mathematics And New Theories

2 Replies
199 Views
Last post May 04, 2019, 09:58:37 PM
by marcm200
clip
Escape Time Blur

Started by AlexH on Share a fractal

0 Replies
351 Views
Last post August 15, 2018, 05:42:06 AM
by AlexH
clip
Rational maps: True shape

Started by marcm200 on Fractal Mathematics And New Theories

3 Replies
155 Views
Last post October 26, 2019, 10:09:47 AM
by marcm200