{"id":904,"date":"2009-07-28T16:00:56","date_gmt":"2009-07-29T00:00:56","guid":{"rendered":"https:\/\/www.reenigne.org\/blog\/?p=904"},"modified":"2018-05-12T17:44:20","modified_gmt":"2018-05-12T16:44:20","slug":"algorithm-for-mandelbrot-cardioid","status":"publish","type":"post","link":"https:\/\/www.reenigne.org\/blog\/algorithm-for-mandelbrot-cardioid\/","title":{"rendered":"Algorithm for Mandelbrot cardioid"},"content":{"rendered":"<p>A good way to speed up a Mandelbrot set plotter is to eliminate the main cardioid and the largest circle. It turns out that there are simple equations for these, which can be found if you know that the cardioid consists of all the points which converge to a single point and the largest circle consists of all the points which converge to a cycle of period 2.<\/p>\n<p>First the main cardioid. For each c, we can find the fixed point of iteration <img src='https:\/\/s0.wp.com\/latex.php?latex=z_f&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='z_f' title='z_f' class='latex' \/> such that <img src='https:\/\/s0.wp.com\/latex.php?latex=z_f%5E2%2Bc+%3D+z_f&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='z_f^2+c = z_f' title='z_f^2+c = z_f' class='latex' \/>. There are two solutions, <img src='https:\/\/s0.wp.com\/latex.php?latex=%5Cdisplaystyle+%5Cfrac%7B1%7D%7B2%7D%281+%5Cpm+%5Csqrt%7B1-4c%7D%29&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='\\displaystyle \\frac{1}{2}(1 \\pm \\sqrt{1-4c})' title='\\displaystyle \\frac{1}{2}(1 \\pm \\sqrt{1-4c})' class='latex' \/>. Then we can look at what happens when we iterate a nearby point <img src='https:\/\/s0.wp.com\/latex.php?latex=%28z_f%2Bd%29%5E2%2Bc+%3D+z_f%5E2%2Bc+%2B+2dz_f&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='(z_f+d)^2+c = z_f^2+c + 2dz_f' title='(z_f+d)^2+c = z_f^2+c + 2dz_f' class='latex' \/>. If <img src='https:\/\/s0.wp.com\/latex.php?latex=%7C2z_f%7C+%3C+1&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='|2z_f| &lt; 1' title='|2z_f| &lt; 1' class='latex' \/> then the fixed point is stable. It turns out that this only happens for the <img src='https:\/\/s0.wp.com\/latex.php?latex=%5Cdisplaystyle+%5Cfrac%7B1%7D%7B2%7D%281+-+%5Csqrt%7B1-4c%7D%29&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='\\displaystyle \\frac{1}{2}(1 - \\sqrt{1-4c})' title='\\displaystyle \\frac{1}{2}(1 - \\sqrt{1-4c})' class='latex' \/> solution, so points in the cardioid are <img src='https:\/\/s0.wp.com\/latex.php?latex=%7C1+-+%5Csqrt%7B1-4c%7D%7C+%3C%3D+1&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='|1 - \\sqrt{1-4c}| &lt;= 1' title='|1 - \\sqrt{1-4c}| &lt;= 1' class='latex' \/>, with equality for the boundary.<\/p>\n<p>Having to compute a complex square root is a bit ugly, though - can we do better? It turns out that we can. It's a fiddly calculation but if you multiply out all the square roots and simplify, you can get the formula <img src='https:\/\/s0.wp.com\/latex.php?latex=%7Cc%7C%5E2%288%7Cc%7C%5E2-3%29+%3C%3D+3%2F32+-+Re%28c%29&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='|c|^2(8|c|^2-3) &lt;= 3\/32 - Re(c)' title='|c|^2(8|c|^2-3) &lt;= 3\/32 - Re(c)' class='latex' \/>.<\/p>\n<p>For the period-2 circle, we solve <img src='https:\/\/s0.wp.com\/latex.php?latex=%28z_f%5E2%2Bc%29%5E2%2Bc+%3D+z_f&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='(z_f^2+c)^2+c = z_f' title='(z_f^2+c)^2+c = z_f' class='latex' \/> and eliminate the period-1 solutions to get <img src='https:\/\/s0.wp.com\/latex.php?latex=%5Cdisplaystyle+%5Cfrac%7B1%7D%7B2%7D%28-1+%5Cpm+%5Csqrt%7B-3-4c%7D%29&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='\\displaystyle \\frac{1}{2}(-1 \\pm \\sqrt{-3-4c})' title='\\displaystyle \\frac{1}{2}(-1 \\pm \\sqrt{-3-4c})' class='latex' \/>. In this case, both solutions are equally valid, since the cycle consists of both. Picking one and doing the same derivative analysis (this time applying two iterations) gives us the circle with center at -1 and radius 1\/4.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>A good way to speed up a Mandelbrot set plotter is to eliminate the main cardioid and the largest circle. It turns out that there are simple equations for these, which can be found if you know that the cardioid consists of all the points which converge to a single point and the largest circle [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[18],"tags":[],"class_list":["post-904","post","type-post","status-publish","format-standard","hentry","category-fractals"],"_links":{"self":[{"href":"https:\/\/www.reenigne.org\/blog\/wp-json\/wp\/v2\/posts\/904","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.reenigne.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.reenigne.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.reenigne.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.reenigne.org\/blog\/wp-json\/wp\/v2\/comments?post=904"}],"version-history":[{"count":6,"href":"https:\/\/www.reenigne.org\/blog\/wp-json\/wp\/v2\/posts\/904\/revisions"}],"predecessor-version":[{"id":2101,"href":"https:\/\/www.reenigne.org\/blog\/wp-json\/wp\/v2\/posts\/904\/revisions\/2101"}],"wp:attachment":[{"href":"https:\/\/www.reenigne.org\/blog\/wp-json\/wp\/v2\/media?parent=904"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.reenigne.org\/blog\/wp-json\/wp\/v2\/categories?post=904"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.reenigne.org\/blog\/wp-json\/wp\/v2\/tags?post=904"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}