Erlang e frattali: fuga verso l’infinito…

Nello scorso articolo, tramite poche righe di codice perl, abbiamo curiosato all’interno del frastagliato universo frattale, rappresentando gli insiemi di Mandelbrot e Julia in modalità rigorosamente monocromatica.

Mandelbrot, I: 40 Z: -2.5, 1.0 x -1.0, 1.0

E’ davvero meraviglioso quando la natura ci sorprende facendo coesistere l’infinitamente semplice con lo smisuratamente complesso come in questo caso. Solo Lei può permettersi di farlo in modo così raffinato ed esuberante: una banale successione quadratica nel dominio dei numeri complessi, apparentemente insignificante ed innocua, è in grado di generare ricorsivamente “uno dei più complessi oggetti della matematica”; così è stato definito l’insieme di Mandelbrot da Benoît MandelbrotHeinz-Otto Peitgen e John H. Hubbard suoi iniziali divulgatori.

Il comportamento dei sistemi caotici ha ancora misteriose proprietà che l’uomo non è stato ancora in grado di decifrare; mattoncini matematici che la natura ha combinato per la costruzione dell’universo e di cui – forse – potremmo parlare nei prossimi articoli.

Erlang e frattali

In questo articolo, ho deciso di realizzare un’applicazione distribuita per la rappresentazione in Erlang degli insiemi frattali di Mandelbrot e Julia in Erlang introducendo anche i colori.

Mandelbrot, I: 500 Z: -0.981,-0.6457 x 0.0169, 0.3527

Un bel frullato di: caos, frattali, colori, concorrenza, programmazione funzionale, emozioni, infinito. Una frizzante e fatale alchimia di argomenti dalla quale non è possibile esser risucchiati!

Erlang

L’Erlang è un linguaggio funzionale progettato da Joe Armstrong, per conto di Ericsson, con lo scopo di favorire lo sviluppo di applicazioni: distribuite, soft-realtime, con un elevato grado di concorrenza ed affidabilità nel campo delle telecomunicazioni. La prima versione proprietaria del linguaggio è stata rilasciata internamente nel 1986 mentre, dopo varie vicessitudini, nel 1998 Erlang è stato distribuito opensource.

Concorrenza e gestione dei processi

The world is concurrent
Things in the world don’t share data
Things communicate with messages
Things fail – Joe Armstrong

Erlang è progettato per la concorrenza massiva. Per spingere tale caratteristica a livelli estremi, si è ben pensato di progettare un gestore di processi ed uno scheduler interni alla virtual-machine. Tali componenti non delegano i loro compiti al kernel del sistema operativo (come fa la quasi totalità degli altri linguaggi) e sono in grado di gestire processi con un’efficientissima gestione della memoria e dello scheduling.

Julia, I: 150 K: -0.835+0.2321i Z: -1.8,1.8 x -1.0, 1.0

Scrivere applicazioni distribuite, scalabili e robuste in Erlang è normalmente più semplice che in altri linguaggi. I processi possono esser distribuiti trasparentemente su più core oppure su più macchine e comunicano tramite message-passing asincrono.

Apprendere l’Erlang

Se siete semplicemente curiosi di conoscere la sintassi del linguaggio, potreste provare questo breve tutorial online che simula via web la shell di Erlang: Tryerlang.

Per un corso online è possibile visitare: Learn You Some Erlang oppure Erlang for Skeptics

I libri che non possono mancare nella biblioteca di chi ama tale linguaggio (sui quali ho studiato l’Erlang):

Applicazione Erlang: frk

Segue il codice sorgente in Erlang, del modulo principale, che ho scritto per la mia applicazione: frk.

-module(frk).
-author('LucaAmore').
-export([save/11, save/9, julia/9, mandelbrot/7]).

%------------------------------------------------------------------------
%    Copyright (C) 2011 Luca Amore <luca.amore at gmail.com>
%------------------------------------------------------------------------

% extract all screen coords
screen(W, H)->
    [ {X,Y} || Y <- lists:seq(0, H - 1), X <- lists:seq(0, W - 1) ].

% convert bitmap point to complex point
complex(X, Y, MinX, MinY, FactX, FactY)->
    { MinX + X * FactX, MinY + Y * FactY }.

iterate(_, _, _, _, MaxIterations, Iterations) 
    when Iterations >= MaxIterations -> Iterations;

iterate(Zre, Zim, _, _,  _, Iterations) 
    when Zre * Zre + Zim * Zim  > 4 -> Iterations;

