Re: Memory usage of a Sierpinski triangle algorithm

*To*: mathgroup at smc.vnet.net*Subject*: [mg124143] Re: Memory usage of a Sierpinski triangle algorithm*From*: DrMajorBob <btreat1 at austin.rr.com>*Date*: Wed, 11 Jan 2012 04:19:26 -0500 (EST)*Delivered-to*: l-mathgroup@mail-archive0.wolfram.com*References*: <201201101058.FAA27787@smc.vnet.net>*Reply-to*: drmajorbob at yahoo.com

a) That code uses almost zero memory and doesn't even create a plot. Did you leave out a CALL, perhaps? (I had to guess what size N would be useful.) b) It turns out that N needs to be HUGE... because PointSize is too small. I suggest a larger one. c) Do NOT use N as a variable. It's a built-in function. It's generally best to never start your own variables with capitals, to eliminate conflicts like that. You don't need to display N or P as symbols, so change them to n and p. d) The plot includes the data, so using Module may do very little to minimize memory. e) Evaluate isn't doing anything where you've put it, since its argument isn't held, anyway. f) The first Module has no module variables, which makes Module useless and makes x a global variable. You could write it throwd3[] := Module[{x = Random[]}, If[x < 1/3, y = 1, If[1/3 < x < 2/3, y = 2, y = 3]]; y] or throwd3[] = Module[{x = Random[]}, Piecewise[{{1, x < 1/3}, {2, 1/3 <= x <= 2/3}}, 3]] Either of those would make sense. g) Do you intend to get 3 when x is 1/3 or 2/3 to machine precision? If not, change < to <= accordingly. (It doesn't really matter, since 1/3 and 2/3 occur with 0 probability.) h) startlist[[throwd3[[]]] can be replaced with RandomChoice@startlist, eliminating throwd3 entirely. i) list never changes, but you subscript it with an integer, and store another list in the result??? The result is N different lists, from small to large, giving N (N + 1)/2 total stored pairs, with only N of them distinct... and you plot only the last subscripted list, so the others are useless. I assume this is why memory usage grows so much. j) p also need a subscript either, for similar reasons. k) Here's a working code, including a call: Clear[sierpinski] startlist = {{0, 0}, {1, 0}, {0.5, 1}}; sierpinski[nmax_, x0_: 0.5, y0_: 0.5] := Module[{n = 1, p, list = startlist}, p = {x0, y0}; Do[p = 1/2 (RandomChoice@startlist + p); AppendTo[list, p], {n, nmax}]; ListPlot[list, PlotStyle -> PointSize[0.005], PlotRange -> All]] sierpinski[10000]//Timing (0.603191 seconds) Table instead of Do, eliminating AppendTo, is five times faster: Clear[sierpinski] startlist = {{0, 0}, {1, 0}, {0.5, 1}}; sierpinski[nmax_, x0_: 0.5, y0_: 0.5] := Module[{n = 1, p, list}, list = Join[Append[startlist, p = {x0, y0}], Table[p = 1/2 (RandomChoice@startlist + p), {n, nmax}]]; ListPlot[list, PlotStyle -> PointSize[0.005], PlotRange -> All]] sierpinski[10000] // Timing (0.1222112 seconds) NestList is still faster: Clear[sierpinski] startlist = {{0, 0}, {1, 0}, {0.5, 1}}; sierpinski[nmax_, x0_: 0.5, y0_: 0.5] := Module[{n = 1, p, list}, list = Join[startlist, NestList[(# + RandomChoice@startlist)/2 &, {x0, y0}, nmax]]; ListPlot[list, PlotStyle -> PointSize[0.005], PlotRange -> All]] sierpinski[10000] // Timing (0.079853 seconds) All three codes give pretty much the same plot. Bobby On Tue, 10 Jan 2012 04:58:57 -0600, Wojciech Morawiec <wmorawie at students.uni-mainz.de> wrote: > 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... > > Thanks for any advice in advance! > > -W. > -- DrMajorBob at yahoo.com

**References**:**Memory usage of a Sierpinski triangle algorithm***From:*Wojciech Morawiec <wmorawie@students.uni-mainz.de>