Re: Memory usage of a Sierpinski triangle algorithm

• To: mathgroup at smc.vnet.net
• Subject: [mg124144] Re: Memory usage of a Sierpinski triangle algorithm
• From: Heike Gramberg <heike.gramberg at gmail.com>
• Date: Wed, 11 Jan 2012 04:19:47 -0500 (EST)
• Delivered-to: l-mathgroup@mail-archive0.wolfram.com
• References: <201201101058.FAA27787@smc.vnet.net>

```Every time you set Subscript[P, n] = ..  you're not assigning a value
to P, but you're actually adding an element to the list of down values
of Subscript. Try for example

Clear[Subscript];
DownValues[Subscript]
Sierp[10];
DownValues[Subscript]

Since the new value of P only depends on the current value, you can do
something like
Sierp1[N_, x0_: 0.5, y0_: 0.5] :=
Module[{nmax = N, n, P, list},
P = {x0, y0}; n = 1;
list = startlist;
Do[Evaluate[P = 1/2 (startlist[[RandomInteger[1,3]]] + P)];
list = Append[list, P], {n, nmax}];
ListPlot[list, PlotStyle -> PointSize[0.0001]]]

This performs a bit better than the original one. To do the same thing
in a functional way, you could do something like

Sierp2[N_, x0_: 0.5, y0_: 0.5] := Module[{list},
list = Join[startlist,
NestList[1/2 (RandomChoice[startlist] + #) &, {x0, y0}, N]];
ListPlot[list, PlotStyle -> PointSize[0.0001]]]

The timings I get for these two versions are

Sierp1[10000]; // Timing
Sierp2[10000]; // Timing

out:

{2.5849, Null}
{0.199617, Null}

so the second version is about a factor 13 faster for 20000 iterations.

Heike.

> Cheers!
>
> I began some Mathematica programming exercises recently and I wrote
some simple algorithm to create a list of points that resembles a
Sierpinski triangle when plotted with ListPlot. Basically you choose on
of the three edges by random, create a point in the middle between
{0.5,0.5} and the chosen edge and continue to create new points in the
middle between a randomly chosen edge and the last created point:
>
> ########################### CODE ###########################
> throwd3[] := Module[{}, x = Random[];
>  If[x < 1/3, y = 1, If[1/3 < x < 2/3, y = 2, y = 3]]; y]
>
>
> startlist = {{0, 0}, {1, 0}, {0.5, 1}};
>
>
> Sierp[N_, x0_: 0.5, y0_: 0.5] :=
> Module[{nmax = N, n, P, list}, Subscript[P, 0] = {x0, y0}; n =
1;
>   Subscript[list, 0] = startlist;
>   Do[Evaluate [
>      Subscript[P, n] =
>     1/2 (startlist[[throwd3[]]] + Subscript[P, n - 1])];
>     Subscript[list, n] =
>     Append[Subscript[list, (n - 1)], Subscript[P, n]], {n, nmax}];
>  ListPlot[Subscript[list, nmax], PlotStyle -> PointSize[0.0001]]]
> ########################### END CODE ########################
>
> The thing is that this code uses huge amounts of memory since it
stores all the lists and points needed during the calculations, although
these shouldn't be stored because I'm using a Module, right?
> Obviously, I'm missing something here...
>