sympy/sympy — pull request #2368 by skirpichev (2013-08-09 12:37:51+00:00)
Title: Implement Karatsuba multiplication for polynomials

Some simple benchmarks:
```
In [6]: p1=random_poly(x, 1000, -100, 100, polys=True)
In [7]: p2=random_poly(x, 1000, -100, 100, polys=True)
In [8]: %timeit p1*p2
1 loops, best of 3: 404 ms per loop
In [9]: !git checkout Karatsuba-polys-mul
Switched to branch 'Karatsuba-polys-mul'
In [10]: %timeit p1*p2
10 loops, best of 3: 179 ms per loop
In [11]: p1=random_poly(x, 10000, -100, 100, polys=True)
In [12]: p2=random_poly(x, 10000, -100, 100, polys=True)
In [13]: %timeit p1*p2
1 loops, best of 3: 7.18 s per loop
In [14]: !git checkout master
Switched to branch 'master'
In [15]: %timeit p1*p2
1 loops, best of 3: 45.1 s per loop
```

Threshold `n = 100` is a result of some experimentation. For sparse polynomials we should also take into account some measure of "sparseness" as well.