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