Calculer la somme des valeurs dans une série de croissance exponentielle

Question

(VOIR LA SOLUTION CI-DESSOUS)

(Rôdeur émerge)

J'utilise les classes BigDecimal/BigInteger à travailler avec des chiffres vraiment énormes. J'ai une formule pour calculer une série de croissance composée.

Pour chaque n, la valeur = initiale * (coef^n).

J'essaie de trouver un moyen rapide de calculer la somme d'un sous-ensemble de valeurs entre n0 et n1.

Ainsi, par exemple, où n0 = 4 et n1 = 6,

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

I Je ne connais pas beaucoup de maths, mais peut-être y a-t-il une façon stéréotypée d'exprimer cela? J'ajoute fondamentalement toutes les valeurs, en agglutinant certaines d'entre elles en puissances de 10 en augmentant le coefficient.

Pour autant que je sache, la fonction est précise. Je peux retourner une valeur pour

n0 = 1, n1 = 50000, initial = 100, coef = 1,05 en moins d'une seconde.

Bien que je ne puisse jamais utiliser la fonction pour des valeurs supérieures à ~ 20 000, il serait bon de savoir s'il existe des approches plus efficaces pour cela.

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

problème suivant est de travailler la plus grande valeur de n1 où la somme (n0, initiale, 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)); 
} 

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

Merci wikipedia.

Answer 1

Je vais écrire quelques pensées algorithmiques.

Tout d'abord permet de simplifier la formule:

Vous devez donc calculer: S = a * (c^n0) + a * (c^(1 + n0)) + ... + a * (c^n1) où initial = a et coef = c

Laissez S (n) être fonction de la somme suivante: S (n) = a + a * c + a * (c^2) + ...+ A * (c^n)

Nous aurons S = S (n1) -S (N0-1)

Dans d'autre part S (n) est une somme d'un geometric progression, d'où S (n) = a * (1-c^n)/(1-c).

Nous obtiendrons donc 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).

Maintenant, nous devons faire face à calculer c^n exposants (bien sûr, la classe BigDecimal a la méthode pow, nous le faisons juste pour être en mesure de calculer la complexité de l'algorithme). L'algorithme suivant a O (log (n)) complexité:

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

Nous pouvons donc conclure que la somme peut être calculée en O (log (n)) complexité si l'on compte tenu du fait cette opération algébrique a O (1) complexité.