[pypy-issue] [issue819] Arithmetic is slower than CPython in extreme cases

[anon]

anon <b10419697 at klzlk.com> added the comment:

Thanks!

That implementation seems to be equivalent to the one in Modern Computer
Algebra. I coded a straight implementation in Python and found that it's slower
than inbuilt multiplication for less than around 20,000-bit numbers.

I think one difference between this implementation and libgmp's one is the
evaluation points we use. This implementation uses -1, 0, 1, 2 and infinity
while libgmp uses the points 0, 0.5, 1, 2 and infinity. A faster version of the
-1, 0, 1, 2 infinity version can be seen on line 229 of:

http://code.google.com/p/bignumberslibrary/source/browse/trunk/src/ru/kirilchuk/bigint/BigInteger.java

I implemented my own version of it in Python:

http://paste.ubuntu.com/1082209/

Additionally it appears _tcmul_split(n, size) essentially makes a copy of n
instead of referencing its bits.

I'd first find out what part of _tc_mul is actually taking so long. When I was
testing my all-Python version above I prematurely returned an obviously wrong
answer at different points inside the toomcook function to see where the bulk of
the computation takes place.

________________________________________
PyPy bug tracker <tracker at bugs.pypy.org>
<https://bugs.pypy.org/issue819>
________________________________________