4 Jun
2009
4 Jun
'09
11:15 p.m.
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@mindspring.com http://futureboy.us/