16 February 2012

Calculating x^y

I stumbled onto this blog (Antonio Gulli) the other day and read through a couple of his suggested programming problems.

Kind of interesting to tackle that power function. After coming up with a rather naive solution to begin with, I attempted to improve on it and ended up with the following implementation for X^Y that works when X and Y  are integers. As I wanted to keep it rooted in the .NET framework implementation I needed to use the BigInteger class so the function will not return a value for negative Y values just yet :)

What do you think?

using System;
using System.Numerics;

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

        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 (Well this will work when we have BigDecimal in System.Numerics)
        return y < 0 ? 1/pow : pow;