{"id":2022,"date":"2008-12-04T08:00:06","date_gmt":"2008-12-04T13:00:06","guid":{"rendered":"http:\/\/www.shamusyoung.com\/twentysidedtale\/?p=2022"},"modified":"2009-08-06T14:23:25","modified_gmt":"2009-08-06T18:23:25","slug":"sierpinski-triangle","status":"publish","type":"post","link":"https:\/\/www.shamusyoung.com\/twentysidedtale\/?p=2022","title":{"rendered":"Sierpinski Triangle"},"content":{"rendered":"

When I was about 15 years old, I ran into the following set of directions:<\/p>\n

    \n
  1. Take a piece of paper.\n<\/li>\n
  2. Mark 3 dots on it. They can be anywhere, but for aesthetic reasons it is common to pick three points that will form an equilateral triangle. Number these points 1 through 3.\n<\/li>\n
  3. Get yourself a 3-sided die. (Or use a d6 and divide by 2.)\n<\/li>\n
  4. Begin at one of the corners. This is your “current” position. Roll your d3, to select one of the points. Measure the distance between your current position and the chosen corner and put a dot at the exact halfway point between the two. This is your new current position.\n<\/li>\n
  5. Sit there for a few hours or days repeating step #4: (Your current position moves, pick a corner, move halfway from where you are to the chosen corner, and make a dot, etc.) For best results, use a good ruler and a nice sharp writing instrument.\n<\/li>\n<\/ol>\n

    When I heard this at 15, I expected that what you would end up with is a mass of dots in the middle of the paper, dense in the middle and thinning out towards the edges. This is not what you get at all. In fact, as long as you follow the directions you will never ever place a dot anywhere near the middle of that triangle. What you actually end up with is a Sierpinski Triangle<\/a>:<\/p>\n

    sierpinski.jpg<\/td><\/tr><\/table><\/p>\n

    This was my first exposure to order from chaos, and it fascinated me. It’s a fractal, meaning there is no limit to how much detail the final image can have. No matter how massive your paper is, how fine you make your dots, there will always be yet another level of even smaller triangles beyond the ones you can see at the resolution you’re working with. The Mandelbrot Set<\/a> was the pop star of fractals during the late 80’s, appearing on Trapper Keepers, pencil holders, lunchboxes, and the like. It is indeed an interesting thing, but I was always more awed by Sierpinski Triangle for the incredibly surprising and simplistic method of generating them.<\/p>\n

    Obviously generating Sierpinski Triangles is a job best left for a computer. (Or people with out-of-control obsessive-compulsive disorder.) Which is what made me think of it yesterday<\/a> during our discussion of random number generators. My very first implementation of the Sierpinski Triangle was written in BASIC, using the random number generator that came with the language, and this was the first time I found out what pseudo<\/strong> random was all about. <\/p>\n

    The implementation I wrote had an odd defect: The area around top-most point would get filled in far, far faster than the area around the left or right points. Likewise, the left-most point was filled in faster than the right, which rarely got any dots at all. (Back then computers were so slow and the resolution so coarse that you could see the dots appear at the rate of only a few a second.) I’d leave the room for 15 minutes, and when I came back I’d have an image much like the one above. But during the beginning stages the problem was easy to see: The first point got lots of dots, point #2 got fewer, and point 3 got hardly any at all.<\/p>\n

    It turned out that the random number generator I was using tended “low”. Low numbers were, for whatever reason, more likely than high numbers. I did find a way to compensate by making a sort of slow and hackish “curve”. Rolling a one would select the first point. Rolling a two or three would select the second point. And rolling a 4, 5, 6, or 7 would select the third point. Using this, I managed to get the thing to fill in just about evenly. <\/p>\n

    Looking back, I can think of a number of better tricks I could have used, but at 15 I didn’t yet know about bit-wise shifting or modulo. (And, I’m not even sure they were available in those early versions of BASIC.)<\/p>\n

    Yes, am am overcome with a sense of nostalgia over a bit of 80’s computer code<\/em>. This is far<\/strong> more healthy than the way some people are getting all nostalgic for 80’s fashions<\/strong>. <\/p>\n

    Question for the coders out there: What was the first program you wrote yourself? No, I don’t mean “Hello World!” I mean the first time you struck out on your own and wrote something on purpose. (Mine was a primitive coin-flip game, on my first computer<\/a>.)<\/p>\n","protected":false},"excerpt":{"rendered":"

    When I was about 15 years old, I ran into the following set of directions: Take a piece of paper. Mark 3 dots on it. They can be anywhere, but for aesthetic reasons it is common to pick three points that will form an equilateral triangle. Number these points 1 through 3. Get yourself a […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[66],"tags":[],"class_list":["post-2022","post","type-post","status-publish","format-standard","hentry","category-programming"],"_links":{"self":[{"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=\/wp\/v2\/posts\/2022","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=2022"}],"version-history":[{"count":0,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=\/wp\/v2\/posts\/2022\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=2022"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=2022"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=2022"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}