如何使用 biginteger 对两个边界之间的数字求和

Question

我正在尝试对 2 个给定数字之间的所有数字求和，不包括边界。例如addNumbers("5", "8") 应该 return 13 因为 6+7=13。这是我目前的功能。

 public static BigInteger addNumbers(String from, String to) {
  BigInteger total = new BigInteger("0");
  BigInteger startingBoundary = new BigInteger(from);
  BigInteger finishingBoundary = new BigInteger(to);

  if (startingBoundary.compareTo(finishingBoundary) < 0) {
     startingBoundary = new BigInteger(from);
     finishingBoundary = new BigInteger(to);
  } else {
     finishingBoundary = new BigInteger(from);
     startingBoundary = new BigInteger(to);
  }

  while (startingBoundary.compareTo(finishingBoundary) != 0 )  {
     System.out.println("Starting boundary:" + startingBoundary.intValue());
     System.out.println("Finishing boundary: " + finishingBoundary.intValue());

     total.add(startingBoundary);
     System.out.println("total: "+total.intValue());

     startingBoundary.add(new BigInteger("1"));
  }
  return total;

}

问题是 while 条件似乎是运行无限，尽管我改变了它的值。此外，当在每个循环中打印出总对象时，它总是打印出 0。我知道我将它初始化为 0，但我希望它会随着我添加到它而改变。

Answer 1

使用

total = total.add(startingBoundary);

和

startingBoundary = startingBoundary.add(new BigInteger("1"));

因为 add 不加到第一个操作数，而是 returns 总和。

此外，在开始循环之前，做

startingBoundary = startingBoundary.add(new BigInteger("1"));

以满足您必须排除起始边界的条件。

作为防御性编码，不要使用等于零，而是使用

startingBoundary.compareTo(finishingBoundary) < 0

Answer 2

请注意，BigInteger 的使用意味着数字，以及两个数字之间之间的差异可能巨大。从字面上看，从下边界到上边界循环可能需要 ages。相反，您可以使用封闭形式 sum(1..N) = (N*(N+1))/2 的变体。用它来计算从 1 到 upper 和从 1 到 lower 的数字，然后将两者结合起来得到你想要的结果。

BigInteger lower = new BigInteger("5"); BigInteger upper = new BigInteger("8"); BigInteger one = BigInteger.ONE, two = BigInteger.TWO; BigInteger oneToUpper = upper.multiply(upper.add(one)).divide(two); BigInteger oneToLower = lower.multiply(lower.add(one)).divide(two); BigInteger lowertoUpperInc = oneToUpper.subtract(oneToLower).add(lower); System.out.println(lowertoUpperInc); // 5 + 6 + 7 + 8 = 26 BigInteger lowertoUpperExc = oneToUpper.subtract(oneToLower).subtract(upper); System.out.println(lowertoUpperExc); // 6 + 7 = 13

（请注意，对于此示例，您的循环似乎也 return 18，这似乎是 5+6+7，因此不是您真正想要的。）

除了你的循环，这也适用于 truly BigInteger，例如lower = 123456789123456789 和 upper = 987654321987654321 的总和（包括和不包括）分别为 480109740480109740075445815075445815 和 480109740480109738964334703964334705。

Answer 3

正如另一个答案中已经提到的那样：像

这样的电话

total.add(startingBoundary);

没有任何可观察到的效果。 add 方法不会修改 total 对象。相反，它 return 是一个 new BigInteger 对象。更一般地说，原因是 BigInteger 是不可变的。这意味着 BigInteger 对象的值在创建后无法更改。原因请看

将行更改为

total = total.add(startingBoundary);

将解决此问题（类似地，对于其他行 - 对于固定实现，请参见下面的示例）。

旁注：通常应该使用 BigInteger.ZERO 和 BigInteger.ONE，而不是 new BigInteger("0") 和 new BigInteger("1")。没有理由为这些经常使用的值创建新对象。

但可能的改进：

