Further BigInteger performance improvements

Alan Eliasen eliasen at mindspring.com
Thu Jun 4 23:15:40 UTC 2009

Alan Eliasen wrote:
>    Note that my optimizations for the pow() function give vastly better
> performance at even small bit sizes for many operands, as they factor
> out powers of 2 in the exponent and perform these very rapidly as
> bit-shifts.

   Oops.  I mean powers of 2 in the *base*, of course.  The
exponentiation of these can be done extremely rapidly as left-shifts,
and the remaining portion of the number can be exponentiated more
rapidly because it's smaller.

   Otherwise, exponentiation is done by repeated squaring as before, but
with much better algorithms that take advantage of new implementations
of Karatsuba and Toom-Cook squaring for larger operands.

   Alan Eliasen
   eliasen at mindspring.com

More information about the core-libs-dev mailing list