### Another possible way to accelerate MB set deep zooming

• 178 Replies
• 7735 Views

0 Members and 1 Guest are viewing this topic.

• 3e
• Posts: 1065

#### Re: Another possible way to accelerate MB set deep zooming

« Reply #60 on: June 04, 2018, 08:05:32 PM »
What's the current status?  Where are the latest maths PDFs (gerrit?) and/or reference implementation source codes (knighty?)?

• 3f
• Posts: 1637

#### Re: Another possible way to accelerate MB set deep zooming

« Reply #61 on: June 04, 2018, 08:49:53 PM »
What's the current status?  Where are the latest maths PDFs (gerrit?) and/or reference implementation source codes (knighty?)?
https://fractalforums.org/fractal-mathematics-and-new-theories/28/fast-mandelbrot-set-research-summary/723/msg3665#msg3665
contains derivation of the recurrence to compute SSA coefficients. None of my bailout methods work, you can ignore that. Knighty found a bailout that works, see posts in this thread. His code is posted here https://fractalforums.org/fractal-mathematics-and-new-theories/28/another-possible-way-to-accelerate-mb-set-deep-zooming/277/msg4006#msg4006.

• 3e
• Posts: 1065

#### Re: Another possible way to accelerate MB set deep zooming

« Reply #62 on: June 05, 2018, 01:18:38 AM »
Here is some Maxima code for calculating the super series approximation (SSA) coefficient iterations, based on my math stackexchange answer https://math.stackexchange.com/a/2449476
Code: [Select]
sumexpand: true$cauchysum: true$F(p, c, z) := z^p + c$D(p, c, z) := expand(F(p, c + C, z + Z) - F(p, C, Z))$A(p) := niceindices(collectterms(D(p,c,sum(a[i]*c^i,i,1,inf)),c))$S(p) := niceindices(collectterms(D(p,c,sum(sum(a[i,j]*c^i*z^j,i,0,inf),j,0,inf)),c))$S(2);
Rearranging the output of tex(S(2)) a bit (renaming indices to be nicer, etc) gives:

$c + \sum_i \sum_j c^i z^j \left( 2 Z a_{i,j} + \sum_{k=0}^i \sum_{l=0}^j a_{i-k,l} a_{k,j-l} \right)$

from which it is relatively easy to read off the 'a(i,j)' coefficient iterations as powers of c^i z^j.

• 3e
• Posts: 1065

#### Re: Another possible way to accelerate MB set deep zooming

