Calculate the sum of values in an exponential growth series

(SEE SOLUTION BELOW)

(lurker emerges)

I'm using the BigDecimal/BigInteger classes to work with really huge numbers.

I've got a formula for calculating a compound-growth series.

For each n, the value = initial * (coef ^ n).

I'm trying to discover a fast way to calculate the sum of a subset of values between n0 and n1.

So for example where n0 = 4 and n1 = 6,

returns: initial * (coef ^ 4) + initial * (coef ^ 5) + initial * (coef ^ 6)

I don't know much maths, but maybe there is a formulaic way of expressing this?

I'm basically adding up all the values, clumping some of them into powers of 10 by raising the coefficient.

As far as I know the function is accurate. I can return a value for

n0 = 1, n1 = 50000, initial = 100, coef = 1.05 in under a second.

Although I may never use the function for values higher than ~20,000, it would be nice to know if there are more effective approaches to this.

public static final BigDecimal sum(int n0, int n1, BigDecimal initial, BigDecimal coef) {
    BigDecimal sum = BigDecimal.ZERO;

    int short_cut = 1000000000;

    //Loop for each power of 10
    while (short_cut >= 10) {
        //Check the range of n is greater than the power of 10
        if (n1 - n0 >= short_cut) {
            //Calculate the coefficient * the power of 10
            BigDecimal xCoef = coef.pow(short_cut);

            //Add the first sum of values for n by re-calling the function for n0 to n0 + shortcut - 1
            BigDecimal add = sum(n0, n0 + short_cut - 1, initial, coef);
            sum = sum.add(add);

            //Move n forward by the power of 10
            n0 += short_cut;

            while (n1 - n0 >= short_cut) {
                //While the range is still less than the current power of 10
                //Continue to add the next sum multiplied by the coefficient
                add = add.multiply(xCoef);
                sum = sum.add(add);
                //Move n forward
                n0 += short_cut;
            }

        }
        //Move to the next smallest power of 10
        short_cut /= 10;
    }

    //Finish adding where n is smaller than 10
    for (; n0 <= n1; n0++)
        sum = sum.add(initial.multiply(coef.pow(n0)));
    return sum;
}

Next problem is to work out the largest value of n1 where the sum(n0, initial, coef) <= x.

EDIT:

public static final BigDecimal sum(int n0, int n1, BigDecimal initial, BigDecimal coef) {
    return initial.multiply(coef.pow(n0).subtract(coef.pow(n1 + 1))).divide(BigDecimal.ONE.subtract(coef));
}

(initial * coef ^ n0 - coef ^ n1 + 1) / 1 - coef

Thanks wikipedia.

Solution

I will write some algorithmic thoughts.

First of all lets simplify your formula:

So you should calculate: S = a * (c ^ n0) + a * (c ^ (n0+1)) +...+ a * (c ^ n1) where initial = a and coef = c

Let S(n) be a function of following sum: S(n) = a + a * c + a * (c^2) +...+ a * (c ^ n)

We will get S = S(n1)-S(n0-1)

In the other hand S(n) is a sum of a geometric progression, hence S(n)=a * (1-c^n)/(1-c).

So we will get S = S(n1)-S(n0-1)=a*(1-c^n1)/(1-c)-a*(1-c^(n0-1))/(1-c)=a*(c^(n0-1)-c^n1)/(1-c).

So now we have to deal with calculating c^n exponents (of course BigDecimal class has pow method, we are doing it just to be able to calculate complexity of algorithm). The following algorithm has O(log(n)) complexity:

function exp(c,n){
    // throw exception when n is not an natural number or 0
    if(n == 0){
        return 1;
    }
    m = exp(c, floor(n/2));
    if (n % 2 == 0){
        return m*m;
    } else{
        return m*m*c;
    }
}

So we can conclude that the sum can be calculated in O(log(n)) complexity if we taking into account the fact that algebraic operation has O(1) complexity.