计算指数增长序列中值的总和

Question

（参见下面的解决方案）

（潜伏者出现）

我正在使用 BigDecimal/BigInteger 类来处理非常大的数字。

我有一个计算复合增长系列的公式。

对于每个n，value = initial * (coef ^ n).

我正在尝试寻找一种快速方法来计算 n0 和 n1 之间的值子集的总和。

例如，n0 = 4 和 n1 = 6，

returns: 初始值 * (coef ^ 4) + 初始值 * (coef ^ 5) + 初始值 * (coef ^ 6)

我不太懂数学，但也许有一种公式化的表达方式？

我基本上是将所有值相加，通过提高系数将其中一些值聚集成 10 的幂。

据我所知该函数是准确的。我可以 return

的值

n0 = 1，n1 = 50000，初始值 = 100，系数 = 1.05，不到一秒。

虽然我可能永远不会将函数用于高于 ~20,000 的值，但很高兴知道是否有更有效的方法。

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

下一个问题是求出 n1 的最大值，其中 sum(n0, initial, coef) <= x。

编辑：

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

(初始 * 系数 ^ n0 - 系数 ^ n1 + 1) / 1 - 系数

感谢维基百科。

Answer 1

我会写一些算法思想

首先让我们简化您的公式：

所以你应该计算：S = a * (c ^ n0) + a * (c ^ (n0+1)) +...+ a * (c ^ n1) 其中 initial = a 和 coef = c

令 S(n) 是以下总和的函数： S(n) = a + a * c + a * (c^2) +...+ a * (c ^ n)

我们会得到S = S(n1)-S(n0-1)

另一方面 S(n) 是 geometric progression 的和，因此 S(n)=a * (1- c^n)/(1-c).

所以我们会得到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).

所以现在我们必须处理计算 c^n 指数（当然 BigDecimal class 有 pow 方法，我们这样做只是为了能够计算算法的复杂度）。以下算法具有 O(log(n)) 复杂度：

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

所以我们可以得出结论，如果我们考虑到代数运算具有 的事实，那么可以在 O(log(n)) 复杂度中计算和O(1) 复杂度。

计算指数增长序列中值的总和

Calculate the sum of values in an exponential growth series

java

bigdecimal

exponential