Algorithms from 6.3 (March/April 2008)

The problem we set for ourselves in this issue's column is: given integers x and N, compute x^N. Since this is a primitive operation in almost every public-key cryptographic system, it is both interesting and useful to understand how to do it quickly. And as a consequence, we can apply what we have learned to write a handy string function. Let us begin with the direct translation of the meaning of exponentiation into code. Function Power(x as Integer, N as Integer) as Integer dim theAnswer as Integer = 1 for i as Integer = 1 to N theAnswer = theAnswer*x next return theAnswer End Function A few test cases confirm that this code handles the case N = 0 correctly, and the case N < 0 not at all, but that's okay for now. The point to take away is that this implementation requires N multiplication operations. We can do a lot better than this. The trick is to expand the exponent N into its binary expansion, which I will write as b0 + b1 + ... + bk; for example, 7 = 1 + 2 + 4. We can then write Power(x, N) = Power(x, b0)*Power(x, b1)*...*Power(x, bk). This is at most Log_2(N) invocations of the Power function. The real optimization now comes from observing that each of these is computing x to a power-of-2. We can compute them as needed, and we can compute higher powers using the results of the previous computations. So what we need is a function that returns a bit representation of an Integer. Function Bits(N as Integer) As Integer() dim theBits() as Integer dim M as Integer = N while M > 0 theBits.Append M and 1 M = M\2 wend return theBits End Function This function returns an Integer array containing a bit representation of N, starting with the low bit. Using it to expand the exponent, here is a faster implementation of exponentiation. Function Power(x as Integer, N as Integer) As Integer dim powerBits() as Integer = Bits(N) dim theAnswer as Integer = 1 dim powerOfX as Integer = x for i as Integer = 0 to UBound(powerBits) if powerBits(i) = 1 then theAnswer = theAnswer*powerOfX end if powerOfX = powerOfX*powerOfX next return theAnswer End Function Of course we can move the code to compute bits inline, and combine the loops. Function Power(x as Integer, N as Integer) As Integer dim theAnswer as Integer = 1 dim powerOfX as Integer = x dim M as Integer = N while M > 0 if (M and 1) = 1 then theAnswer = theAnswer*powerOfX end if powerOfX = powerOfX*powerOfX M = M\2 wend return theAnswer End Function Finally, here is a version that eliminates the last multiplication and division. Function Power(x as Integer, N as Integer) As Integer dim theAnswer as Integer = 1 dim powerOfX as Integer = x dim M as Integer = N while M > 0 if (M and 1) = 1 then theAnswer = theAnswer*powerOfX end if powerOfX = powerOfX*powerOfX M = M\2 wend return theAnswer End Function Let us now approach the problem from the other end of the bit representation of the exponent. Suppose that N is even. Then Power(x, N) = Power(x, N\2)^2. If N is odd, then N - 1 is even, so Power(x, N) = x*Power(x, (N - 1)\2)^2. This provides us with a recursive solution. Function Power(x as Integer, N as Integer) if N = 0 then return 1 end if dim p as Integer = Power(x, N\2) if N mod 2 = 0 then return p*p else return x*p*p end if End Function This version is a little longer, but performs the comparison to 0 only as needed. Function Power(x as Integer, N as Integer) if N Mod 2 = 0 then if N > 0 then dim p as Integer = Power(x, N\2) return p*p else return 1 end if else dim p as Integer = Power(x, N\2) return x*p*p end if End Function We can get simpler code, though, by instead using the identity Power(x, N) = Power(x*x, N\2). Function Power(x as Integer, N as Integer) As Integer if N mod 2 = 0 then if N > 0 then return Power(x*x, N\2) else return 1 end if else return x*Power(x*x, N\2) end if End Function And at the cost of some function calls, we can reduce the code even further. Function Power(x as Integer, N as Integer) As Integer if N > 1 then return Power(x, N mod 2)*Power(x*x, N\2) elseif N = 1 then return x else return 1 end if End Function So we have both iterative and recursive implementations of our idea. Some testing suggests that the iterative implementation is about 50% faster than the recursive implementation. The iterative implementation is about twice as slow as the REALbasic function Pow. In either case, the number of operations performed is proportional to Log_2(N). As N grows, this results in a significant performance boost. Now let us apply our efforts to strings. Many scripting languages come with a Repeat function that returns the concatenation of N copies of a string with itself. Repeat("abc", 3) = "abcabcabc" We can use the algorithms we have worked out to implement such a function. Because string concatenation is a lot slower and more expensive than multiplication, we can really see the benefit of reducing the number of operations. Here is the recursive version. Function Repeat(s as String, N as Integer) As String if N > 1 then return Repeat(s, N mod 2) + Repeat(s + s, N\2) elseif N = 1 then return s else return "" end if End Function And here is the iterative version. Function RepeatIterative(x as String, N as Integer) As String dim theAnswer as String = "" dim powerOfX as String = x dim M as Integer = N while M > 1 if M mod 2 = 1 then theAnswer = theAnswer + powerOfX end if powerOfX = powerOfX + powerOfX M = M\2 wend if (M and 1) = 1 then theAnswer = theAnswer + powerOfX end if return theAnswer End Function The iterative version remains faster than the recursive version, and in fact the performance difference is more significant than it was for integer computation. For strings, we can write an even faster iterative version in exchange for being a little more casual with memory usage. Function RepeatIterative2(x as String, N as Integer) As String dim powerOfX as String = x dim M as Integer = N while M > 0 powerOfX = powerOfX + powerOfX M = M\2 wend return LeftB(x, LenB(x)*N) End Function Here, we simply double the string until it is long enough, then chop off the bit we want. Perhaps you think that we have beaten exponentiation into the ground. But we are not even close. For that, you should consult Volume 2 of "The Art of Computer Programming" for an in-depth discussion of exponentiation.

Clearance Sale!

Fast Exponentiation

It's Not Just for Numbers

Print:
PDF: