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); } }

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; } }

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.

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:

ReplyDeleteusing 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);

}

}

def xton(x, n):

ReplyDeleteif (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)

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

ReplyDeleteSo 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

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.

ReplyDelete