Further BigInteger performance improvements (original) (raw)

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 http://futureboy.us/

More information about the core-libs-dev mailing list