BigInteger性能

Question

public static BigInteger find(BigInteger A,BigInteger B) 
{ 
     BigInteger res=BigInteger.ONE;
     for(BigInteger i=A;i.compareTo(B)!=0;i.add(BigInteger.ONE)) 
          res=res.add(i);
     /*for(BigInteger i=1;i.compareTo(B)!=0;i.add(BigInteger.ONE)) 
          res=res.multiply(A);*/ 
     return res; 
} 

我的意图是在范围内添加任何2个数字。，假设是2到5(2+3+4+5)或加薪到B。我还有其他选择可以在BigInteger内完成，但有人能说出上面的片段有什么问题吗？

factor/performance)?

1. ，它产生长(而不是原始的)和
2. ，它的挣扎/杂耍如此之多地增加了1，而它通常在外面/没有循环增长？
3. 什么时候才能达到一个增量(时间还是空间
4. )？

Answer 1

在一个范围内，所有整数的和可以用平均值乘以值的数目来计算，也就是“计数”。

如果如问题中的"2至5( A )“文本所示，A和B都是包括在内的，那么我们就有：

average = (A + B) / 2
count = B - A + 1
sum = count * average
    = (B - A + 1) * ((A + B) / 2)
    = (B - A + 1) * (B + A) / 2   // flipped A + B for the symmetry of it

在Java代码中，使用BigInteger意味着：

public static BigInteger sumRangeInclusive(BigInteger A, BigInteger B) {
    return B.subtract(A).add(BigInteger.ONE).multiply(B.add(A)).shiftRight(1);
}

Answer 2

在增量后存储循环变量的值似乎存在问题。

算术级数之和应包括A和B。

public static BigInteger find(BigInteger A,BigInteger B) 
{ 
     BigInteger sum = BigInteger.ZERO;
     for (BigInteger i = A; i.compareTo(B) <=0; i = i.add(BigInteger.ONE)) {
         sum = sum.add(i);
     }
     return sum; 
}

测试：

System.out.println(find(new BigInteger("2"), BigInteger.valueOf(5)));
System.out.println(find(new BigInteger("200"), BigInteger.valueOf(500)));

输出：

14
105350

Answer 3

解决这一问题的一个更好的方法是应用简单的算法。我们知道：

到n = n * (n + 1) / 2的自然数的和

从m到n的自然数的和= Sum of natural numbers up to n减去Sum of natural numbers up to m - 1 = n * (n + 1) / 2 - (m - 1) * (m - 1 + 1) / 2 = n * (n + 1) / 2 - (m - 1) * (m) / 2 = (n * (n + 1) - (m - 1) * m) / 2.

演示：

import java.math.BigInteger;

public class Main {
    public static void main(String[] args) {
        System.out.println(find(BigInteger.valueOf(123456789), BigInteger.valueOf(987654321)));
    }

    public static BigInteger find(BigInteger A, BigInteger B) {
        return B.multiply(B.add(BigInteger.ONE)).subtract(A.subtract(BigInteger.ONE).multiply(A))
                .divide(BigInteger.TWO);
    }
}

输出：

480109740075445815

你的代码出什么问题了？

1. 循环在A与B相等时终止，而当A大于B时则终止。为此，可以使用终止条件，因为i.compareTo(B.add(BigInteger.ONE)) != 0.
2. A BigInteger是一个不可变的任意精度整数。因此，i.add(BigInteger.ONE)不会修改i的值。您需要将结果赋值给0.

，即i = i.add(BigInteger.ONE)，以便将i引用的值增加一个。

正确代码：

import java.math.BigInteger;

public class Main {
    public static void main(String[] args) {
        System.out.println(find(BigInteger.valueOf(2), BigInteger.valueOf(5)));
    }

    public static BigInteger find(BigInteger A, BigInteger B) {
        BigInteger res = BigInteger.ZERO;
        for (BigInteger i = A; i.compareTo(B.add(BigInteger.ONE)) != 0; i = i.add(BigInteger.ONE))
            res = res.add(i);
        return res;
    }
}

输出：

14

尽管通过这种方式修改代码可以得到正确的结果，但是它的性能将非常糟糕。