{"id":4047,"date":"2017-06-27T10:24:58","date_gmt":"2017-06-27T10:24:58","guid":{"rendered":"http:\/\/stratio.com\/?p=4047"},"modified":"2023-09-20T13:33:04","modified_gmt":"2023-09-20T13:33:04","slug":"sparkart-part-one","status":"publish","type":"post","link":"https:\/\/www.stratio.com\/blog\/sparkart-part-one\/","title":{"rendered":"SparkArt! Part One: Exploring the depths of Mandelbrot Set with Spark"},"content":{"rendered":"

On March the 26th 2012, James Cameron and\u00a0his submarine craft, Deepsea Challenger, explored the depths of the ocean down to 11km under sea level at\u00a011.329903\u00b0N 142.199305\u00b0E, an infinitesimal point on the surface of the Earth’s vast Oceans. Could you imagine how incredible it would be to\u00a0have thousands of “Deep Challengers” reaching the bottom of our planet in parallel? What a map we would get!<\/p>\n\n\n\n
\n

James Cameron’s trip<\/figcaption><\/figure><\/th>\n
\n

Distributed sea exploration<\/figcaption><\/figure><\/th>\n<\/tr>\n<\/tbody>\n<\/table>\n

Throughout the lines of this post we’ll see how such a feat is possible, just let me replace the\u00a0Earth’s Oceans with\u00a0The Mandelbrot Set<\/a>\u00a0and\u00a0thousands of “Deepsea Challengers<\/a>”\u00a0by\u00a0Hundreds of distributed execution units. Yes! We will see how it is possible to draw\u00a0HUGE<\/strong>\u00a02D representations of this beautiful fractal using the distributed computational power which only\u00a0Apache Spark can provide.<\/p>\n

What is this fractal about?<\/h2>\n

As the reader surely knows, fractals are self-repetitive physical or abstract structures such as geometric figures generated\u00a0by repeating their dominant\u00a0features as they get zoomed in on.<\/p>\n

The Mandelbrot set is a set of complex numbers whose 2D representation shows the self-replication property of fractals. This representation consist of\u00a0drawing the points belonging to the complex set in a 2D plane using a given color, let’s use\u00a0black<\/strong>, and the points not on the set with a different color, we’ll see which one (or rather which color palette) soon.<\/p>\n

Drawing figures with complex numbers<\/h2>\n

2D complex number representation is as simple as using the real part as the value for the x-axis value and the imaginary part as a value in the y-axis. e.g: The complex value\u00a0-1+2i<\/strong>\u00a0could be represented as:<\/p>\n

-1+2i complex number 2D representation<\/figcaption><\/figure>\n

Thus a set of infinite points cover a surface, potentially forming a geometric figure, e.g:<\/p>\n

A random complex set representation<\/figcaption><\/figure>\n

As we can’t handle an infinite number of points, the resolution of the surface would be given by the number of points in the set, the more you have, the less porous the painted surface is.<\/p>\n

So, yes, it is possible to draw things by just providing a set of complex numbers. And The Mandelbrot set is a complex set, this has been known for ages by now. See this\u00a0example of a representation created by a primitive computer in\u00a01989:<\/p>\n

The Emperor’s new mind – Pg 98 – Roger Penrose 1989<\/figcaption><\/figure>\n

So it is done, why Spark?<\/h2>\n

There you go, \u00a0a single 1989 computer was already able to draw a representation of the set so that’s all, end of the post. I hope you enjoyed it…<\/p>\n

Just kidding! The problem with the figure above is that it is so coarse , so zoomed out that you don’t see anything beyond a kind of bug, maybe some kind of\u00a0Rorschach test<\/a>\u00a0, nothing of apparent interest.\u00a0The ancient computer is to blame in this case. it couldn’t provide a large enough set to represent the nuances of the details hidden behind this black blob. Lets jump 30 years in the future and see what Spark can provide given the same mathematical description:<\/p>\n

The Mandelbrot set representation using Apache Spark<\/figcaption><\/figure>\n

Hey! those strange branches aren’t a anything else than the figure itself!<\/p>\n

Better resolution. more insight. The blur was hiding\u00a0features.<\/figcaption><\/figure>\n

This is an improvement for sure! But, believe me, you could have generated this “high resolution” image with a cheap PC in less than a minute. We haven’t discussed the details of the algorithm yet but, I promise you, there is no need to use\u00a0the power of distributed computation\u00a0<\/strong>to create this representation.<\/p>\n

An infinite universe to explore<\/h2>\n

The colourful representation shown above is yet small just 1MP (Mega Pixel). However, the points in the complex set are infinite, meaning that you could keep zooming in and calculating whether or not the, each time more infinitesimal, points of the 2D plane fall inside or\u00a0outside the set. To paint them in black, if they fall inside, or in another color if not. No, there is nothing wrong with your screen\u00a0nor with your perception (at least regarding this): All of a sudden we have colors! Let’s ignore them and\u00a0keep in mind that the black dots are those representing complex numbers within the Mandelbrot Set.<\/strong><\/p>\n

A good analogy here are black holes, everything within their event horizon is not there to see: It is black, the information around it is what we can actually see in a colorful fashion.<\/p>\n

So, before explaining how, let’s take a look at the result of using\u00a0distributed computation with\u00a0Apache Spark to compute a\u00a0ONE TERAPIXEL REPRESENTATION OF THE MANDELBROT SET<\/a>.<\/span><\/strong><\/p>\n

Don‘<\/b>t be shy, enter and explore yourself. In any case, you can find an example in the following video:<\/p>\n

Is in these extremely huge cases where more computational power is needed, where we can harness the potential of distributed systems to reach levels of detail hardly imaginable\u00a0for a single computer.<\/p>\n

Colors, unveiling the algorithm<\/h2>\n

So far, we’ve just discussed what this is all about and seen the results of this experiment, now it’s time to start digging right into how this huge, but limited at the same time, snapshot of an infinite universe can be generated.<\/p>\n

We can\u00a0ignore distribution, parallelization and fancy computation accelerators for now and center our attention in the classical sequential algorithm. As we have discussed by now, the idea is to map complex values onto an area on a 2D plane, let’s refer to that rectangular region as our canvas. To map these complex numbers, first we have to find them.<\/p>\n

For that, we will sample the 2D plane, that is an interval of complex numbers, and check which elements of the sample fall into the set. A relatively simple algorithm to test whether or not a complex number is part of the set\u00a0is the\u00a0Escape Time Algorithm<\/a>\u00a0. Without getting into the mathematical details (which are better explained at Wikipedia\u00a0than by\u00a0any attempt of me to bring them to this TLDR post) the idea is:<\/p>\n

    \n
  1. Take\u00a0z = 0<\/strong>\u00a0as starting value.<\/li>\n
  2. Take as\u00a0c<\/strong>\u00a0the complex value whose belonging to the set we want to check.<\/li>\n
  3. Compute the result of the (tail) recursive function:\n
    \/\/ Not the actual implementation, a quick draft to illustrate the idea.\ndef f(z: Complex, c: Complex): Boolean = {\n    if(modulus(z) > 4.0) false \/* ESCAPED THE RECURSION!\n                                  c wasn't part of the set *\/\n    else f(z*z + c)\n}<\/pre>\n<\/li>\n<\/ol>\n
    If we run the snippet from above.\u00a0We have two options: Keep our computer running until the end of the universe or change\u00a0f\u00a0<\/strong>to stop iterating at a certain number of iterations. The points in the set are guaranteed to not make\u00a0z^2+c\u00a0<\/strong>diverge therefore, by definition, \u00a0f(Complex.Zero, cInput)<\/span>\u00a0should indefinitely call to itself.\u00a0\u00a0Thus, the function should be changed to include some kind of limit:<\/p>\n
    \/\/ Not the actual implementation, a quick draft to give you an idea.\ndef f(z: Complex, c: Complex)(maxIterations: Int): Boolean = {\n    if(modulus(z) > 4.0) false \/* ESCAPED THE RECURSION!\n                                  c wasn't part of the set *\/\n    else if(maxIterations == 0) true\n    else f(z*z + c)(maxIterations-1)\n}<\/pre>\n
    And this way, we’ve transformed the algorithm into an approximation algorithm where the accuracy\u00a0of its results increase as the initial limit of iterations increases. That is, the probability of getting false positives (wrongly acknowledging values as belonging to the set) increases as\u00a0\u00a0maxIterations<\/span>\u00a0gets reduced, sadly for us, the bigger this limit is, the slower the algorithm is.<\/p>\n
    Having to constraint the number of iterations is a toll we’ve to pay if we want to get our results in a reasonable time. Nevertheless, it has a silver lining, a cool feature which bestows our representation with colourful contours. What if, due to the points not belonging to the set and therefore escaping before reaching the limit, we returned the number of iterations it took to diverge?<\/p>\n
    \/\/ Not the actual implementation, a quick draft to make an idea.\ndef f(z: Complex, c: Complex)(\n    maxIterations: Int,\n    currentIteration: Int = 0\n): Option[Int] = {\n    if(modulus(z) > 4.0) Some(currentIteration)\n                               \/* ESCAPED THE RECURSION!\n                                  c wasn't part of the set, that is now\n                                  represented by returning Some(noIterations)\n                                *\/\n    else if(currentIteraton == maxIterations) None \/* Reached the limit, not interested \n                                                      in the number of iterations as \n                                                      the function didn't escape *\/\n    else f(z*z + c)(maxIterations, currentIteration+1)\n}\n\nval explorationResult: Option[Int] = f(Complex.Zero, Complex(x, y))(1000)\nval inMandelbrotSet: Boolean = explorationResult.isEmpty\n\n\/* The number of iterations for escaped values can be used\n   to give color to the complement set of Mandelbrot set *\/\n\nval palette: Vector[Color] = ???\n\nval color = explorationResult map { n => \n    palette(n % palette.size)\n} getOrElse Black\n<\/pre>\n
    This algorithm produces nice results for small\u00a0samples or small limits to the number of iterations, you can find a single threaded implementation which can be run in your very own browser at\u00a0https:\/\/github.com\/pfcoperez\/mandelbrot_scalajs<\/a>, it is in\u00a0this experiment repository as well<\/a>, implemented without notions of parallelization. We are about to discover that it can be used in a parallel computation just as it is, no changes required:<\/p>\n
    package org.pfcoperez.iterativegen\n\nobject MandelbrotSet {\n\n  \/** A single iteration of the numeric method\n    *  O(1)\n    *\n    * @return `None` if the point escapes the set,\n    *         `Some(new complex state)` otherwise.\n    *\/\n  def iteration(\n                 zeroth: (Double, Double)\n               )(\n                 xy: (Double, Double)\n               ): Option[(Double, Double)] = {\n    val (x, y) = xy\n    val (x0, y0) = zeroth\n\n    if(x*x + y*y >= 4.0) None\n    else Some((x*x - y*y + x0, 2.0*x*y+y0))\n  }\n\n  \/** Several iterations, it can be used to approximate\n    *  Mandelbrot's set. The more iterations,the better\n    *  the approximation is.\n    *\n    * O(nIterations)\n    *\n    * @zeroth Start point, e.g: (x,y) \\in ([-2.5, 1], [-1,1]) area.\n    * @nIterations Max depth to be check in the recursion.\n    * @prevSt Starting point in the expliration\n    * @return The state after `nIterations` or condition escape.\n    *\n    *\/\n  def numericExploration(\n                          zeroth: (Double, Double),\n                          nIterations: Int,\n                          prevSt: Option[((Double, Double), Int)] = None\n                        ): (Option[(Double, Double)], Int) = {\n\n    val (prevPoint, prevIterations) = prevSt.getOrElse((0.0, 0.0) -> 0)\n\n    def numericExploration(current: (Double, Double), it: Int): (\n      Option[(Double, Double)], Int\n      ) =\n      if(it == nIterations) (Some(current), prevIterations+it)\n      else iteration(zeroth)(current) match {\n        case Some(p) => numericExploration(p, it+1)\n        case _ => (None, prevIterations+it)\n      }\n\n    numericExploration(prevPoint, 0)\n\n  }\n\n}<\/pre>\n
    Explorers Galore!<\/h2>\n
    Coming back to James Cameron’s adventures, given the coordinates of a point on the\u00a0Earth surface, he explored that point by going deeper and deeper with his submarine. This is exactly what we’re doing with our\u00a0Escape Time Algorithm<\/strong>, we set a point in our\u00a0canvas\u00a0<\/strong>and then we descend as deep as the maximum number of iterations determines:<\/p>\n