« Reply #63 on: June 05, 2018, 04:45:09 AM »
Here's some changes I made to nanoMB to make it read the location from KFR files:
Code: [Select]
--- mb.cpp.old 2018-06-05 01:36:50.638327340 +0100+++ mb.cpp.new 2018-06-05 03:31:38.276282647 +0100@@ -22,6 +22,7 @@ #include <limits>  #include <iostream>+#include <fstream>  #if 0 #include <complex>@@ -369,17 +370,62 @@      // parse arguments   // TODO FIXME bad arguments can read past end of argv+  char *memblock = 0;+  R_lo radius = 0;   for (N a = 1; a < argc; ++a)   {+    if (!strcmp("--kfr", argv[a]))+    {+      const char *kfrfile = argv[++a];+      size_t size;+      ifstream file(kfrfile, ios::in|ios::binary|ios::ate);+      if (file.is_open())+      {+        size = file.tellg();+        memblock = new char [size + 1];+        file.seekg (0, ios::beg);+        file.read (memblock, size);+        file.close();+        memblock[size] = 0;++        for (size_t i = 0; i < size; ++i)+          switch (memblock[i])+          {+            case ' ':+            case '\r':+            case '\n':+              memblock[i] = 0;+          }++        for (size_t i = 0; i < size; )+        {+          if (!strcmp("Re:", memblock + i))+            sre = memblock + i + strlen(memblock + i) + 1;+          else+          if (!strcmp("Im:", memblock + i))+            sim = memblock + i + strlen(memblock + i) + 1;+          else+          if (!strcmp("Zoom:", memblock + i))+            radius = 2 / r_lo(memblock + i + strlen(memblock + i) + 1);+          else+          if (!strcmp("Iterations:", memblock + i))+            maxiters = atoi(memblock + i + strlen(memblock + i) + 1);+          i = i + strlen(memblock + i) + 1;+        }+      }+      else+      {+        cerr << "Unable to open file " << kfrfile << "'\n";+        abort();+      }+    }+    else     if (!strcmp("--width", argv[a]))       width = atoi(argv[++a]);     else     if (!strcmp("--height", argv[a]))       height = atoi(argv[++a]);     else-    if (!strcmp("--maxiters", argv[a]))-      maxiters = atoi(argv[++a]);-    else     if (!strcmp("--orderM", argv[a]))       bm = atoi(argv[++a]);     else@@ -389,18 +435,6 @@  if (!strcmp("--period", argv[a]))       period = atoi(argv[++a]);     else-    if (!strcmp("--precision", argv[a]))-      precision = atoi(argv[++a]);-    else-    if (!strcmp("--re", argv[a]))-      sre = argv[++a];-    else-    if (!strcmp("--im", argv[a]))-      sim = argv[++a];-    else-    if (!strcmp("--radius", argv[a]))-      sradius = argv[++a];- else     if (!strcmp("--escape", argv[a]))       Bout = r_lo(argv[++a]);     else@@ -411,16 +445,12 @@       cerr << argv[0] << ": unexpected: " << argv[a] << endl;       cerr         << "usage:" << endl+        << "  --kfr s.kfr" << endl         << "  --width n" << endl         << "  --height n" << endl-        << "  --maxiters n" << endl         << "  --orderM n" << endl  << "  --orderN n" << endl  << "  --period n" << endl-        << "  --precision n" << endl-        << "  --re f" << endl-        << "  --im f" << endl-        << "  --radius f" << endl  << "  --escape f" << endl         << "  --output s.ppm" << endl         ;@@ -428,7 +458,9 @@     }   }   // render-  R_lo tmax(r_lo(sradius));+  if (! (radius > 0))+    radius = r_lo(sradius);+  R_lo tmax(radius);   precision = N(-std::log2(tmax)) + 64;//set the precision == log2(radius) + Pmax (63)   mpreal::set_default_prec(precision);//Was: mpfr_float::default_precision(precision);   C_hi c((R_hi(sre)), (R_hi(sim)));
One benchmark shows nanoMB 100x faster than KF, but the shapes are different   (Use scroll wheel in attachment lightbox to compare).  I don't know how to check which is correct without doing unapproximatead iterations and the time necessary for that may be infeasible for this example... the kfr file has a Ratio that isn't 360 (which means it is stretched/skewed)

Code: [Select]
$time ./nanomb --kfr 1e1242.kfr --width 1024 --height 1024 --orderM 4 --orderN 4 --period 179301 --escape 5e-826 --output 1e1242-nanomb.ppmreal 0m27.734suser 6m41.971ssys 0m0.040s$ time ./kf-2.12.13.1/kf.64.exe -s 1e1242.kfs -l 1e1242.kfr -p 1e1242-kf.pngreal 41m13.686suser 614m10.583ssys 0m21.057s`
Zooming out a factor of 10 and nanoMB is "only" 4x faster than KF.
Zooming out to 1e1086 (4x embedded Julia) and nanoMB is 5-10x slower tjnan KF (but the glitches are much smaller, which is interesting).

EDIT I'm using the atom domain size as super-escape-radius/bailout -not sure if this is correct?  Should I be using |a_01| / |a_02| instead (at the p'th iteration I presume?)?
« Last Edit: June 05, 2018, 06:32:44 AM by claude, Reason: superbailout question »

• 3f
• Posts: 1637

#### Re: Another possible way to accelerate MB set deep zooming

« Reply #64 on: June 05, 2018, 09:01:38 AM »
EDIT I'm using the atom domain size as super-escape-radius/bailout -not sure if this is correct?  Should I be using |a_01| / |a_02| instead (at the p'th iteration I presume?)?
I think that was the last thing we tried. Hopefully Knighty can chime in as I don't know any more than what was posted in this thread, it was a while ago.
I think he came up with better bailouts (main problem) after posting his code.
I've attached my testing code which should have all the things we discussed as options to try, not sure if it's of any use to you. It works, but you won't be able to run it. Driver script is sc*.m

• 3e
• Posts: 1065

#### Re: Another possible way to accelerate MB set deep zooming

« Reply #65 on: June 05, 2018, 01:32:49 PM »
I spent many hours trying to get the method in knighty's first post to work, failed as hinted at in later posts by knighty which I missed on rereading the thread the first few times..

The problem is that when the periods aren't multiples, when the deeper higher period Z is 0, the shallower lower period Z will (in general) be large, causing issues with the requirement for small deltas with perturbation and SSA by extension.  Trying to iterate with single-step perturbation iterations until the shallower Z is 0 leads to a complementary problem: the deep reference Z is large then.  And single-stepping until escape after SSA bailout is slower than the regular SA stuff for all but the closest-to-minibrot zooms, at least in my tests at one location...

• 3f
• Posts: 1637

#### Re: Another possible way to accelerate MB set deep zooming

« Reply #66 on: June 05, 2018, 08:07:11 PM »
I spent many hours trying to get the method in knighty's first post to work, failed as hinted at in later posts by knighty which I missed on rereading the thread the first few times..

The problem is that when the periods aren't multiples, when the deeper higher period Z is 0, the shallower lower period Z will (in general) be large, causing issues with the requirement for small deltas with perturbation and SSA by extension.  Trying to iterate with single-step perturbation iterations until the shallower Z is 0 leads to a complementary problem: the deep reference Z is large then.  And single-stepping until escape after SSA bailout is slower than the regular SA stuff for all but the closest-to-minibrot zooms, at least in my tests at one location...
I don't understand what you mean with deep and shallow periods. Periods of what? How can a period be 0 except for the main body?

Way I understand it is you find the dominant nucleus (say period p), build SSA series, then super iterate until "super-escape". You then have bands where you have completed $$k_i p$$ iterations with $$k_i$$ different for each band. SSA is then done and you proceed normally except you have a "hot start". Problem is to figure out a good s-escape condition: if too aggressive your hot start may just be wrong, if too conservative no speedup results. It may be unsolvable, still a 100X speedup for some locations is a nice carrot...

I assume your test location is beyond my code's ability to try (can only go to about 1e250).

I sent knighty a PM for his latest code and ideas, the s-escape condition is his idea and I don't understand if and why it works/doesn't work.

• 3e
• Posts: 1065

#### Re: Another possible way to accelerate MB set deep zooming

« Reply #67 on: June 06, 2018, 01:40:19 PM »
Quote
I don't understand what you mean with deep and shallow periods. Periods of what? How can a period be 0 except for the main body?
This is relative to the idea in knighty's first post in this thread, where you iterate with the deepest nucleus, then switch to progressively shallower nuclei as z gets bigger.

#### knighty

• Fractal Feline
• Posts: 185

#### Re: Another possible way to accelerate MB set deep zooming

« Reply #68 on: June 07, 2018, 08:35:00 PM »
Hi,
That idea does work only in one specific case: when the minibrot period is a multiple of its parents' periods.

Here is the latest-latest version I have: I've just added claude's kf files supprot. A quick bench mark: The location below (period 3422) was rendered in 1mn07s with KF, in 4mn35s with SMB and only around 11s with nanoMB. Raising the iteration limit to 500000 iteration didn't took much longer, only around 13s.

• 3e
• Posts: 1065

#### Re: Another possible way to accelerate MB set deep zooming

« Reply #69 on: June 12, 2018, 01:50:19 AM »
Would a hybrid SA / SSA work? (BTW I don't like the SSA acronym for Super Series Approximation, makes me think of Small Size Approximation instead, which I read in a paper about the Mandelbrot set some years ago).

I mean, do both the normal calculation of per-image series approximation coefficients with probe points, and calculate the SSA big-step coefficients, then for each pixel do the SSA big-steps until super-escape (or maxiters reached).  Now, if the regular per-image SA skipping is larger than the SSA skipping for that pixel, discard your SSA iterations for that pixel and use the regular SA to initialize that pixel instead.

May do some wasted work, so an option to disable it could be useful, but perhaps the automation makes it worth it for casual exploration?  Or render a lo-res image first to decide whether the SSA is worth it for that image?

• 3f
• Posts: 1637

#### Re: Another possible way to accelerate MB set deep zooming

« Reply #70 on: June 12, 2018, 03:30:16 AM »
Would a hybrid SA / SSA work? (BTW I don't like the SSA acronym for Super Series Approximation, makes me think of Small Size Approximation instead, which I read in a paper about the Mandelbrot set some years ago).

I mean, do both the normal calculation of per-image series approximation coefficients with probe points, and calculate the SSA big-step coefficients, then for each pixel do the SSA big-steps until super-escape (or maxiters reached).  Now, if the regular per-image SA skipping is larger than the SSA skipping for that pixel, discard your SSA iterations for that pixel and use the regular SA to initialize that pixel instead.

May do some wasted work, so an option to disable it could be useful, but perhaps the automation makes it worth it for casual exploration?  Or render a lo-res image first to decide whether the SSA is worth it for that image?
Sounds reasonable but perhaps simpler for a first implementation would be to just have an option to use SSA or not. You need to set the two orders of the series and want to be able to input a number that multiplies whatever s-escape condition is the default, so it's a feature to try and test for "expert" users for now I think.

• 3e
• Posts: 1065

#### Re: Another possible way to accelerate MB set deep zooming

« Reply #71 on: June 14, 2018, 01:03:01 PM »
added floatexp support (always used, much slower than the long double version for shallower zooms)

period 10000 location near -2+0i rendered at 640*4 * 360*4 with jitter and downscaled in a couple of minutes of rendering (about 27m CPU time on a 16-thread chip)

todo:
use C++ templates to allow switching between double / long double / floatexp
make the switching automatic based on zoom depth with a flag to override

• 3e
• Posts: 1065

#### Re: Another possible way to accelerate MB set deep zooming

« Reply #72 on: June 14, 2018, 03:05:33 PM »
added automatic number type selection based on precision using C++ templates
added flag to override automatic number type selection
deleted presets

• 3e
• Posts: 1065

#### Re: Another possible way to accelerate MB set deep zooming

« Reply #73 on: June 14, 2018, 06:56:32 PM »
Took about 1 hour of wall-clock time, 7 hours of CPU time (using 7 threads for Newton's method) to find the location.

Period 100000 near -2+0i, at zoom 1e120410, maxiters 100100100.  This is my deepest non-trivial render so far.

Took real 2m29.871s user 15m40.857s sys 0m0.756s to render at 640x360 in nanomb.  A different colour scheme might be better than the current nanomb default for these very dense filaments.

Timings indicate that threaded reference calculations may be worth it to speed up the whole thing (though of course threading isn't free, so there should be a way to turn it off for low precisions).

Issues to solve while porting the algorithm to KF:

1. (optionally) automagic period detection in case the period is not known
2. (optionally) automagic nucleus detection in case the center coordinate is not a mini nucleus
3. (optionally) winapi threaded reference calculations in case the precision is high enough to make it worth it
5. progress reporting mechanism for the various iterations
6. cross-validation w.r.t. other KF calculation algorithms to make sure the colours match up without seams etc
7. compile both with-derivatives (for de) and without-derivatives (for speed) iterations, for speed (my local kf-2.13 branch has an option to disable derivatives, bringing the speed back to 2.12 ball-park)

• 3e
• Posts: 1065

#### Re: Another possible way to accelerate MB set deep zooming

« Reply #74 on: June 14, 2018, 07:21:26 PM »
log(de) colouring. supersampled 4x4
real   16m2.003s
user   229m43.963s
sys   0m1.624s

EDIT: filename is misleadng, same location as previous post

### Similar Topics

###### Speeding up deep zooming using neural networks / deep learning?

Started by greentexas on Fractal Mathematics And New Theories

27 Replies
1625 Views
December 13, 2017, 10:43:46 PM
by Byte11
###### a way to accelerate Mandelbrot (etc) deep zoom world record attempts

Started by claude on Fractal Mathematics And New Theories

4 Replies
408 Views
February 19, 2018, 04:46:10 PM
by claude
###### How to avoid zooming too deep?

Started by noahfence on Mandelbulber

2 Replies
291 Views
June 10, 2018, 02:47:48 AM
by mclarekin
###### Mandelbrot set deep zooming in the web browser

Started by claude on Other

0 Replies
370 Views
October 29, 2017, 11:00:15 PM
by claude
###### DEEP IN IMAGINATION

Started by VEDES on Fractal Image Gallery

0 Replies
100 Views
March 21, 2018, 08:44:48 AM
by VEDES