Large number multiplication

Ian Kelly ian.g.kelly at
Thu Jul 7 17:49:10 CEST 2011

On Thu, Jul 7, 2011 at 2:30 AM, Ulrich Eckhardt
<ulrich.eckhardt at> wrote:
> Even worse, most people would actually pay for its use, because they don't
> use numbers large enough to merit the Schönhage–Strassen algorithm.

As it stands, Karatsuba is only used for numbers greater than a
specific threshold.  Adding Schönhage–Strassen would just mean adding
another threshold, below which Karatsuba would still be used.  So at
worst it would just add another comparison or two for numbers within
the Karatsuba range.

More information about the Python-list mailing list