🚀 go-pugleaf

In article <C3Ar79.C1u@world.std.com> mrob@world.std.com (Robert P Munafo) writes:
>If any of you are using the "luams" program (posted by Ocie Mitchell around
>Feb. 12th, at the beginning of the GIPPP project) you might wish to
>incorporate one or both of the following speed improvements.  Neither will
>have any effect on the results generated by the program.
> 
>Period detection
>~~~~~~~~~~~~~~~~
>There are many methods of period detection that could be used.  For our
>purposes, we only need to know that a period exists.  We don't care about
>the actual value.  I have found that the following method works quite well:
>* Save X and Y.  After 1 iteration, compare the current X and Y to the
>  saved value.
>* Save X and Y again.  After 2 additional iterations, compare the current X
>  and Y to the saved value.
>* Save X and Y again.  After 3 additional iterations, compare the current X
>  and Y to the saved value.
>(and so on, you get the idea!)
> 

The problem is that you have to specify a small enough epsilon so that
|z(current)-z(last)| < epsilon only occurs when the orbit converges.  A
heuristic I have heard is epsilon=1/2 pixel width, but there is always the
danger of counting a pixel in the set because it does not escape fast enough

>The amount of speedup you gain from this will depend on the precision of
>your floating-point math, and on roundoff errors.  However, period
>detection will not cause the program's results to be different.
> 
>Avoid computing X*X and Y*Y twice
>~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
>The expression "xx*xx+yy*yy" is used in the for loop, and "xx*xx-yy*yy" is
>used immediately afterwards in the iteration.  With most compilers you
>will get a significant speed improvement if you declare two new variables
>"x_squared" and "y_squared" and use them to avoid computing xx*xx and
>yy*yy twice.

oh, I'll add this

> 
>This change might not speed things up, depending on how smart your
>compiler is.  I would suggest benchmarking the program with and without
>the change.
> 
>After implementing these changes (and cleaning up the indentation a little
>bit), the is_in routine looks like this:
> 

I'll make modifications to the code, which I will place on anonymous ftp
fenris.claremont.edu in the pub/luams directory sometime this evening.

>int is_in(double x, double y, int limit)
>{
>   int c;
>   double xx,yy,d;
>   double x_save, y_save;
>   double x_squared, y_squared;
>   int next_compare, next_period;
> 
>   xx=yy=0;
>   x_save = y_save = 0;
>   x_squared = y_squared = 0;
>   next_compare = next_period = 1;
> 
>   for (c=0;(c<limit) && (x_squared+y_squared<4);c++)
>      {
>      d = x_squared - y_squared + x;
>      yy = 2*xx*yy + y;
>      xx = d;
>      
>      next_compare--;
>      if (next_compare == 0)
>         {
>         if ((xx==x_save) && (yy==y_save))  

I'll change this to xx-xsave<epsilon && so forth

>            return(1);
>         x_save = xx;
>         y_save = yy;
>         next_period++;
>         next_compare = next_period;
>         }
>      
>      x_squared = xx*xx;
>      y_squared = yy*yy;
>      }
> 
>   if (c==limit)
>      return(1);
> 
>   return(0);
>}
>-- 
>mrob's .sig #3 |     the Mandelbrot Set.             _,,___~-    '     Ra   _~
>collect all 5! |                                           ~^___.-,          \,

thanks for the input, Ocie


Ocie Mitchell                | what this .sig lacks in size it makes up in 
omitchel@fenris.claremont.edu | lack of originality.
-----------------------------+--------------------------------------------