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

[anon]

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

Sadly the code is part of proprietary software and I cannot provide source. If
you have a Linux 64 build of PyPy with such modifications I can test using that.

To anyone interested in implementing Toom-Cook multiplication, a good
description and pseudo-code is provided in Modern Computer Arithmetic which is
available freely. See http://arxiv.org/abs/1004.4710/, section 1.3.3.

To get best results one would need a fast algorithm for computing division by 3
which can be used with a right-shift to provide an exact division by 6 on line 8.

I'd expect an optimal cutoff parameter n_1 to be about 150 bits but it will need
tuning depending on the implementation.

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