Math.Pow to the People

The .NET framework is crammed with nifty and useful small classes that provide commonly needed utility functions. You can't write a substantive application without finding a need for at least a handful of them. If you're working on an application doing computations particularly ones involving equations that need to be solved, you'll probably end up looking at the .NET Math class.

In that class is a method I've had some recent intense exposure to that dredged up memories of high school algebra classes, wondering what I'd do with algebra down the road, and being thankful I grew up just after slide rules disappeared from common use. But I digress.

The method in question in my case is the ever handy Pow method. This little guy takes a double and raises it to a double power. Very handy. However, I quickly ran into some real world issues with it that required cracking open some of those old dusty books and re-reading the rules of algebra.

You see the equation I was toying with deals with raising numbers to an integer power. This makes things a bit easier and straightforward. But Math.Pow although highly useful wasn't designed for the Decimal .NET type, and it isn't tuned to this special case of integer powers. It's handy, but, well.., slow.

I was using it in some algorithms for which I had neither the time nor sanction to overhaul to reduce or eliminate the use of Math.Pow. I was stuck with how it was used. But I wondered if I could use it more efficiently. Thus the turn to algebra.

A little refresher.

Take a number (any number) and raise it to an integer power, let's say, 10. Generally, we'd write that as x ^ 10. Now using the rules of algebra, x ^ 10 = x ^ ( 5 * 2 ). But things get more interesting. We can also write this as x ^ 10 = (( x ^ 5 ) ^ 2 ). That is raise x to the power of 5 and then that value to the power of 2. Mathematically we get the same number in the end. But here's the kicker. When doing an exponential calculation, instead of writing this as multiply x by itself 10 times (which is 10 multiplications), we've reduced that to 5 + 2 = 7 multiplications in the alternative style.

You can generalize this even further by finding the set of integer divisors of an integer that sum to the smallest possible value. This value is the smallest number of multiplications you can do to raise a number to that power. Take a number like 100. That can be rewritten as 10 * 5 * 2 = 17. So if I need to raise a value like 1.2 ^ 100, I can rewrite that as ((1.2 ^ 10) ^ 5) ^ 2). 17 multiplications is a whole lot less than 100.

The sharp reader might notice that a flaw in the approach is dealing with prime numbers like 7 or 13. These numbers have no divisors other than itself and 1, so the approach isn't more optimal for them than just doing the full set of multiplications. But for non primes particularly those with large numbers of divisors, this approach can result in significant performance improvements of Math.Pow.

Finding the set of divisors for an integer that form the smallest possible sum is mechanical and lends itself to a lookup table. Easy to implement too.

So the next time someone asks what good is algebra, tell them that like that old TV show from the 1970's, you can "compute that value in 2 notes". Um, I mean 2 divisors with a little help from basic algebra.

Peace.

Posted by Mark M. Baker at 11:49 PM  Permalink