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

Sunday, November 06, 2005

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?