## 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) +  * (d-len(C1)))...   c2 = FFT.fft(list(C2) +  * (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  on Wikipedia (alternate link: ).

## 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?