Return to Revisions

I've got a version that is slightly faster. I'd like to think the whole algorithm could be improved but it's too early in the morning for me to concentrate on that. What I would caution you is that sometimes casting can hurt performance, most notably if you are casting hundreds of millions of times.

That said there are lots of implicit castings going on in your code. A couple of examples:

• i < n
• m + 1 - i

Certainly m needs to be a BigInteger to hold Math.Pow(2, 200). But the constraint is that n will be less than 80K. So n could be a simple integer, which means there will be no implicit casting in the for conditional.

So I took your code and tried removing all such implicit castings to BigInteger while making n an Int32. I got over 10% improvement. On a side note, local variables should begin with a lowercase letter.

public static BigInteger Height(int n, BigInteger m)
{
    return n == 0 || m == BigInteger.Zero ? BigInteger.Zero : BigInteger.Remainder(SumHeight(n + 1, m), mo);
}

public static BigInteger SumHeight(int n, BigInteger m)
{
    BigInteger bigInt = BigInteger.One;
    BigInteger bigIntegerSum = BigInteger.Zero;

    for (int i = 1; i < n; i++)
    {
        BigInteger bi = new BigInteger(i);
        BigInt = BigInteger.Divide(BigInteger.Multiply(BigInteger.Subtract(BigInteger.Add(m, BigInteger.One), bi), bigInt), bi);
        bigIntegerSum = BigInteger.Add(bigIntegerSum, bigInt);
    }

    return bigIntegerSum;
}

Note that just your for loop alone required i to be cast as BigInteger 3 times (2 implicitly and 1 explicit). My reworking reduces that to only 1. Still, it would be cool to see if there is a better algorithm. Perhaps there should be some binary halving method. Instead of going from the bottom floor up, test the middle floor. If it fails, check the middle between it and the bottom, whereas if it succeeded check the middle between the top?