Category Archives: Algorithms

Fast Peak Autocorrelation

So, I was at geekcon. It was a blast. There were many interesting projects, and I didn’t get to play with them all. I did get to work a bit on the Lunar Lander from last year, and this year … Continue reading

Posted in Algorithms, Math, Programming, Projects, Python, Utility Functions | Tagged , , , , , | Leave a comment

Computing Large Determinants in Python

Story: For my seminar work, I had to calculate the determinant of a large integer matrix. In this case, large meant n>=500. You might say that this isn’t very large and I would agree. However, it is large enough to … Continue reading

Posted in Algorithms, computer science, Math, Programming, Python, Research | Tagged , , , , , | 2 Comments

Fractal Memory Usage and a Big Number

In a previous post I said I’d talk about 4**(4**(4**4)). First, about the number. I first saw it mentioned in a math lesson back in high-school, when the teacher wanted to demonstrate estimation abilities. He wrote it on the board, … Continue reading

Posted in Algorithms, computer science, Fractals, Math, Programming, Python | Tagged , , , | 1 Comment

First Code Transformation: Removing Flag Computations

Short introduction to code transformations If you intend to write a decompiler, you’ll find yourself writing code transformations. In our context, code transformations are operations that take as input an expression tree, and return an equivalent but different expression tree. … Continue reading

Posted in Algorithms, Assembly, decompilation, Programming | Tagged , , , , , , | 1 Comment

Issues in Writing a VM – Part 2

Writing a VM capable of executing expression trees is different from writing a VM for executing assembly instructions. Here I’ll cover several issues stemming from this difference. The first group of issues involve generality. Supporting a specific instruction set is … Continue reading

Posted in Algorithms, Assembly, computer science, Programming, Projects, Python | Tagged , , , , , | 7 Comments

Two Mathematical Bugs

A few days ago, I discovered I had at least one, maybe two mathematical bugs. The first bug is in the line clipping algorithm. Here’s a quick reminder of what’s going on there: There are six points of interest: the … Continue reading

Posted in Algorithms, Geometry, Math, Programming, Python | Tagged , , , , | 2 Comments

Rhyme and Reason with Python

After reading xkcd’s blog, I went to LimerickDB.com. It looks and works just like bash.org, but for limericks. Quite amused with some of the limericks available, I wanted to try and compose my own. The first one came out fine, … Continue reading

Posted in Algorithms, Humour, Programming, Python | Tagged , , , , , | Leave a comment

Small Python Challenge No. 2 – LRU Cache

Caching is easy. Consider the cache I used to optimize the recursive spring: class _NotInDict(object): pass _NotInDict = _NotInDict() def cached(func): cache = {} def wrapper_func(*args): prev_result = cache.get(args, _NotInDict) if prev_result is _NotInDict: result = func(*args) cache[args] = result … Continue reading

Posted in Algorithms, Challenges, computer science, Programming, Python, Utility Functions | Tagged , , | 2 Comments

Optimizing the recursive spring

Remember the recursive spring? Well, when I worked on it, it was quite slow. I mean very slow. Especially at the higher levels. The original reason was the recursion. Consider this – to ‘springify’ a track, you had to sample … Continue reading

Posted in Algorithms, Fractals, Programming, Python | Tagged , | Leave a comment

Elegant Line Clipping Algorithm

I actually wrote about that a long time ago, in the wiki that once was algorithm.co.il. Since the wiki is long gone, and I figured this is a very elegant algorithm, I decided I should write about it. First, some … Continue reading

Posted in Algorithms, Geometry, Graphics, Math, Programming, Python | Tagged , , , | Leave a comment