🚀 go-pugleaf

Another GIPPP status update, giving lots of results that I am using to
estimate what our error will be when we do the GIPPP run.

It's real long (as usual with me, sorry!)  To summarize, I have proven to my
satisfaction that the GIPPP is worth running.  The three sources of error
are iteration roundoff error, grid size (sampling error), and number of
iterations.  For the GIPPP, it looks like the errors will be +- 0.00000050,
+- 0.00000083, and << 0.00000001 respectively.

I should also mention that Jay Hill and Yuval Fisher will be starting a GIPPP
of their own, using a fundamentally different approach which promises to yield
useful information.  To avoid confusion I will call mine "GIPPP #2 (Munafo)"
and theirs "GIPPP #3 (Fisher/Hill)"; the first was "GIPPP #1 (Fisher)".

FLOATING-POINT ROUNDOFF:  Here are the floating-point accuracy results:

  width height max_iter  pix_in_set  area       mantissa  type
   8192   4096   524288     8987154  1.50658906       24  float
   8192   4096   524288     8987091  1.50657853       33  double, truncated
   8192   4096   524288     8987089  1.50657820       44  double, truncated
   8192   4096   524288     8987086  1.50657769       53  double
   8192   4096   524288     8987088  1.50657803       64  extended

The "mantissa" column shows the number of mantissa bits, and "type" shows
what data type was used in the computation.  For the "double, truncated"
types the following formula was applied to all intermediate results to
simulate lowered resolution:
   truncated_result = (1001.0 * result) - (1000.0 * result)
This example truncates about 10 bits; it reduces "float" to 14 bits and
"double" to 44.

53-bit doubles are fairly common, and are often the highest precision
available.  64-bit "extended" is the precision used in IEEE standard
floating-point.  On Intel and Motorola machines, it is the fastest
precision available because it is the "native" precision for the hardware.

The pixel count seems to decrease as precision increases, approaching a
limit around 8987087.  The higher count for low precision is probably the
result of roundoff error on a few points that are near the boundary of the
Mandelbrot Set but not actually in the Set itself. Iterating these points,
the roundoff error can result in a cycle (of very long period, probably);
without roundoff error the iterations would not repeat and would eventually
diverge.

It appears that the pixel count never really settles down on a specific value,
but varies by one or two pixels depending on specifics of the floating-point
precision used.  This is not surprising as the 44-bit results were simulated
using a roundoff formula that does not perfectly mimic what hardware would do,
and the 64-bit results were done on a different machine from the other results.

Therefore, I think it is reasonable to put the error due to floating-point
roundoff at 3 pixels on an 8192x4096 grid, which comes out to 0.00000050.

SAMPLING ERROR (GRID SIZE) and GRID ALIGNMENT:  The sampling error can be
measured by running lots of pixel-counts that will generate independent
results, and then looking at the distribution of those results.  To
accomplish this, I used grids that differed in size (number of rows and
columns). Since these grids are pretty much unrelated to each other, they
will generate pixel counts that are unrelated:

   width height max_iter pix_in_grid  pixels_in_set      area_estimates
                                       \:/     :V:       \:/        :V:
    8200   4100   524288    33620000 9004746 9004988 1.50659418 1.50663467
    8202   4101   524288    33636402 9009125 9009089 1.50659182 1.50658580
    8204   4102   524288    33652808 9013550 9013652 1.50659698 1.50661402
    8206   4103   524288    33669218 9017977 9017856 1.50660228 1.50658207
    8208   4104   524288    33685632 9022286 9022311 1.50658770 1.50659187
    8210   4105   524288    33702050 9026667 9026786 1.50658497 1.50660483
    8212   4106   524288    33718472 9031148 9031239 1.50659874 1.50661392
    8214   4107   524288    33734898 9035432 9035580 1.50657948 1.50660416
    8216   4108   524288    33751328 9039822 9039906 1.50657772 1.50659172
    8218   4109   524288    33767762 9044262 9044393 1.50658411 1.50660593
    8220   4110   524288    33784200 9048783 9048813 1.50660381 1.50660880
    8222   4111   524288    33800642 9052983 9053174 1.50656989 1.50660167
    8224   4112   524288    33817088 9057578 9057459 1.50660152 1.50658173
    8226   4113   524288    33833538 9061982 9061969 1.50660119 1.50659903
    8228   4114   524288    33849992 9066307 9066400 1.50658756 1.50660301
    8230   4115   524288    33866450 9070724 9070722 1.50658904 1.50658871
    8232   4116   524288    33882912 9075048 9075190 1.50657491 1.50659848
    8234   4117   524288    33899378 9079556 9079578 1.50659114 1.50659479
    8236   4118   524288    33915848 9084073 9083865 1.50660867 1.50657417
    8238   4119   524288    33932322 9088543 9088366 1.50661821 1.50658887
                                 standard deviation  0.00001205 0.00001386
                                            average  1.50659220 1.50659841

                      standard deviation for all 40 runs  0.00001320
                                  average of all 40 runs  1.50659530
                    std error for average of all 40 runs  0.00000209

