tag:blogger.com,1999:blog-11250707903508917012024-03-13T21:17:21.191-07:00normal ordersacheiehttp://www.blogger.com/profile/11515254793586726097noreply@blogger.comBlogger35125tag:blogger.com,1999:blog-1125070790350891701.post-7235891430461835312019-06-18T09:39:00.002-07:002020-09-16T00:59:33.564-07:002048It's been a while without any new posts here; I've been focused on projects where JavaScript or C are more suitable than Haskell (for me, anyway). But I did dust off GHC this weekend to write this no-frills clone of Gabriele Cirulli's popular '2048' puzzle game. It didn't come out quite as concise as I had hoped - maybe I'm a bit rusty? :)
<p>
As usual with my graphical stuff, you'll need the legacy (1.2) versions of SDL to compile this. And the font path may vary; adjust it for your system.
<script src="https://gist.github.com/mkserra/98cef704b7b5dd87a9f4d2ebfc663186.js"></script>sacheiehttp://www.blogger.com/profile/11515254793586726097noreply@blogger.com0tag:blogger.com,1999:blog-1125070790350891701.post-57599948604500980522018-05-31T14:47:00.004-07:002020-09-16T01:25:02.375-07:00ramanujan's Π summationWhen G.H. Hardy first began his correspondence with Srinivasa Ramanujan, he was amazed by the prodigy's elegant and surprising series for irrational and transcendental values. Although Ramanujan hadn't included proofs of the theorems, Hardy told his colleagues, "they must be true, because, if they were not true, no one would have the imagination to invent them."
<p>
For example, here's Ramanujan's sum for Π which, after just 3 terms, overwhelms IEEE 754 double precision. Modern discoveries, like spigot algorithms on non-decimal bases, can find a given individual digit in constant time. But for fully expanding Π, no one has surpassed Ramanujan's expression: both the Chudnovsky brothers and Yasumasa Kanada adapted it to achieve their milestone calculations.
<script src="https://gist.github.com/mkserra/a20fa47129c1f975b1c49660a1880933.js"></script>sacheiehttp://www.blogger.com/profile/11515254793586726097noreply@blogger.com0tag:blogger.com,1999:blog-1125070790350891701.post-69317530311988411702018-03-13T15:27:00.004-07:002020-09-16T09:00:24.706-07:00generalizing langton's ant
<a target='_blank' href='https://1.bp.blogspot.com/-V8jfBbguPX8/X2HZJiQOGnI/AAAAAAAABpQ/d8iing5fhLocbzHd52rZF8GNKeZlS0G8wCNcBGAsYHQ/s0/turmite_big.png'>
<img style='float: left; margin-right: 15px' alt="" border="0" src="https://1.bp.blogspot.com/-lKPwhKMjzWQ/X2HPbuJYVEI/AAAAAAAABpE/hlCrfKp3aAUvm91mbRk3DZFJtOLdH18NQCNcBGAsYHQ/s0/turmite.png"/>
</a>
<div style='font-size: 1.25em; line-height: 150%'>
<a target='_blank' href='http://normalorder.blogspot.com/2016/01/langtons-ant.html'>Christopher Langton's ant</a> can be generalized by adding states to the ant, producing automata known as <a target='_blank' href='https://en.wikipedia.org/wiki/Turmite'>turmites</a>. Shown here is the behavior of one interesting two-state turmite, started on an empty plane. Click the thumbnail to see more generations; you'll see that this turmite always produces a framed square with the same distinctive irregular pattern.
</div>
<div style='clear: left; padding-top: 20px'>
<script src="https://gist.github.com/mkserra/ea85cf5539eda4c1138ad40847f001d0.js"></script>
</div> sacheiehttp://www.blogger.com/profile/11515254793586726097noreply@blogger.com0tag:blogger.com,1999:blog-1125070790350891701.post-79737557197650168342017-12-13T11:26:00.003-08:002020-09-16T02:39:22.988-07:00gumowski-mira attractor
<a target='_blank' href='https://3.bp.blogspot.com/-Smw4GP9WAjM/WjGu2DdnlgI/AAAAAAAAAY4/zPRYNcdliIwRxWX_7_97oKCubp2ptxoRACLcBGAs/s1600/other_mira.gif'>
<img style='float: left; margin-right: 15px' alt="" border="0" src='https://3.bp.blogspot.com/-nvYiaarlOVA/WjF-cJR3ehI/AAAAAAAAAYk/lI8EUhCe3KsRCh6n2JBrJ0mwPpGZnUhGQCLcBGAs/s1600/mira.png'/>
</a>
<div style='font-size: 1.25em; line-height: 150%'>
Here's an unusual chaotic attractor: the web doesn't seem to have much information on this one, except that it was invented to model particle trajectories in physics. A google image search for 'mira fractals' does turn up some pretty results though.
<p>
The system seems to give interesting results only when <i>b</i> is close to one. It behaves less chaotically when <i>b > 1</i> is fixed, so you can actually animate it - click the thumbnail to see.
<script src="https://gist.github.com/mkserra/fd65e1c2cb67971c9c77dfc6bb48f35e.js"></script>sacheiehttp://www.blogger.com/profile/11515254793586726097noreply@blogger.com0tag:blogger.com,1999:blog-1125070790350891701.post-16599717854715042022017-05-15T15:10:00.004-07:002020-09-16T03:00:26.467-07:00128-bit AES electronic codebookRijndael (the core of AES) is an algorithm that might actually be shorter and simpler in C, but I was curious to see how natural I could make it look in Haskell. Thanks to <a target='_blank' href="http://www.moserware.com/2009/09/stick-figure-guide-to-advanced.html">Jeff Moser</a> and <a target='_blank' href="http://www.samiam.org/rijndael.html">Sam Trenholme</a> for their clear elucidations.
<p>
Note that this code only does ECB mode; it computes rather than hard-codes the S-box; and it could be vulnerable to side-channel attacks. So enjoy reading it, but don't try to make a serious encryption app out of it. That kind of thing is best left to the professionals :)
<script src="https://gist.github.com/mkserra/8eadae29b4072deef4a024f0bbeb3f6d.js"></script>sacheiehttp://www.blogger.com/profile/11515254793586726097noreply@blogger.com0tag:blogger.com,1999:blog-1125070790350891701.post-67642294293820877462017-03-06T03:08:00.003-08:002020-09-16T06:39:03.665-07:00butterfly curve<a target='_blank' href='https://3.bp.blogspot.com/-gSClndDq9FE/WL1BQmnm4xI/AAAAAAAAAVI/2TZ31TG3t1I0lEQ-exNLf70bHGHiAMmXQCLcB/s1600/color_butterfly.png'>
<img style='float: left; margin-right: 15px' alt="" border="0" src="https://2.bp.blogspot.com/-UXkqYB30d5M/WL1Arw1EcuI/AAAAAAAAAVE/69AFaFv0NdYIn-TB3g5NPn4ch6yIvSzTQCLcB/s1600/small_color_butterfly.png"/>
</a>
<div style='font-size: 1.25em; line-height: 150%'>
Temple Fay discovered this <a target='_blank' href='https://en.wikipedia.org/wiki/Butterfly_curve_(transcendental)'>complicated curve</a> in 1989. It can be defined either parametrically or as a polar equation; I did it the former way.
<p>
One application I thought of for this is object motion in games: I tried it out by writing <a target='_blank' href='http://sacheie.net/space-evader/'>this little Canvas game,</a> where the comets follow the curve's trajectory. The differences in plot density along the curve create natural-looking comet tails.
</div>
<div style='clear: left; padding-top: 5px'>
<script src="https://gist.github.com/mkserra/ece6db0f99ba990432a226b6511708f6.js"></script>
</div>
sacheiehttp://www.blogger.com/profile/11515254793586726097noreply@blogger.com0tag:blogger.com,1999:blog-1125070790350891701.post-37293210908620395972017-02-24T13:15:00.004-08:002020-09-16T07:13:38.873-07:00bézier curves<img style='float: left; margin-right: 15px' alt="" border="0" src="https://1.bp.blogspot.com/-ogSfNYkwoYQ/X2IcYH9w4MI/AAAAAAAABpc/lqUd-7EXyH0aZr0k6z3qt3Xams_bykcjwCNcBGAsYHQ/s0/curve.png"/>
<div style='font-size: 1.58em; line-height: 180%'>
<a target='_blank' href='https://en.wikipedia.org/wiki/De_Casteljau%27s_algorithm'>De Casteljau's algorithm</a> is a fast, numerically stable way to rasterize Bézier curves. This code implements an interactive demo: click to append nodes to the curve's defining polygon, and drag any node to alter the curve.
</div>
<div style='clear: left; padding-top: 15px'>
<script src="https://gist.github.com/mkserra/c4cb7bdbb7b9fbb8b04a7a30cad092c8.js"></script>
</div>
sacheiehttp://www.blogger.com/profile/11515254793586726097noreply@blogger.com0tag:blogger.com,1999:blog-1125070790350891701.post-42488398970129715452017-02-22T15:02:00.004-08:002020-09-16T07:32:50.214-07:00convex hulls<a target='_blank' href='https://1.bp.blogspot.com/-k3-X-yY6g_w/WK9nU6T3-QI/AAAAAAAAATg/5O6imW3CsCQV2ddRuoTeuQArTK8kP31AQCLcB/s1600/bighull.png'>
<img style='float: left; margin-right: 15px' alt="" border="0" src="https://1.bp.blogspot.com/-nHy8kF5hedo/WK8AeytRiJI/AAAAAAAAATE/7b2hqXxGYeYWphIdcThQr8EDkSDAh84LgCLcB/s320/hull2.png"/>
</a>
<div style='font-size: 1.25em; line-height: 150%'>
This code demonstrates the <a target='_blank' href='https://en.wikipedia.org/wiki/Graham_scan'>Graham scan</a>, an O(<i>n</i> log <i>n</i>) method for finding the <a target='_blank' href='https://en.wikipedia.org/wiki/Convex_hull'>convex hull</a> (smallest enclosing polygon) of a planar point set. It's a great example of exploiting order: it works by sorting the set by angle about a known extreme point, allowing the hull points to be found in linear time.
<p>
A <a target='_blank' href='https://en.wikipedia.org/wiki/Graham_scan#Notes'>variation on the algorithm</a>, noted by A.M. Andrew, sorts the set lexicographically and finds the upper and lower hull chains separately. This 'monotone chain' version is often preferred, since it's easier to do robustly.
</div>
<div style='clear: left; padding-top: 1px'>
<script src="https://gist.github.com/mkserra/698cffe52366bba038baf66a5ecaaf46.js"></script>
</div>
sacheiehttp://www.blogger.com/profile/11515254793586726097noreply@blogger.com0tag:blogger.com,1999:blog-1125070790350891701.post-75504719458949037212017-02-15T11:41:00.001-08:002020-09-16T08:59:22.847-07:00more Π obscurantismHere's an illustration of an <a target='_blank' href="http://www.mathpages.com/home/kmath001/kmath001.htm">approach</a> to Π pointed out by Kevin Brown. Define <i>f(n)</i> as the nearest greater or equal multiple of n-1, then of n-2, etc (yielding OEIS sequence <a target='_blank' href="http://oeis.org/A002491">2491</a>). Then, inverting a result found by Duane Broline and Daniel Loeb, Π = n<sup>2</sup> / f(n).
<p>
But as you can see from the comment, the series converges very slowly!
<script src="https://gist.github.com/mkserra/7d8ec492b867d5e892a22f22b40a4875.js"></script>sacheiehttp://www.blogger.com/profile/11515254793586726097noreply@blogger.com0tag:blogger.com,1999:blog-1125070790350891701.post-72509343272991537712016-06-03T09:36:00.002-07:002020-09-16T12:00:06.097-07:00segment intersection search<div style='font-size: 1.55em; line-height: 180%'>
<a target='_blank' href='https://4.bp.blogspot.com/-yWZD_oZ8KaU/V1GxgMYEKMI/AAAAAAAAAPM/DXMg-DFJPTcvUJxJd7YXy3TAD69IxPqjQCLcB/s1600/full.png'>
<img style='float: left; margin-right: 15px' alt="" border="0" src="https://1.bp.blogspot.com/-xjXK2W_qSZ8/X2JgBBZpGAI/AAAAAAAABpo/cd7o3XWPf-UjmSmUvSBuc5ttd3pb6qAUwCNcBGAsYHQ/s0/lines.png"/>
</a>
Here's a simple method I learned from <a target='_blank' href="http://stackoverflow.com/a/565282">Gareth Rees</a> for finding the intersection (or parallel / collinear status) of two line segments. Rees credits <a target='_blank' href="https://www.researchgate.net/publication/243505273_Intersection_Of_Two_Lines_In_Three-Space">Ronald Goldman</a>, though I'd imagine the technique goes further back.
</div>
<div style='clear: left; padding-top: 20px'>
<script src="https://gist.github.com/mkserra/11ac1321ba9dc1d8405da51358090442.js"></script>
</div>sacheiehttp://www.blogger.com/profile/11515254793586726097noreply@blogger.com0tag:blogger.com,1999:blog-1125070790350891701.post-70815471803565002272016-03-28T15:06:00.003-07:002020-09-16T12:16:01.024-07:00today in oblique approaches
If your standard library offers complex numbers and you're not in any hurry, you can't ask for much simpler (or more obscure!) ways to compute Π than <a target='_blank' href='https://www.youtube.com/watch?v=d0vY0CKYhPY'>this</a>.
<div style='clear: left; padding-top: 15px'>
<script src="https://gist.github.com/mkserra/30417b5ad5522f91f037a76704a7731f.js"></script>
</div>
sacheiehttp://www.blogger.com/profile/11515254793586726097noreply@blogger.com0tag:blogger.com,1999:blog-1125070790350891701.post-63663487733474251062016-02-17T18:01:00.002-08:002020-09-16T12:23:34.100-07:00ikeda map
<div style='font-size: 1.25em; line-height: 155%'>
<a target='_blank' href='https://2.bp.blogspot.com/-CoxPaA4OGwc/VsUqVOM7rgI/AAAAAAAAAN4/f--BuPtMgio/s1600/big_ikeda.png'>
<img style='float: left; margin-right: 15px' alt='' border='0' src='https://2.bp.blogspot.com/-erE89eWX7KA/VsUhmgnRjnI/AAAAAAAAANk/M3mWbKMWTSk/s1600/thumb_ikeda.png'/>
</a>
Continuing the theme of strange attractors, here's the well-known one embedded in the <a target='_blank' href='https://en.wikipedia.org/wiki/Ikeda_map'>Ikeda map</a>. The thumbnail at left shows the central 'vortex'
of the attractor, and links to a larger viewport.
<p>
In these images, I've plotted the real and imaginary components along the x and y axes respectively. But <a href='https://en.wikipedia.org/wiki/Ikeda_map#Attractor' target='_blank'>the more popular way</a> to visualize this attractor
adds an extra parameter to the system and is expressed in trigonometric functions. Such adaptation of the code below yields <a target='_blank' href='https://4.bp.blogspot.com/-uxkjyNQ9j50/VsZwXYviPEI/AAAAAAAAAOM/zxvMEvI1tzw/s1600/real_ikeda.png'>
these results</a>.
</div>
<div style='clear: left; padding-top: 5px'>
<script src="https://gist.github.com/mkserra/21bb008f67a4892fb9ccf151756d4e0a.js"></script>
</div>
sacheiehttp://www.blogger.com/profile/11515254793586726097noreply@blogger.com0tag:blogger.com,1999:blog-1125070790350891701.post-89007956082152087132016-02-13T19:33:00.001-08:002020-09-16T12:58:18.951-07:00hénon attractor
<div style='font-size: 1.6em; line-height: 170%'>
<a target='_blank' href='https://2.bp.blogspot.com/-QJf-LsglPpo/Vr_zOQbBOII/AAAAAAAAANM/Jd93h8wZYQc/s1600/big.png'>
<img style='float: left; margin-right: 15px' alt='' border='0' src='https://1.bp.blogspot.com/-kR-PslYFD78/X2Jsq35WQ9I/AAAAAAAABp0/7Eq3mzv3GmocSS6JjxdU3SU8gY7G_4OnQCNcBGAsYHQ/s0/small_henon.png'/>
</a>
French astronomer Michel Hénon reported on this <a target='_blank' href='https://en.wikipedia.org/wiki/Hénon_map'>strange, fractal attractor</a> in 1976. Since then, it has been among the most studied examples of chaotic dynamical systems.
</div>
<div style='clear: left; padding-top: 15px'>
<script src="https://gist.github.com/mkserra/f42974545c2ae08baa84a275b36238a3.js"></script>
</div>sacheiehttp://www.blogger.com/profile/11515254793586726097noreply@blogger.com0tag:blogger.com,1999:blog-1125070790350891701.post-59593975486880668752016-01-26T17:10:00.003-08:002020-09-16T13:17:58.607-07:00langton's ant
<div style='font-size: 1.4em; line-height: 170%'>
<img style='float: left; margin-right: 30px' alt='' border='0' src='https://4.bp.blogspot.com/-9NBIHOKbvnQ/VqgY-tiUkmI/AAAAAAAAAMY/Ff3HqgB26EY/s1600/langton.png'/>
For a round of code golf, I wrote this spare implementation of <a href='https://en.wikipedia.org/wiki/Langton%27s_ant' target='_blank'>Chris Langton's remarkably simple universal computer.</a> If you want amenities like <i>pause</i>, <i>random starting pattern</i> or even <i>quit</i>, check out <a href='http://normalorder.blogspot.com/2016/01/plenary-ant.html'>this more complete version</a>.
</div>
<div style='clear: left; padding-top: 20px'>
<script src="https://gist.github.com/mkserra/763fbc32b98e17090c42efd2cb005994.js"></script>
</div>
sacheiehttp://www.blogger.com/profile/11515254793586726097noreply@blogger.com0tag:blogger.com,1999:blog-1125070790350891701.post-2157471081902072122015-12-23T14:02:00.003-08:002020-09-16T13:58:21.614-07:00connett circles
<div style='font-size: 1.5em; line-height: 160%'>
<a target='_blank' href='http://4.bp.blogspot.com/-DrPHFLhP2S8/VnsZJ2Vr3pI/AAAAAAAAALo/WwRRsLq1wtg/s1600/fav5.png'>
<img style='float: left; margin-right: 23px' alt='' border='0' src='http://4.bp.blogspot.com/-J9vlBNvV3aU/VnsY0fdLQwI/AAAAAAAAALg/nFq3uSOtfe8/s1600/main0_thumb.png'/>
</a>
Like Barry Martin's '<a href='http://normalorder.blogspot.com/2015/12/martin-attractor.html'>Hopalong</a>' fractal, this dynamical system from John Connett was first published in <i>Scientific American</i> in 1986. This demo is interactive: successively clicking two points specifies a rectangle to zoom into. Doing so, you'll see that the system isn't actually a fractal. Instead of self-similarity, deep zooms reveal <a target='_blank' href='http://4.bp.blogspot.com/-abARZNIhun4/VnsZgxwIKMI/AAAAAAAAALw/i0m0OAXvj7k/s1600/4.png'>peacock-like images</a>.
</div>
<div style='clear: left; padding-top: 20px'>
<script src="https://gist.github.com/mkserra/e65866b39beeb97169d8a6d05b9ee689.js"></script>
</div>
sacheiehttp://www.blogger.com/profile/11515254793586726097noreply@blogger.com0tag:blogger.com,1999:blog-1125070790350891701.post-41601734611757892862015-12-23T09:33:00.001-08:002020-09-16T14:59:30.995-07:00martin attractor
<div style='font-size: 1.3em; line-height: 150%'>
<a target='_blank' href='http://2.bp.blogspot.com/-syi1BFCehpM/VnrZ9NJUTYI/AAAAAAAAAK4/IAJZ9-RB7NE/s1600/big.png'>
<img style='float: left; margin-right: 20px' alt='' border='0' src='https://1.bp.blogspot.com/-KxNzTztCrs0/VnrY5Ad59VI/AAAAAAAAAKw/ZbrhQQ-TL00/s1600/hopalong_thumb.png'/>
</a>
This pattern generator, discovered by Barry Martin, was nicknamed '<a target='_blank' href='http://www.nahee.com/spanky/www/fractint/martin_hop_type.html'>Hopalong</a>' when <i>Scientific American</i> introduced it in their September '86 issue.<p>Clicking the window adjusts the viewport position; there is also an <a target='_blank' href='http://4.bp.blogspot.com/-K-VQqaqvP40/Vnr6e5UZ-VI/AAAAAAAAALM/b1X8BYBIf-w/s1600/animated_martin_fractal.png'>alternate version</a> with color and animation.
<p>
Also, for a certain Rubyist friend, I wrote another lazily-evaluated, colored and animated <a target='_blank' href='https://github.com/mkserra/ruby_toys/blob/master/martin-attractor.rb'>implementation</a> in Ruby.
</div>
<div style='clear: left; padding-top: 5px'>
<script src="https://gist.github.com/mkserra/c16284c2f8de8e9d9e723116524c371d.js"></script>
</div>
sacheiehttp://www.blogger.com/profile/11515254793586726097noreply@blogger.com0tag:blogger.com,1999:blog-1125070790350891701.post-8651300429737238622015-12-22T00:03:00.005-08:002020-09-16T15:25:06.354-07:00lyapunov fractals
<div style='font-size: 1.65em; line-height: 160%'>
<a target='_blank' href='http://4.bp.blogspot.com/-6n4tFWlGJ40/Vnlk4dOcO3I/AAAAAAAAAKY/rf8OjBhAY1Q/s1600/24000-1-3.5-3.65_big.png'>
<img style='float: left; margin-right: 25px' alt='' border='0' src='https://1.bp.blogspot.com/-ZAdzhAQx6Hk/X2KQhO5OA7I/AAAAAAAABqE/z9ah_hK81togjLuzn5e75W34Zu7U1GDRACNcBGAsYHQ/s0/lyapunov.png'/>
</a>
It took me some experimentation to figure out how to color <a target='_blank' href="https://en.wikipedia.org/wiki/Lyapunov_fractal">this derivation of the logistic map</a>; I'm still not quite sure how the hues should scale as you zoom. But the bi-tonal method shown below works well enough to produce the image at left - click it for more detail.
</div>
<div style='clear: left; padding-top: 20px'>
<script src="https://gist.github.com/mkserra/004b3d1f5a48d6db514fc06805b3c5f0.js"></script>
</div>
sacheiehttp://www.blogger.com/profile/11515254793586726097noreply@blogger.com0tag:blogger.com,1999:blog-1125070790350891701.post-82285435868224315792015-12-15T18:22:00.002-08:002020-09-16T15:59:08.733-07:00the mandelbrot set
<div style='font-size: 1.4em; line-height: 160%'>
<img style='float: left; margin-right: 18px' alt='' border='0' src='https://1.bp.blogspot.com/-j2PbkiTElHw/X2KV2gzaXxI/AAAAAAAABqQ/28Mj71xrIis9ocsZ5QRbY5I55YWdKCIugCNcBGAsYHQ/s0/mandelbrot.png'/>
What programmer hasn't at some point written an implementation of Benoit Mandelbrot's great discovery, <a target='_blank' href="https://en.wikipedia.org/wiki/Mandelbrot_set">the most famous fractal</a> in the world? Here's my own minimal version, with the simplest possible coloring scheme. To interact with it, just click any two points: the window will zoom in on the rectangle they define.
</div>
<div style='clear: left; padding-top: 20px'>
<script src="https://gist.github.com/mkserra/7b8626417b2730b55849fdb415cd92fa.js"></script>
</div>
sacheiehttp://www.blogger.com/profile/11515254793586726097noreply@blogger.com0tag:blogger.com,1999:blog-1125070790350891701.post-21832603328192475842015-11-02T14:19:00.003-08:002020-09-16T16:11:43.005-07:00a lava lamp
<div style='font-size: 1.4em; line-height: 150%'>
<img style='float: left; margin-right: 20px' alt='' border='0' src='https://2.bp.blogspot.com/-q9o4iBdF-wQ/VjfhIgoAlqI/AAAAAAAAAJA/9oUTND4uX44/s320/result.gif'/>
This 'lava lamp' is actually a simple <a target='_blank' href='https://en.wikipedia.org/wiki/Cyclic_cellular_automaton'>cyclic cellular automaton</a>; the CA rule is courtesy of <a target='_blank' href='http://www.mirekw.com/ca/rullex_cycl.html'>Jason Rampe.</a> In keeping with the spirit of Haskell, I chose to implement it with a hashmap of points rather than an array. Needless to say, that's not practical; but this is just a demonstration.
</div>
<div style='clear: left; padding-top: 20px'>
<script src="https://gist.github.com/mkserra/b592d05303f412c6f74aab152c3cb5d9.js"></script>
</div>
sacheiehttp://www.blogger.com/profile/11515254793586726097noreply@blogger.com0tag:blogger.com,1999:blog-1125070790350891701.post-69493514250214735072015-08-19T19:58:00.004-07:002020-09-16T19:26:15.695-07:00random undirected graphs<div style='font-size: 1.55em; line-height: 180%'>
<img style='float: left; margin-right: 25px' alt='' border='0' src='http://4.bp.blogspot.com/-9FgGTNjyNm4/VdVGYXxOOlI/AAAAAAAAAIY/l14d2dQNSLE/s1600/rand_graph.png'/>
This little program generates random, undirected graphs without loops or isolated vertices (though the graph is not necessarily connected).
<p>
I have found it useful to generate random inputs for testing graph algorithms.
</div>
<div style='clear: left; padding-top: 20px'>
<script src="https://gist.github.com/mkserra/d09184336ada304954bc532f67e49589.js"></script>
</div>
sacheiehttp://www.blogger.com/profile/11515254793586726097noreply@blogger.com0tag:blogger.com,1999:blog-1125070790350891701.post-11346704525879551932015-07-08T16:57:00.007-07:002020-09-16T21:18:33.544-07:00sqrt 2, visualized
<div style='font-size: 1.1em; line-height: 130%'>
<a target='_blank' href='https://drive.google.com/uc?export=view&id=0B629ZbkrOtvdd0tTZlJpb1lLY2s'>
<img style='float: left; margin-right: 20px' alt='' border='0' src='https://1.bp.blogspot.com/-Z7RVhg8i0d0/VZ2tWDS71sI/AAAAAAAAAHA/2H9lpQUNNoY/s1600/thumb.png'/>
</a>
This code, inspired by my <a href="http://normalorder.blogspot.com/2014/01/prime-curve.html">earlier post</a>, animates the digits of √2 in an unsuual way. Each digit advances the curve in the direction given by a numeric keypad, with 5 and 0 both considered (0,0). The thumbnail at left links to a 4000x4000 window on 9856041 digits of the curve, which originates at the image center.
<p>
The program makes for an interesting screensaver, but does it follow any pattern, or illustrate any special properties of √2 ? Though I'm no mathematician, from what I've read this seems unlikely. √2 is <a target='_blank' href='https://en.wikipedia.org/wiki/Square_root_of_2#Properties'>suspected</a> (but not proved) to be a <a target='_blank' href='https://en.wikipedia.org/wiki/Normal_number'>normal number</a>. This would mean the digits of its expansion (respective to some number base) follow a uniform distribution; no digit would be more likely to appear than any other.
<p>
Nonetheless, I'd be curious to see the results of a really long run!
</div>
<div style='clear: left; padding-top: 0px'>
<script src="https://gist.github.com/mkserra/a5028ebcebf2cc3fdad660363b927bee.js"></script>
</div>
sacheiehttp://www.blogger.com/profile/11515254793586726097noreply@blogger.com0tag:blogger.com,1999:blog-1125070790350891701.post-72592018575196469672015-06-28T23:46:00.001-07:002020-09-16T21:33:00.825-07:00triangle geometry
<div style='font-size: 1.55em; line-height: 160%'>
<img style='float: left; margin-right: 20px' alt='' border='0' src='https://2.bp.blogspot.com/-EeQPQkoFElQ/VZDpuNtcN7I/AAAAAAAAAGs/JTVh-vV9GZI/s1600/triangle.png'/>
Here's a trivial post, mostly just to show off how nice mathematical code can look in Haskell. It illustrates the <a target='_blank' href="https://en.wikipedia.org/wiki/Centroid">centroid</a>, <a target='_blank' href="https://en.wikipedia.org/wiki/Incircle_and_excircles_of_a_triangle">incircle</a>, and <a target='_blank' href="https://en.wikipedia.org/wiki/Circumscribed_circle">circumcircle</a> of a random triangle, with everything defined in terms of vertex triples. The viewport centers on the circumcenter, and the triangle's interior is filled using <a target='_blank' href="https://en.wikipedia.org/wiki/Barycentric_coordinate_system">barycentric coordinates.</a>
</div>
<div style='clear: left; padding-top: 20px'>
<script src="https://gist.github.com/mkserra/3bff0f6398ed407c40a8bac32318f9be.js"></script>
</div>
sacheiehttp://www.blogger.com/profile/11515254793586726097noreply@blogger.com0tag:blogger.com,1999:blog-1125070790350891701.post-53933514415313085742015-03-30T23:29:00.003-07:002020-09-16T21:57:14.064-07:00primitive totalistic automata
<div style='font-size: 1.4em; line-height: 170%'>
<img style='float: left; margin-right: 18px' alt='' border='0' src='https://1.bp.blogspot.com/-JNv8AsqotmA/VRo_mhTlXHI/AAAAAAAAAF4/p3BNBdL0UaI/s1600/1017.png'/>
This code renders any of the 2187 possible 3-colored, 1-dimensional, <a target='_blank' href='https://mathworld.wolfram.com/TotalisticCellularAutomaton.html'>totalistic cellular automata</a>. I was charmed by these and many other beautiful demonstrations in <a target='_blank' href='https://en.wikipedia.org/wiki/A_New_Kind_of_Science'>Stephen Wolfram's notorious compendium</a>, though I regret I can't say the same for its tendentious style.
<p>
The program input is an integer representing the intended CA rule in base 3.
</div>
<div style='clear: left; padding-top: 2px'>
<script src="https://gist.github.com/mkserra/0d528c89a2d0a1ab799687a3c63e3890.js"></script>
</div>
sacheiehttp://www.blogger.com/profile/11515254793586726097noreply@blogger.com0tag:blogger.com,1999:blog-1125070790350891701.post-78934500384603764362015-02-18T00:01:00.002-08:002020-09-16T22:15:56.733-07:00elementary cellular automata
<div style='font-size: 1.25em; line-height: 150%'>
<img style='float: left; margin-right: 20px' alt='' border='0' src='https://1.bp.blogspot.com/-LDZNznPvcCA/X2LvVcyDKrI/AAAAAAAABqc/Xmt3jVlquKM9QfQdYzeANfUeGgybA42lQCNcBGAsYHQ/s0/110.png'/>
This code takes the rule number for an elementary cellular automaton as input, and then runs the CA from a random seed, rendering the result. The seed comprises 600 random bits taken from <a target='_blank' href="http://en.wikipedia.org/wiki/Rule_30">rule 30</a>. Its length, when accounting for scale, is greater than the window width; this helps keep pathological edge effects outside the visible frame. The screenshot at left shows an execution of the famous <a target='_blank' href="http://en.wikipedia.org/wiki/Rule_110">rule 110.</a>
</div>
<div style='clear: left; padding-top: 20px'>
<script src="https://gist.github.com/mkserra/568cb7948cd6c933089e0dce7c3e2097.js"></script>
</div>
sacheiehttp://www.blogger.com/profile/11515254793586726097noreply@blogger.com0tag:blogger.com,1999:blog-1125070790350891701.post-82247198878377146192015-02-16T22:15:00.004-08:002020-09-16T22:47:17.145-07:00wolfram's random generator
Despite its fundamental simplicity, <a target='_blank' href="http://en.wikipedia.org/wiki/Rule_30">the rule 30 elementary CA</a> is conjectured to generate a purely random sequence along its center column. It reputably excels at many statistical tests of randomness, and <i>Mathematica</i> includes it as a choice of RNG.
<p>
For my own conviction, it was enough to find that the expression <i>sum (take 80 $ rands 5000) `div` 80</i> produces 2525.
<p>
Since each random bit requires computing a full cell generation, this algorithm quickly slows down. I assume more pragmatic implementations solve this by perhaps re-seeding the automaton after some number of iterations.
<div style='padding-top: 2px'>
<script src="https://gist.github.com/mkserra/956a7337c4c513ae8d4e4e1b93a8ab0d.js"></script>
</div>
sacheiehttp://www.blogger.com/profile/11515254793586726097noreply@blogger.com0