除非作业明确说明这必须用循环来解决，否则有一个 far 更有效和优雅的解决方案。您可以使用 Gauß'sche Summenformel（抱歉，没有英文版本），它基本上说明了

1到n的自然数之和等于(n*(n+1))/2

因此您可以直接计算这些总和，以获得范围的限制，然后只是return 两者之间的差值。

以下包含原始代码的固定版本和替代实现，以及（非常基本）"microbenchmark":

import java.math.BigInteger;
import java.util.Locale;

public class SumFromRange
{
    public static void main(String[] args)
    {
        simpleExample();
        simpleBenchmark();
    }

    private static void simpleExample()
    {
        System.out.println(addNumbers("5", "8"));
        System.out.println(addNumbersFast("5", "8"));

        System.out.println(addNumbers("15", "78"));
        System.out.println(addNumbersFast("15", "78"));
    }

    private static void simpleBenchmark()
    {
        int blackHole = 0;
        for (long min = 10000; min <= 20000; min += 10000)
        {
            for (long max = 10000000; max <= 20000000; max += 10000000)
            {
                String from = String.valueOf(min);
                String to = String.valueOf(max);

                long before = 0;
                long after = 0;

                before = System.nanoTime();
                BigInteger slow = addNumbers(from, to);
                after = System.nanoTime();
                blackHole += slow.hashCode();

                System.out.printf("Compute %10d to %10d slow took %8.3f ms\n",
                    min, max, (after - before) / 1e6);

                before = System.nanoTime();
                BigInteger fast = addNumbersFast(from, to);
                after = System.nanoTime();
                blackHole += fast.hashCode();

                System.out.printf(Locale.ENGLISH,
                    "Compute %10d to %10d fast took %8.3f ms\n", min, max,
                    (after - before) / 1e6);

            }
        }
        System.out.println("blackHole " + blackHole);
    }

    public static BigInteger addNumbers(String from, String to)
    {
        BigInteger total = BigInteger.ZERO;
        BigInteger startingBoundary = new BigInteger(from);
        BigInteger finishingBoundary = new BigInteger(to);

        if (startingBoundary.compareTo(finishingBoundary) < 0)
        {
            startingBoundary = new BigInteger(from);
            finishingBoundary = new BigInteger(to);
        }
        else
        {
            finishingBoundary = new BigInteger(from);
            startingBoundary = new BigInteger(to);
        }

        startingBoundary = startingBoundary.add(BigInteger.ONE);
        while (startingBoundary.compareTo(finishingBoundary) != 0)
        {
            total = total.add(startingBoundary);
            startingBoundary = startingBoundary.add(BigInteger.ONE);
        }
        return total;
    }

    public static BigInteger addNumbersFast(String from, String to)
    {
        BigInteger f = new BigInteger(from);
        BigInteger t = new BigInteger(to);
        BigInteger sf = computeSum(f);
        BigInteger st = computeSum(t.subtract(BigInteger.ONE));
        return st.subtract(sf);
    }

    // Compute the sum of 1...n
    public static BigInteger computeSum(BigInteger n)
    {
        BigInteger n1 = n.add(BigInteger.ONE);
        return n.multiply(n1).divide(BigInteger.valueOf(2));
    }

}

较大值的基准测试结果很明显：

Compute      10000 to   10000000 slow took  635,506 ms
Compute      10000 to   10000000 fast took    0.089 ms
Compute      10000 to   20000000 slow took 1016,381 ms
Compute      10000 to   20000000 fast took    0.037 ms
Compute      20000 to   10000000 slow took  477,258 ms
Compute      20000 to   10000000 fast took    0.038 ms
Compute      20000 to   20000000 slow took  987,400 ms
Compute      20000 to   20000000 fast took    0.040 ms

他们甚至不在同一个联盟中...

如何使用 biginteger 对两个边界之间的数字求和

How to sum numbers between two boundaries using biginteger

java

biginteger