• January 17, 2022, 06:30:10 PM

Author Topic:  The constant in f(z) = z^2 + c  (Read 513 times)

0 Members and 1 Guest are viewing this topic.

Offline DanKje

  • Fractal Phenom
  • ****
  • Posts: 53
The constant in f(z) = z^2 + c
« on: December 02, 2021, 06:05:45 AM »
I have a very basic question that I can't find the answer to.

I'm using the basic logic for a language without complex variables.

do {             // f(z) = z^2 + c
    xsq = x * x;
    ysq = y * y;
    y = y * x;
    y = y + y + qArray[row];
    x = xsq - ysq + pArray[col];
} while((++iter < maxIterations) && ((xsq + ysq) < escThresholdSquared));

My question concerns the values in pArray and qArray which comprise the constant c = p + iq.  The code I'm using was taken from the book "Fractal Programming in C".

deltaP = viewerWidth / (double)screenWidth;
pArray[0] = mbRegion.getXMin();       
for(int col=1; col < screenWidth; col++)
    pArray[col] = pArray[col-1] + deltaP;

deltaQ = viewerHeight / (double)screenHeight;
qArray[0] = mbRegion.getYMax();
for(int row=1; row < screenHeight; row++)
    qArray[row] = qArray[row-1] - deltaQ;

Q: Why is qArray being loaded differently than pArray?

I thought that the p and q arrays were used to offset the z vector so that it points to each pixel as it is being processed.  (See attachment.)  If the logic is wrong then I have 2 problems since the program is working fine.

Thanks.

Linkback: https://fractalforums.org/index.php?topic=4520.0

Offline youhn

  • Fractal Furball
  • ***
  • Posts: 231
  • Shapes only exist in your head
Re: The constant in f(z) = z^2 + c
« Reply #1 on: December 02, 2021, 08:37:14 AM »
How do you mean different? The only minor detail I can spot is the difference is sign + vs - on deltaQ. This just flips the Y direction, that's all.

Offline lycium

  • Strange Attractor
  • ******
  • Posts: 86
    • deviantArt profile
Re: The constant in f(z) = z^2 + c
« Reply #2 on: December 02, 2021, 08:37:24 AM »
Did a quick google of that book and yep, it's from the 80s. I sincerely think learning from this book is a bad idea and will ingrain a bunch of bad habits.

About your source snippet, a few things spring to mind:

1. The style of coding where you try to declare as few variables as possible and reuse them as much as possible is super, super bad. Declaring new variables doesn't equate to using more storage or slower code, and in fact you usually get faster code this way, besides not driving yourself nuts with the spaghetti code ("is this the new x value or the old one?"). Unless you truly need to modify state, you should be using const variables basically everywhere. Even though I've been programming basically my whole life and the inner loop is 5 lines long, I can't easily tell if it's correct because of the reuse of the x and y variables.

2. CPUs have been getting faster faster than memory has been getting faster, so a lot of the old ways of precomputing stuff not only don't help, but usually make things worse / slower / more buggy (more state to keep track of etc). Basically, those arrays need to go.

3. The way those arrays are computed, incrementally based on the previous value in the array, is numerically gross (values later in the array are much less accurate than ones in the beginning, due to cumulative roundoff).

4. All this stateful stuff prevents you from putting a single line above the inner loops to make it parallel, which is basically the most important thing you can do for performance these days.

In summary, since Mandelbrot/Julia rendering is so trivial, just nuke all that code and do it again in a nice functional programming style: compute everything needed on the spot in the inner loops, don't use any extra buffers etc, make as many variables const as possible, and then stick a "#pragma omp parallel for" at the top and watch it fly.

Also, if you'd like to chat about fractal coding stuff feel free to join our great community on Discord: https://discord.gg/V2QnCaBJdx

Offline DanKje

  • Fractal Phenom
  • ****
  • Posts: 53
Re: The constant in f(z) = z^2 + c
« Reply #3 on: December 02, 2021, 09:05:16 AM »
How do you mean different? The only minor detail I can spot is the difference is sign + vs - on deltaQ. This just flips the Y direction, that's all.

I mean pArray[0] = mbRegion.getXMin();
but qArray[0] = mbRegion.getYMax();

