Another possible way to accelerate MB set deep zooming

  • 170 Replies
  • 4882 Views

0 Members and 1 Guest are viewing this topic.

Offline claude

  • *
  • Fractal Freak
  • **
  • Posts: 662
    • mathr.co.uk
« 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?)?

Offline gerrit

  • *
  • 3f
  • ******
  • Posts: 1243
« 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.

Offline claude

  • *
  • Fractal Freak
  • **
  • Posts: 662
    • mathr.co.uk
« 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.

Offline claude

  • *
  • Fractal Freak
  • **
  • Posts: 662
    • mathr.co.uk
« 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.ppm
real 0m27.734s
user 6m41.971s
sys 0m0.040s
$ time ./kf-2.12.13.1/kf.64.exe -s 1e1242.kfs -l 1e1242.kfr -p 1e1242-kf.png
real 41m13.686s
user 614m10.583s
sys 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 »

Offline gerrit

  • *
  • 3f
  • ******
  • Posts: 1243
« 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

Offline claude

  • *
  • Fractal Freak
  • **
  • Posts: 662
    • mathr.co.uk
« 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...

Offline gerrit

  • *
  • 3f
  • ******
  • Posts: 1243
« 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.

Offline claude

  • *
  • Fractal Freak
  • **
  • Posts: 662
    • mathr.co.uk
« 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.

Offline knighty

  • *
  • Fractal Feline
  • **
  • Posts: 169
« 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.

Offline claude

  • *
  • Fractal Freak
  • **
  • Posts: 662
    • mathr.co.uk
« 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?

Offline gerrit

  • *
  • 3f
  • ******
  • Posts: 1243
« 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.

Offline claude

  • *
  • Fractal Freak
  • **
  • Posts: 662
    • mathr.co.uk
« Reply #71 on: June 14, 2018, 01:03:01 PM »
added makefile
added floatexp support (always used, much slower than the long double version for shallower zooms)
added jitter (always on)

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

Offline claude

  • *
  • Fractal Freak
  • **
  • Posts: 662
    • mathr.co.uk
« 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

Offline claude

  • *
  • Fractal Freak
  • **
  • Posts: 662
    • mathr.co.uk
« 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
4. port per-pixel calculations threading from openmp to winapi threads
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)

Offline claude

  • *
  • Fractal Freak
  • **
  • Posts: 662
    • mathr.co.uk
« 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


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

Started by greentexas on Fractal Mathematics And New Theories

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

Started by claude on Fractal Mathematics And New Theories

4 Replies
274 Views
Last post February 19, 2018, 04:46:10 PM
by claude
xx
How to avoid zooming too deep?

Started by noahfence on Mandelbulber

2 Replies
149 Views
Last post June 10, 2018, 02:47:48 AM
by mclarekin
xx
Mandelbrot set deep zooming in the web browser

Started by claude on Other

0 Replies
285 Views
Last post October 29, 2017, 11:00:15 PM
by claude
xx
Deep n brassy

Started by timemit on Fractal Image Gallery

0 Replies
179 Views
Last post November 09, 2017, 07:11:35 PM
by timemit