Excursions in Programming - Generators

“Lazy computation kicks the llama’s ass” - Somebody The concept of a generator may be very foreign to those who haven’t really explored Python - though it is a general principle (like iterators). The crux of it is to generate the members of a set/relation one at time (which are subsequently returned). If you are not going to store the enumeration, this methods prevents needless use of memory (that may lead the program to be extremely slow). The trade of is the (minute) expense of storing some “state” in the function, and perhaps some additional function call overhead that is rarely a concern. ...

November 12, 2009 · 6 min · 1227 words · Arun Tejasvi Chaganty

Revisit to the Tripfest Era - Transport Tycoon Deluxe

It’s been far too long since I came up with decent material to put up here. Rather than let my blog die, the organic creature that it is, I thought I might as well look deep in my archives of half-baked articles and post something from there. This is one such article that I have no clue why I haven’t published as yet. I wrote it loooong ago, around the time of my rant about PlasmaPong, and is of a similar theme (and no surprise it’s a rant too). Anyways, here it is, in it’s raw un-edited format (oh, the value addition of lazyiness): ...

September 14, 2009 · 3 min · 542 words · Arun Tejasvi Chaganty

On Windows

It’s been a while since I’ve posted anything - prime culprit being work. For about two months now, I’ve been hacking on Windows (gasp), and I’d like to share my experiences. Since I am under a NDA (pfft), I can’t give more details than I was working with the Windows Filtering Platform and had to write a “driver” to do some packet inspection in kernel space. For those who know me at all, I’m a Linux-boy through and through (signed, sealed and delivered ;-)), but I took this as a great opportunity to actually find out how good/bad Windows was. I’m trying to be unbiased, but like heck I will be. ...

July 29, 2009 · 6 min · 1075 words · Arun Tejasvi Chaganty

Nearest Prime Number Algorithm

So prime numbers are useful. I found that I needed to generate a prime number for a hash table (details of which should be posted soon. If all goes well that is…). And I decided to come up with an algorithm to generate that prime number. Clearly stating the problem: “Find the smallest prime greater than n” The simplest way of generating primes is of course using Eurothenes' sieve1. However, this naive method runs in order of $\frac{n}{2} + \frac{n}{3} + \frac{n}{5} \ldots + \frac{n}{p}$ time, which MathWorld tells me is about $T(n) = \omega(n \ln(\ln(n)))$, and uses $\Theta(n)$ memory. This sucks for big numbers (or atleast I think I can do better). Further more, this step has to be repeated (or intelligently modified) till a prime number has been found. (I will show later that the best this can go would be $T(\lceil(\sqrt{n})+1^2\rceil)$), which is of the same order, $\omega(n \ln(\ln(n+1)))$ (mind you this is a lower bound). The algorithm I came up with, which I thought might be better is: generate all primes till $\sqrt{n}$, and check if any of them divide the number in question. If they don’t well, we have a prime, ladies and gentlemen. If they do, then we’ll just have to move along won’t we… ...

December 18, 2008 · 3 min · 474 words · Arun Tejasvi Chaganty

anjuta-gvim Preview

I closed some big bad bugs yesterday, and managed to get a whole workflow (open a bunch of files, edit, save, close) working without any glitchy-ness. Most of the time. And while I’m no where near the quality required to ship this plugin, it feels great all the same. A phenomenally boring Youtube screencast. There’s a very apparent bug in the video; it doesn’t change pages when the option is document is chosen from the Documents menu. I’ve already fixed it. If you liked this plugin, well, unfortunately you’ll have to wait a while. ...

July 11, 2008 · 3 min · 442 words · Arun Tejasvi Chaganty

QuickSort

QuickSort. It’s widely accepted as the fastest generic sorting algorithm around. It’s also very simple. A comment in the last article showed me this Haskell beauty: 1 2 qsort [] = [] qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs) While my C implementations aren’t any where as beautiful, I’m quite satisfied with their efficiencies. I’ll keep the code to a minimum, and the let the graphs do the talking. Quicksort is kinda like the heapsort, only not as strong (thus not as reliable). It is generally always recursive, and basically consists of 2 steps (Divide and Conquer): ...

July 6, 2008 · 4 min · 823 words · Arun Tejasvi Chaganty

Mergesort. Dissected.

Note: All code in this under the WTFPL1. Except possibly for Stepane Delcroix’s adapted code, which is under the MIT/X11 license Very recently, I decided to spend some time coding those standard algorithms that every programmer should know, but I am woefully ignorant of. The plan was to do an algorithm a day. Unfortunately, yesterday night, I started on the Merge sort algorithm, and I found some ancient bash script I wrote to profile and graph the running time of some other sorts (i.e. the bubble sort). Which led to me spending precious time playing around with gnuplot and various program parameters. Expect graphs. Lots of them. ...

July 4, 2008 · 8 min · 1607 words · Arun Tejasvi Chaganty

Maintainers, I Salute You!

For most of this past week, I have played the role of a maintainer for an obscure part of our college’s technical festival, Shaastra’s 1 website. I now respect the terribly difficult job a maintainer has to do. I also think I qualify as the worst maintainer ever. The portion of the website I’m working on is basically a portal where participants can pre-register for events, discuss on a forum and plot to take over the government. Nothing unusual as such really. This year, we decided to make the whole thing with Django (except the forums, which is a customized UNB). I remember reading a quote 2: ...

June 22, 2008 · 7 min · 1455 words · Arun Tejasvi Chaganty

Vim. Other Editors Don't Do Such Things

I’ve been making some progress on my Anjuta-Vim Integration project, infact, I even have screenshots :-) 1. But that’s very deceptive, notice the (null) ((null)) on the window title. Essentially, I’ve written an AnjutaPlugin that implements the necessary interfaces to “open files”. Currently all my interface implementation functions are returning NULL’s or 0’s (which can cause unpredictable segfaults and memdumps), and that brings me to the real challenge of my GSoC project. ...

June 1, 2008 · 5 min · 1012 words · Arun Tejasvi Chaganty

Glade Gotchas

Glade is awesome, no denying that. It’s clean, unlike any other ‘GUI building tool’ I’ve seen. It generates an XML description of the GUI, which is parsed at runtime. It’s simple, and hence easy to use (by virtue of the previous two attributes). At the same time, it does have it’s idiosyncrasies (and limitations) as well, only I’ve never really used the signal callback connector it provides to discover it for myself. It took a bit of googling before I could figure it out. ...

May 18, 2008 · 2 min · 231 words · Arun Tejasvi Chaganty