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.

Search the Web in Python

Query 6 search engines in Python. (Module website).

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.

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.

FFT polynomial multiplication

It's easier than you might think:

>>> def fft_mul(C1, C2):
...   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]

Takes O(n logn) 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]).

Trigonometry proved

Common trigonometric identities, proved in one page.

pysam -- Python I2P SAM library

A Python I2P SAM library, emulates the Python socket module. I haven't updated it in a while, but it works. (Main Page).

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?

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).

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.

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).

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).

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).

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).

Why books suck

An essay. Click comments for the text.

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).

Infinity in Python

Negative infinity:

>>> None < -1e308
True

Positive infinity:

>>> () > 1e308
True

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 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).