## Wednesday, February 8, 2012

### Calculate x^y in optimal time

#### 4 comments:

1. Hehe.. I thoroughly enjoyed this one. Although it is getting a bit late and I've had a few beers, here is my attempt at solving this assuming that X and Y are always integers (decimals are harder), C# code below:

using System;
using System.Linq;
using System.Numerics;

class Program
{
private static Tuple<BigInteger, bool>[] levels;
private static int multcount;

static void Main(string[] args)
{
int x = 2;
int y = 2000;

levels = new Tuple<BigInteger, bool>[(int)Math.Ceiling(Math.Log(y, 2))];

// Calculate the levels
Build(x, y, 0);

// Now sum the whole thing according to the array
BigInteger sum = 1;
foreach (var p in levels.Where(m=> m.Item2))
{
sum *= p.Item1;
multcount++;
}

Console.WriteLine("{0}^{1}={2}\n operations:{3}", x, y, sum, multcount);
}

private static void Build(BigInteger sum, int y, int level)
{
levels[level] = new Tuple<BigInteger, bool>(sum, y % 2 != 0);
if (y <= 1) return;
multcount++;
Build(sum*sum, y/2, level+1);
}
}

2. def xton(x, n):
if (n == 0): return 1;
if (n == 1): return x;
t1 = xton(x, n/2);
t2 = xton(x, n/2);
if (x % 2 == 0):
return t1*t2;
else:
return t1*t2*x;

O log(n)

3. OK, my first attempt was poor and overly simple and I just couldn't leave it here :)

So below is my second attempt, this time around:
1. Uses loops rather than recursion (allows for better optimisation)
2. Removes state and unnecessary memory allocation (uses an extra BigInteger though)
3. Better handles edge cases, negative x values and smaller y values
4. Handles negative y values internally. But function returns 0 because BigDecimal is currently missing in the .NET framework.

using System;
using System.Numerics;

internal class Program
{
private static void Main(string[] args)
{
int x = 2;
int y = 2001;

BigInteger pow = Pow(x, y);

Console.WriteLine("{0}^{1}={2}", x, y, pow);
}

private static BigInteger Pow(int x, int y)
{
if (y == 0) return 1; // Zero power
int ay = Math.Abs(y);
BigInteger pow = 1;
BigInteger sum = x;
if (ay > 0)
{
var iterations = (int) Math.Ceiling(Math.Log(ay, 2));
for (int i = 0; i <= iterations; ++i)
{
if (ay == 0) break;
if (ay%2 != 0) pow *= sum;
sum *= sum;
ay = ay/2;
}
}

// Handle negative powers (This will work when we have BigDecimal in System.Numerics)
return y < 0 ? 1/pow : pow;
}
}

phew.. that is better

4. Knuth has a fascinating section in TAOCP about this problem. If I remember the summary correctly, finding the optimal addition chain is NP hard. You pretty much need to make a table for all lower powers.