## Saturday, December 17, 2005

### Allegro Quick Reference in Japanese

The Allegro Quick Reference guide that I wrote in 2002 [1] has been translated into Japanese [2] by Ohsawa Hirotaka. Cool.

## Friday, December 16, 2005

## Wednesday, December 07, 2005

### MPI matrix multiplication and inversion

MPI matrix multiplication and inversion routines, written for a physics class that I took last year. The code is modular, and more flexible than the matrix multiplication codes I found on the Web (I couldn't find any simple MPI matrix inversion routines on the Web). The PDF document is public domain. (Algorithms and Code).

See also: ScaLAPACK.

See also: ScaLAPACK.

## Sunday, November 13, 2005

### Moore's law

For the past 5 years, CPU speeds have been increasing roughly linearly. That's right, for processor speeds, Moore's law does not currently apply.

## Saturday, November 12, 2005

### FFT polynomial multiplication

It's easier than you might think:

I posted the algorithm [1] on Wikipedia (alternate link: [2]).

>>> def fft_mul(C1, C2):Takes O(

... d = len(C1)+len(C2)-1

... c1 = FFT.fft(list(C1) + [0] * (d-len(C1)))

... c2 = FFT.fft(list(C2) + [0] * (d-len(C2)))

... return list(FFT.inverse_fft(c1*c2)[:d].real)

...

>>> fft_mul([1,2,3],[4,5]) # (1+2*x+3*x**2)*(4+5*x)

[4.0, 13.0, 22.0, 15.0]

*n*log*n*) time. The idea is to right pad each polynomial with enough zeros so that the cyclic convolution becomes a noncyclic convolution. For more speed, pad`c1`

and `c2`

so each has power-of-2 length. (Source Code).I posted the algorithm [1] on Wikipedia (alternate link: [2]).

## Sunday, November 06, 2005

### pysam -- Python I2P SAM library

### Hogwarts Security

Wow. I thought I'd seen it all. Then I find the world's most famous cryptographer talking about security in the sixth Harry Potter book. Yes, I'm talking about Bruce Schneier, author of Applied Cryptography. That made me smile. The guy is also a judge for a proposed Tor GUI. Which makes me wonder: is he now interested in anonymous networks?

## Saturday, October 29, 2005

### Propositional logic in Python

Propositional logic inference via compressed truth tables. Module

`entail`

is presumably slower than your industrial-grade C inference algorithm, but logical statements are given as Python expressions, and entailment can be checked at the interactive prompt. This makes the module easy to use, and fun. (Source Code).
## Sunday, October 23, 2005

### Ventiloquate

Hyperventilate + loquacious = ventiloquate, to freak out and speak too much, too fast, and use way more breath than is actually needed to explain the idea. I assumed that this word existed, but I guess it actually doesn't.

## Friday, October 14, 2005

### Basic factorization algorithms

A paper which gives pseudocode and the reasoning behind some basic factorization algorithms: Fermat factorization, Pollard rho, Pollard p-1, and Brent's method. Public domain. (PDF document).

## Saturday, October 08, 2005

### Memoization with cache clear on return of last function call

Memoization is nice, but in dynamic programming, it can eat up ever-increasing amounts of memory as your memoized function is called with various arguments. A simple solution is to clear the cache when the last function call returns. (Python Recipe).

## Thursday, October 06, 2005

### mw2html -- Export Mediawiki to static, traditional website

`mw2html`

is a Python program which exports a Mediawiki site to a traditional-looking HTML site. No indices are generated, and Wikipedia sidebars and extra formatting are removed to give a simple, streamlined site (you can substitute in your own sidebars if you wish). The outputted HTML source code is Monobook-specific and rather verbose at the moment. But the sites thus exported don't look bad. (Source code).
## Tuesday, October 04, 2005

### List of bits in Python

A memory compacted list of bits (uses 1 byte per every 8 elements). Instantiate from a list or string of bits. Otherwise behaves just like the builtin Python list class. Uses the ListMixin class also published on this page. (Source code).

## Sunday, October 02, 2005

### Timing a function (pytime)

Python's timing facilities are...unPythonic. Module

`timeit`

requires you to specify the number of iterations for the timing loop. But that number varies according to the speed of the machine you're running on, level of optimization of your code, etc. It's more Pythonic to calculate the number of iterations in the timing procedure. As so: (Source code).
### Python htmldata module

Extract and modify URLs in an HTML/XHTML/CSS document. Translate HTML/XHTML documents to and from list data structures. Use cases: robots, proxy CGI scripts, filtering of HTML and CSS, and flexible wget-like mirroring. (Module website).

### List mixin for Python

You can use

`UserDict.DictMixin`

to create custom dictionary classes. Now you can use `listmixin.ListMixin`

to create custom list classes. (Source code).
### Modified Dijkstra's algorithm in Python

Algorithm: perform a breadth-first search, always expand the vertex with the smallest cost, and don't remove duplicate vertices in the cost-priority-queue.

This algorithm turns out to be nearly equivalent to Dijkstra's algorithm. For

The strategy of not removing duplicate vertices is particularly helpful in Python, where the builtin priority queue class doesn't support the DECREASE-KEY operation. See my comment at David Eppstein's recipe (the comment is public domain).

This algorithm turns out to be nearly equivalent to Dijkstra's algorithm. For

*n*vertices and*m*edges, it requires O(*n*+*m*) space, O(*m**log(*m*)) time, and always finds the shortest path.The strategy of not removing duplicate vertices is particularly helpful in Python, where the builtin priority queue class doesn't support the DECREASE-KEY operation. See my comment at David Eppstein's recipe (the comment is public domain).

### AI algorithms in Python

Uninformed search algorithms: breadth-first, depth-first, depth-limited, uniform cost, iterative deepening DFS, and bidirectional (in both tree and graph modes). (Source code).

Informed search algorithms: greedy best-first, beam, A* (in both tree and graph modes). (Source code).

Informed search algorithms: greedy best-first, beam, A* (in both tree and graph modes). (Source code).

Subscribe to:
Posts (Atom)