There are two columns of figures for pixel count and area estimates.  In
the column labeled "\:/" the grid has been aligned so that one row of
pixels goes right down Seahorse Valley (the cusp at -0.75).  In the other
column, labeled ":V:", the grid is shifted half a row to the right so
that Seahorse Valley lands midway between two adjacent rows of pixels. 
The standard deviation and average were computed seperately for these two
columns, and again for a grand total.

The area estimates vary a fair amount, as you can see.  The useful value
from these results is the standard deviation of the area estimates. 
Since each of these area estimates is a sampling estimate of the same
"true area" (notice that the max_iter value is the same for all) they are
all subject to a standard error which is related to the number of samples
and the distribution of points between solid regions and edge regions,
etc.  The standard deviation of the samples (and the standard error for
any one sample when considered out of context) is 0.00001320.  This
figure represents the error that you would expect to get with a *single*
run of 8192x4096.

  (I also computed the average area for each column and the average of all
  40 runs.  The last figure, "standard error for average of all 40 runs" is
  the expected error of this average; it is 0.00001320 divided by the
  square root of 40.  Thus, using these runs we would expect that the pixel
  count for a max_iter of 524288 is 1.50659530 +- 0.00000209.  In the next
  section I show that the error resulting from this choice of max_iter is
  about 0.00000560.)

This standard error figure of 0.00001320 can be extrapolated to larger grid
sizes by dividing by 2.0 for each grid size.  This is actually a
conservative estimate because when you use larger grids, the proportion of
pixels near the edge gets smaller.  The GIPPP will use a gridsize of 131072
x 65536, this is 16 times as large in each direction, so our conservative
estimate of the sampling error is 0.00001320 divided by 16, or 0.00000083. 
This error can be either positive or negative.

NUMBER OF ITERATIONS:  Here the error can be estimated by running counts on
the same grid size with different iteration limits.  Some results:
  maxiter    escaped not_escaped error_estim
     1023   98182559    36035169
     2047      44608    35990561 0.00187
     4095      21525    35969036 0.000902
     8191      10532    35958504 0.000441
    16383       4998    35953506 0.000209
    32767       2396    35951110 0.000100
    65535       1244    35949866 0.0000521
   131071        602    35949264 0.0000252
   262143        284    35948980 0.0000119
   524287        133    35948847 0.0000056
  1048575         79    35948768 0.0000033
These results are from iterating on a 16384x8192 grid; the total number of
pixels in the grid is 134217728.  Interpretation: the first line says
that after 1023 iterations, 98182559 pixels had escaped, and 36035169 had
not yet escaped. After 2047 iterations, an additional 44608 pixels
escaped, leaving 35990561.  At 4095 iterations another 21525 pixels had
escaped leaving 35969036, and so on.

As you can see, with each doubling of maxiter, half as many points escape.
Thus, for any line in the table, the value in the "escaped" column is
(nearly) equal to the total of all of the figures below it.  Thus, we can
use the figure in the "escaped" column to estimate the error for the
iteration limit.  The "error_estim" column gives the value of "escaped"
multiplied by the area represented by each pixel (which with this grid size
is 0.0000000419).

The GIPPP wlll use an iterations limit of 2147483648 (which is 2 to the 31st
power).  This is so large that the amount of error resulting from the
iterations limit will be insignificant compared to the other two sources
noted above.  So I estimate it as << 0.00000001; "<<" means "much less
than".

If anyone has comments on all this, let me know.  I'm getting ready to
start mailing the source code and instructions to participants.
-- 
mrob's .sig #5 |Myers-Briggs: ESTJ or ENFJ (dep. on context)          -".'
collect all 5! |  NBCS 1.9.1: B3 c f g++ k r- s+ t+            	       -`'