So if pArray starts with XMin (as I would expect), why doesn't qArray start with YMin?


Thank you @lycium, your suggestions sound exciting and I will try to learn from them.  Much has changed since I worked in the industry.

Offline marcm200

  • 3e
  • *****
  • Posts: 1107
Re: The constant in f(z) = z^2 + c
« Reply #4 on: December 02, 2021, 02:31:31 PM »
So if pArray starts with XMin (as I would expect), why doesn't qArray start with YMin?
That's purely arbitrary. The pArray depicts the screen from left (min) to right (max), the qArray from max down to min (its definition is qArray[row-1] - deltaQ. You could as well start with min and then use the same code line as for pArray, i.e. +deltaQ. That would flip the set on the x-axis.

The reason might just be that some software starts an image at 0,0 at the lower left corner, for some (0,0) is the upper left.

Note, the use of an array to store the seed values is quite costly in terms of memory. If you compute a large Mset, you quickly need gigabytes. Here I would recommend not storing the values and rather compute them over and over, as it's only 2 muls and 2 adds, and for nested loops, say outer loop col, inner loop row, it's only the inner loop's constant value (p or q) that needs to be computed repeatedly. And for nowadays' computers a few million double multiplications is nothing, especially not when comparing to the billions of operations inside the while-iteration loop.

That was different in the 80s though as lycium mentioned.


Offline DanKje

  • Fractal Phenom
  • ****
  • Posts: 53
Re: The constant in f(z) = z^2 + c
« Reply #5 on: December 03, 2021, 07:59:06 AM »
Well, I think I found the issue and I must reiterate my first statement here, that I’m just a babe in the MB woods. It is also apparent that I am behind the times in terms of modern computing. I fear my level of knowledge may not lie within the scope of this forum.
 
The way q array was being loaded did invert the y axis. However, by assuming the book was right and by incorrectly thinking that I had to move the origin from Java’s upper left to the traditional lower left, I inverted the y-axis a second time. Both I and the book (as it applied to my code) were wrong, the errors canceled each other out, and everything seemed fine. Except for that q array, which always bothered me. At least now I know why, and my code is in a little better shape.

Thanks again for your suggestions, I will pursue them.
« Last Edit: December 03, 2021, 09:35:31 AM by DanKje »

Offline hobold

  • Fractal Frankfurter
  • *
  • Posts: 531
Re: The constant in f(z) = z^2 + c
« Reply #6 on: December 03, 2021, 10:30:04 AM »
Programming for performance is a tricky thing. Processors and compilers have changed a lot over time, as did programming languages, runtime environments and operating systems.

IMHO the best starting point is to write programs for clarity and simplicity of expression.

It is true that not thinking about speed can lead one to write really slow code. But it also remains true that "premature optimization is the root of all evil", as computer science legend Donald E. Knuth pointedly joked.

In my experience, there is no single recipe for high performance programs. I have always had to go though all the steps repeatedly:

1. write a prototype
2. measure/profile where it spends/wastes its time
3. understand why it is slow there
4. improve those bottlenecks
5. success! - followed by the realization that I should have architected the program differently from the start
6. go to 1

Then there is the can of worms in the question "how much optimization does it need?", especially in commercial software development. The only advice I can give here is to ask yourself: who is waiting for the computer? If everybody is waiting, then optimization is definitely worth it. If nobody is waiting, then maybe users are avoiding the functionality like the plague, because it is unusably slow? In the latter case, performance optimization can turn your program from an unknown competitor into the king of the hill.

Offline Alef

  • Fractal Frogurt
  • ******
  • Posts: 480
  • a catalisator / z=z*sinh(z)-c^2
    • My deviant art page
Re: The constant in f(z) = z^2 + c
« Reply #7 on: December 03, 2021, 07:41:18 PM »
I guess it depends on objectives, some have just private soft ! for_a_public. I think some modularity planned at the start is the best, so that parts could be easily improved || added. Alsou most of the books on fractals seems to be rather outdated pushing up same stuff.
« Last Edit: December 04, 2021, 01:49:10 AM by Alef »
by Edgar Malinovsky aka Edgars Malinovskis.