Efficient implementation of algorithms for approximate exponentiation
We present efficient implementations of algorithms for the following fundamental problem: Given as input three positive integers x, y and j, compute the leading j digits of x(y). A special case of this problem (k = 2 and j = 1) was recently studied by Hirvensalo and Karhumaki [M.Hirvensalo, J.Karhumaki, Computing partial information out of uncomputable one-The first digit of 2 '' to base 3 as an example, in: Mathematical Foundations of Computer Science, in: Lecture Notes in Computer Science, Springer-Verlag, Inc., 2002] for which they presented a polynomial time algorithm. Specifically an algorithm of bit complexity O(n(2) log(3) n log log n) where n =: vertical bar y vertical bar is the number of digits in y. But their algorithm is not efficient in practice. For example, finding the leading digit of 2(y) where y is a 500 digit positive integer takes several hours. Hirvensalo and Karhumaki's algorithm is based on computing a rational approximation to In 2 (and a few other constants) to a high-degree of precision. Our approach is fundamentally different from theirs: we use a modified addition chain algorithm in which the multiplication is truncated to varying number of digits at various steps, followed by a self-tester that validates the truncation. Our algorithm runs several orders of magnitude faster. For example, on an input in which x and y have a few thousand digits, our program computes the leading 1000 digits in under 3 minutes. Since the approximate exponentiation has many application [B.Ravikumar, A Las Vegas randomized approximation algorithm for approximate exponentiation and its applications, in preparation] we hope that our algorithm will stimulate further research on this problem. (c) 2007 Elsevier B.V. All rights reserved.
algorithms software design and implementation