Skip to content

Latest commit

 

History

History
136 lines (98 loc) · 3.21 KB

README.md

File metadata and controls

136 lines (98 loc) · 3.21 KB
Raw

Mandelbrot Kata

This a little programming exercise using the fractal domain, in particular the Mandelbrot Set.

Detailed explanations about the Mandelbrot Set can be found here: https://en.wikipedia.org/wiki/Mandelbrot_set

The goals of the kata are:

  • Understand a little bit the mathematical concepts behind fractals.
  • Apply Test-First Programming approach.
  • Improve OO programming skills.

In order to finish the kata you have to draw two versions of the Mandelbrot fractal:

  • ASCII graph: see file mandelbrot-160x160.txt
  • Image (background white and mandelbrot set in black): see file mandelbrot-160x160.png

Math

Basically, there is a mathematical formula for complex number:

f(x) = z² + c

where z and c are complex number.

The Mandelbrot set is the set of complex numbers c for which the function does not diverge when iterated from z=0. Than means, given a c complex number, if you apply the formula to that number n times using the previous result as the new z number, that c belongs to Mandelbrot Set if the sequence does not diverge.

You can represent those complex number in a graph where x-axis is the real part of the complex number and y-axis is the imaginary part.

Drawing the fractal

You have to draw the portion of the graph between -2 and 2 real and imaginary parts. Mandelbrot Set is inside those limits.

Mandelbrot Graph

Prerequisites

PHP

PHP 7.4

Installation

PHP without docker

composer install

PHP with docker

docker build -t php-mandelbrot .
docker run -it --rm \
	-v "$PWD":/usr/src/app \
	-w /usr/src/app \
	-u $(id -u ${USER}):$(id -g ${USER}) \
	php-mandelbrot \
    composer install

Running the tests

PHP without docker

./vendor/bin/phpunit

PHP with docker

docker run -it --rm \
	-v "$PWD":/usr/src/app \
	-w /usr/src/app \
	-u $(id -u ${USER}):$(id -g ${USER}) \
	php-mandelbrot

Execute only one test class

docker run -it --rm \
	-v "$PWD":/usr/src/app \
	-w /usr/src/app \
	-u $(id -u ${USER}):$(id -g ${USER}) \
	php-mandelbrot \
    ./vendor/bin/phpunit --filter 'MandelbrotFormulaShould'

Acknowledgments

Similar projects

Performance

It's very bad. It's not the goal of the project.

For 8192px image:

  • Size: 8192x8192px
  • Iter: 200
  • Decimal precision: 28
  • Time: 179m (2,98h)
  • Performance: 0,17ms/px
  • Min number step: 0,00048828125 (4/8192)

For 16384px image:

  • Size: 16384x16384px
  • Iter: 200
  • Decimal precision: 28
  • Time: 673m (11,21h)
  • Performance: 0,17ms/px
  • Min number step: 0,000244140625 (4/16384)

TODO

Increase performance:

  • Use PHP parallel
  • Symmetry real axis.
  • Mapping from pixel to complex number only for one image corner. Calculate next pixel complex from previous complex number.

More fun:

Arbitrary precision:

  • Test it with numbers greater than PHP float precision.