iterate(Zre, Zim, Cre, Cim, MaxIterations, Iterations)->
    iterate(
        Zre * Zre - Zim * Zim + Cre, 
        2 * Zre * Zim + Cim, 
        Cre, Cim,
        MaxIterations, Iterations+1
    ).

%------------------------------------------------------------------------
% Julia's set
%
% Z1 = C0, Zn+1 = Zn^2 + K
%------------------------------------------------------------------------
julia(X, Y, MinX, MinY, FactX, FactY, Kre, Kim, MaxIterations)->
    {Cre, Cim} = complex(X, Y, MinX, MinY, FactX, FactY),
    iterate(Cre, Cim, Kre, Kim, MaxIterations, 0).

%------------------------------------------------------------------------
% Mandelbrot's set
%
% Z1 = 0, Zn+1 = Zn^2 + C0
%------------------------------------------------------------------------
mandelbrot(X, Y, MinX, MinY, FactX, FactY, MaxIterations)->
    {Cre, Cim} = complex(X, Y, MinX, MinY, FactX, FactY),
    iterate(0, 0, Cre, Cim, MaxIterations, 0).

% Julia's set exploration
generate(julia, W, H, MinX, MaxX, MinY, MaxY, Kre, Kim, MaxIterations) 
    when W > 0, H > 0, MaxX > MinX, MaxY > MinY, MaxIterations > 0 ->
    FactX = (MaxX - MinX) / W,
    FactY = (MaxY - MinY) / H,
    [ julia(X, Y, MinX, MinY, FactX, FactY, Kre, Kim, MaxIterations) || 
        {X, Y} <- screen(W, H) ].

% Mandelbrot's set exploration
generate(mandelbrot, W, H, MinX, MaxX, MinY, MaxY, MaxIterations) 
    when W > 0, H > 0, MaxX > MinX, MaxY > MinY, MaxIterations > 0 ->
    FactX = (MaxX - MinX) / W,
    FactY = (MaxY - MinY) / H,
    [ mandelbrot(X, Y, MinX, MinY, FactX, FactY, MaxIterations) || 
        {X, Y} <- screen(W, H) ].

% save Julia's set in ppm format
save(julia, W, H, MinX, MaxX, MinY, MaxY, Kre, Kim, MaxIterations, FileName) 
    when W > 0, H > 0, MaxX > MinX, MaxY > MinY, MaxIterations > 0 ->
    M = [
            paletteblu:color(Iterations, MaxIterations) || 
                Iterations <- generate(
                    julia, W, H, MinX, MaxX, MinY, MaxY, Kre, Kim, MaxIterations
                )
    ],
    ppm:save(image, W, H, 255, FileName, M).

% save Mandelbrot's set in ppm format
save(mandelbrot, W, H, MinX, MaxX, MinY, MaxY, MaxIterations, FileName) 
    when W > 0, H > 0, MaxX > MinX, MaxY > MinY, MaxIterations > 0 ->
    M = [
            palettered:color(Iterations, MaxIterations) || 
                Iterations <- generate(
                    mandelbrot, W, H, MinX, MaxX, MinY, MaxY, MaxIterations
                )
    ],
    ppm:save(image, W, H, 255, FileName, M).

Mandelbrot, I: 40 Z: -1.825,-1.705 x -0.06, 0.06

Per non appesantire troppo il codice ho deciso di utilizzare come formato delle immagini di output PPM (tra i più semplici disponibili) e poi convertirlo in PNG, tramite script bash, utilizzando l’utility convert di ImageMagick.

Tutte le immagini dei frattali di questo articolo sono stati generati da frk.

L’applicazione frk. rilasciata come software libero sotto licenza GNU/GPL, è disponibile presso:

Repository GIT su GITHUB di FRK

Rappresentazione dell’insieme frattale di Mandelbrot in Perl

Mandelbrot

La rappresentazione dell’insieme di Mandelbrot, considerato uno dei frattali più popolari, è tra i miei algoritmi di prova preferiti quando studio un nuovo linguaggio di programmazione.

L’algoritmo di base è estremamente semplice e si presta facilmente ad esser parallelizzato.

Recentemente, all’interno dei Google Labs, è stata rilasciata un’applicazione Web che, sfruttando le API di Google Maps e canvas di HTML5, permette la navigazione all’interno dell’insieme di Mandelbrot o di altri frattali (es. Julia); vi consiglio di utilizzarla per un tour veloce.

Definizione formale

L’insieme di Mandelbrot è definito come il sottoinsime del piano complesso per cui la successione ricorsiva:

  P^c_n=  \begin{cases}  & Z_0=0  \\  & Z_{n+1}=Z_n^2+c  \end{cases}

 

