| Showing 1-5 of 17 in category: all |
|
Blog split
The separation of life and geekdom |
|
||||
|
I had the realisation the other day that I had become reluctant to post computer science blog entries at the risk of annoying any non-computer science readership, and dually had become reluctant to post personal, or miscellaneous, blog entries at the risk of diluting any computer science content. This dichotomy of reluctance resulted in little to no blogging. The solution? Two blogs.
I now have a personal blog for essentially everything, and a computer science blog for maths/computer science and research-type things. Subsequently there are also two separate feeds and a feed that combines both. The old RSS feed address points to the feed for both blogs (see the pane on the right for the choices). Accompanying this split is a slight revamping of fonts and layouts, and a fixing of the older posts that had broken layouts. | |||||
|
13 May 2009 19:30:04 |
General |
Comments (4)
|
|||||
|
Easter & BCTCS '09
|
|
||||
|
Apologies for the lack of blog posts over the last few months. I've been pretty busy, but also quite lazy in writing anything on here, even if just to say that I am alive and well. It is now the "summer" term here at Cambridge and I am hoping that it will be a productive one. I had a full and fulfilling Easter holidays: attending the Midlands Graduate School (a week long pedagogical conference aimed at graduates doing theoretical CS work with programming languages), attending BCTCS 2009 (British Colloquium for Theoretical Computer Science), briefly visiting my family, and taking a trip with friends to Germany to see our good friend Larry (fantastic). BCTCS '09 was held at Warwick University- the university that I graduated from just last year and that is very dear to me! I enjoyed the conference particularly as I got to spend time with Steve Matthews and Sara Kalvala (my undergraduate project supervisors from my 3rd and 4th years), old friends from my undergraduate days, new friends from other universities, and also Bill Wadge, co-creator of Lucid, who was invited to speak at BCTCS '09 all the way from Victoria, Canada.
If you have ever had a conversation with me about computer science you will know I have a particular proclivity for the Lucid programming language, so getting to chat about all things Lucid for a few days was great fun. Bill supervised Steve back when Bill was at Warwick, in the early days of Lucid. The quip is that Bill is my grandsupervisor. I include here the slides from the my BCTCS talk. I am planning to write a few blog posts on Lucid, Lucian, and some other ideas and thoughts that came out of discussions at BCTCS, so watch this space if you are interested. Regular blog posting: a promise so easily made and so easily broken.
| |||||
|
29 April 2009 00:14:27 |
Lucian |
Comments (1)
|
|||||
|
The Koch Snowflake
Construction and some properties |
|
||||
|
As I mentioned a couple of weeks ago I was going to write a post about a certain fractal.
Now I have finally gotten round to writing something it has come at a very appropriate time as Britain has seen
an unusual amount of snow recently. Sadly all of that snow has melted now.
I am going to briefly introduce the Koch Snowflake (also known as the Koch Island, or Koch Star) which is a
fractal with a very simple construction. I will first informally describe
a geometrical construction of the fractal and will then show some of its properties, particularly the property
that the fractal has an infinite length enclosing a finite area.
Construction The base case of the construction is an equilateral triangle. For each successive iteration the construction proceeds as follows:
The first 5 iterations look like: 
Properties Two properties of this fractal may seem paradoxical at first but are easily shown. I will show the derivations here for the interested without skipping too many steps. For an infinite number of iterations the perimeter of the fractal (the length of all the edges) tends to infinity whilst the area enclosed remains finite. Infinite Perimeter First consider the number of edges for an infinite number of iterations. Initially the number of edges is 3, each iteration transforms a single edge into 4 edges (see above), thus the series of the edge count is: 3, 12, 48, .... The general form is: 
Starting from an edge length of a each iteration divides the edge length by 3. The following defines the edge length for iteration n and from this calculates the perimeter for iteration n. The limit as n tends to infinity is found, showing that the perimeter is infinite. 
Thus it is easy to see that the perimeter length is infinite through standard results on limits. Finite Area The area calculation is a little bit more involved. The result can be seen on Mathworld or Wikipedia but a full derivation isn't given, so I show my derivation here for the interested. The area of the n-th iteration of the Koch snowflake is the area of the base triangle + the area of the new, smaller, triangles added to each edge. From the above length calculations and construction we know that each iteration of the construction divides the length of the edges by three. First consider the relationship between the area of a triangle of edge length a and a triangle of edge length a/3
At each iteration we add new equilateral triangles to each edge, a ninth of the area of the previous iteration's triangles. We formulate this as a summation of base case A0 plus the next n-1 iterations where the triangle area at each stage is A0 divided by 32n or 9n (successive divisions of the area by 9). The number of edges is defined by the previous iterations number of edges 3 * 4n-1, thus at the n-th iteration we need to add this number of triangles to the snowflake. 
Thus the area is finite at 8/5 times the area of the base equilateral triangle. Summary So the Koch snowflake construction has been introduced and it has been shown relatively easily that the area of a Koch snowflake tends to a finite limit of 8/5 times the base case area (5) and that the length of perimeter tends to infinity (4). Next time I will probably talk a bit about the fractal dimension of the Koch snowflake and also show an interesting problem that uses the Koch snowflake. As a last note, following on from the blog post I made about the Python turtle library, a turtle program of the Koch snowflake for Python can be downloaded here. | |||||
|
18 February 2009 09:35:03 |
Maths |
Comments (0)
|
|||||
|
Fractals with the Python turtle library
Y-fractal |
|
||||
|
This coming weekend I am planning on writing a blog post about a particular fractal (I won't give the game away just yet :p), and whilst looking around at what was written on the Internet about this fractal I stumbled across a really cool little Python library: turtle. The turtle library essentially provides LOGO-like functionality to Python. You get a nice turtle object on which you can call standard logo functions like forward, left, right, pen up, etc. and it draws them on a Tk widget for you - FUN!
I thought I'd just share a couple of simple programs I made using the turtle library. The next post I will make about fractals will be more mathematical - this post is just for fun. I show here a method of drawing Y-fractals using the turtle. The informal scheme for drawing Y-fractals is: draw a Y then at the end of each of the two top branches of the Y draw smaller Y shapes and so on... A simple way to define fractals is via a Lindenmayer system which is essentially a grammar of production rules, variables, constants, and starting axioms. My Y-fractal has the following L-system properties:
 Y-fractal with branching depth of 5 in the process of being drawn by the Python turtle library. Download the source file for this program The neat thing about the library is that it handles all the graphics for you, so you can just have fun. The above example is only 20 lines of code:
import turtle
# Position the turtle
turtle.up()
turtle.goto(0,-100)
turtle.left(90)
turtle.down()
# Create description of the fractal
set="A"
for i in range(5): set=set.replace("A","LFSATFKFSATFL")
i = 1
turtle.forward(40)
for move in set:
if move is "A": turtle.left(180)
if move is "F": turtle.forward(100.0/1.6**i)
if move is "L": turtle.left(45)
if move is "K": turtle.left(90)
if move is "S": i+=1
if move is "T": i-=1
input()
Simple! The for-loop performs the L-system rewrite 5 times to create the 5 branches of the fractal. I then took this simple program a bit further and created a program that varies the branching factor and length of branches over time, generating a set of frames that emulates a tree growing from a small sapling to a densely foliaged tree: Apologies: The Youtube video is pretty blurry; the AVI file is slightly clearer although for some reason I still lost quite a bit of clarity from the generated frames. Here is the source file for this program (and the supporting script files used to convert the PS files to PNGs, generate still frames for the start and end of the movie, and convert from a sequence of PNGs to an AVI). So if you want to reminisce about the good old days of programming LOGO on your school's 286 during lunchtime then have a play with the turtle library, it comes with standard Python 2.4 and 2.6 installs. | |||||
|
23 January 2009 01:12:18 |
Programming |
Comments (1)
|
|||||
|
OpenCL 1.0 Specification released
Some thoughts... |
|
||||
|
Yesterday the specification for OpenCL 1.0 was released. For those who don't
know what OpenCL is here is a summary quote from the specification:
"OpenCL is an open industry standard for programming a heterogeneous collection of CPUs, GPUs and other discrete computing devices organized into a single platform. It is more than a language. OpenCL is a framework for parallel programming and includes a language, API, libraries and a runtime system to support software development. Using OpenCL, for example, a programmer can write general purpose programs that execute on GPUs without the need to map their algorithms onto a 3D graphics API such as OpenGL or DirectX." [p. 18]A worthy goal. But is OpenCL designed for use by anyone? "The target of OpenCL is expert programmers wanting to write portable yet efficient code. This includes library writers, middleware vendors, and performance oriented application programmers. Therefore OpenCL provides a low-level hardware abstraction plus a framework to support programming and many details of the underlying hardware are exposed." [p. 18]What about the general scientific computing community? Do we expect them to be expert programmers or have expert programmers on hand to write their simulations? While OpenCL addresses the expression of low-level programs for compilation to heterogeneous architectures it does not solve the human-tractability issues of manual parallel programming: it is complex, lengthy, tedious, error prone, and difficult to prove. OpenCL is not all things to all men/women. It does however provide a possible intermediate language for higher-level languages that abstract over low-level concurrency/parallel concepts. An interesting issue, that the specification picks up on, is that heterogeneity makes portability difficult when to porting code between a CPU and a GPU (as opposed to between different types of CPUs and different types of GPUs). "Unfortunately, there are a number of areas where idiosyncrasies of one hardware platform may allow it to do some things that do not work on another. " [p. 208] "Likewise, the heterogeneity of computing architectures might mean that a particular loop construct might execute at an acceptable speed on the CPU but very poorly on a GPU, for example. CPUs are designed in general to work well on latency sensitive algorithms on single threaded tasks, whereas common GPUs may encounter extremely long latencies, potentially orders of magnitude worse. A developer interested in writing portable code may find that it is necessary to test his design on a diversity of hardware designs to make sure that key algorithms are structured in a way that works well on a diversity of hardware. We suggest favoring more work-items over fewer. It is anticipated that over the coming months and years experience will produce a set of best practices that will help foster a uniformly favorable experience on a diversity of computing devices." [p. 208]This doesn't sound like the behaviour of a language with which people want to write "portable yet efficient code." [p. 18], but it is not the fault of OpenCL. This particular lack of portability is a necessary symptom of the low-level nature of the language. In OpenCL a loop is a loop. How can this be solved? Ideally we don't want our programmers to have to modify their algorithms to suit a set of possible hardware. Ideally algorithms and implementation should be separated by layers of specialization. A more abstract language may describe a loop that has a semantically equivalent efficient interpretation for a GPU and a standard efficient interpretation for the CPU. However, it is not desirable that a compiler perform significant transformations unbeknownst to the programmer, as this affects the programmer's (tacit or otherwise) cost-model for the language. Perhaps specializations should be expressed by the programmer (up to a point) via a multi-tiered approach to programming languages? Who knows! I'm just waving my hands in my head now and am going home for some tea. Check out the OpenCL project if you are interested. Bye. | |||||
|
9 December 2008 20:27:06 |
Programming |
Comments (6)
|
|||||
| Showing 1-5 of 17 in category: all |