al tendere di n all’infinito, rimane limitata nel suo modulo, ovvero:

  M=\left\{c\in \mathbb{C} : \exists s \in \mathbb{R}, \forall n \in \mathbb{N},|P_n^c| \leq s \right\}

 

Sorgente perl

Ecco un sorgente perl che rappresenta l’insieme in modalità rigorosamente monocromatica:

#!/usr/bin/perl

##########################
# M A N D E L B R O T
# Luca Amore
##########################

use strict;
use warnings;

use GD;

my $FILENAME = 'mandelbrot.png';
my $ITERATIONS = 30;
my ($SIZEX, $SIZEY) = (700, 400);
my ($RE_MIN, $RE_MAX) = (-2.5, 1.0);
my ($IM_MIN, $IM_MAX) = (-1.0, 1.0);

my $re_factor = ($RE_MAX - $RE_MIN) / $SIZEX;
my $im_factor = ($IM_MAX - $IM_MIN) / $SIZEY;

my $img = new GD::Image->newTrueColor($SIZEX,$SIZEY)
    or die "Can't create GD::Image";

# palette
my $cl_black = $img->colorAllocate(  0,  0,  0);
my $cl_white = $img->colorAllocate(255,255,255);

open(my $fh, '>', $FILENAME) 
    or die "Can't open $FILENAME: $!";

binmode $fh;

my $C_im = $IM_MIN;

YY: for (my $yy=0; $yy < $SIZEY; $yy++){
   
    my $C_re = $RE_MIN;

    XX: for (my $xx=0; $xx < $SIZEX; $xx++){
    
        my ($Z_re, $Z_im, $i) = (0,0);

        # Z0=0, Zn+1 = Zn^2 + C
        ESCAPE_ITERATIONS: for ($i = 1; $i<$ITERATIONS; $i++){

            my ($Z_re2, $Z_im2) = ($Z_re * $Z_re, $Z_im * $Z_im);

            last ESCAPE_ITERATIONS unless ($Z_re2 + $Z_im2 < 4);

            # (a+bi)^2 = a^2 + 2abi - b^2
            $Z_im = 2 * $Z_re * $Z_im + $C_im;
            $Z_re = $Z_re2 - $Z_im2 + $C_re;

        } # end: ESCAPE_ITERATIONS

        # draw pixel
        $img->setPixel(
            $xx, $yy, $i == $ITERATIONS ? $cl_black : $cl_white
        );

        $C_re += $re_factor;

    } # end: XX

    $C_im += $im_factor;

} # end: YY

# save image
print $fh $img->png(0);
close $fh;

Il codice è stato mantenuto semplice per facilitare le modifiche e la comprensione.

E’ richiesto il package GD per la produzione dell’immagine di output in formato PNG: “mandelbrot.png“.

mandelbrot.png generato dal sorgente perl

 

Colori

Normalmente, per rendere tale frattale più gradevole, nella sua rappresentazione più semplice, si colorano i punti esterni all’insieme in funzione della velocità con la quale divergono a più infinito. Per la colorazione dei punti interni ed esterni esistono una miriade di algoritmi di complessità crescente; alcuni spunti interessanti.

Insieme di Julia

Una variante dell’insieme di Mandelbrot è l’insieme di Julia definito in questo modo:

  Q_n^K(c)=  \begin{cases}  & Z_0=c  \\  & Z_{n+1}=Z_n^2+K  \end{cases}

 

Rispetto all’insieme di Mandelbrot cambia la successione ricorsiva ed è stata introdotta una costante complessa K.

Analogamente a Mandelbrot i punti appartenenti all’insieme di Julia sono quelli per cui il modulo della successione ricorsiva non diverge.

  J=\left\{c\in \mathbb{C} : \exists s \in \mathbb{R}, \forall n \in \mathbb{N},|Q_n^K(c)| \leq s \right\}

 

Alcuni valori di K che si consiglia di esplorare:

  • K = 0.353+0.288i
  • K = -0.70176-0.3842i
  • K = -0.835-0.2321i
  • K= -0.45+0.1428i

Dopo aver adeguato lo script perl, ho rappresentato questi insiemi di Julia:

Insieme di Julia (K=0.353+0.288i)

    Insieme di Julia (K=-0.835-0.2321i)

    Riferimenti

    Mandelbrot Set – Wikipedia
    Mu-Ency – The Encyclopedia of the Mandelbrot Set
    The Mandelbrot Set (algoritmo tracciamento)
    Julia Set – Wikipedia

    Esplorazione

    Visual Guide To Patterns In The Mandelbrot SetMandelbrot: World Map and Popular Tourist Areas