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

Question

我试图将 2 个给定数字之间除边界之外的所有数字相加。例如，addNumbers("5", "8")由于 6+7=13，因此应该返回 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

请注意，使用BigInteger意味着数字以及两个数字之间的差异可能会很大。从字面上看，从下边界到上边界循环可能需要很长时间。相反，您可以使用封闭形式的变体sum(1..N) = (N*(N+1))/2。1使用它对 from toupper和 from 1to 的数字求和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

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

除了循环之外，这也适用于true BigInteger，例如 和 的总和（包含和排除）分别为lower = 123456789123456789和。upper = 987654321987654321480109740480109740075445815075445815480109740480109738964334703964334705

Answer 2

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

total.add(startingBoundary);

没有任何可观察到的影响。该add方法不会修改对象total。相反，它返回一个新 BigInteger对象。更一般地说，其原因是BigInteger不可变的。这意味着对象的值BigInteger在创建后就无法更改。至于原因，可以看一下为什么java中的BigInteger被设计成不可变的？

将行更改为

total = total.add(startingBoundary);

将解决这个问题（同样，对于其他行 - 对于固定实现，请参见下面的示例）。

旁注：您通常应该使用and来代替new BigInteger("0")and 。没有理由为这些常用值创建新对象。new BigInteger("1")BigInteger.ZEROBigInteger.ONE

不过，可能的改进是：

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

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

因此，您可以在范围的限制下直接计算这些总和，然后返回两者之间的差值。

以下包含原始代码的固定版本和替代实现，以及（非常基本的）“微基准”：

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

这些根本就不是一个档次的……

Answer 3

使用

total = total.add(startingBoundary);

和

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

因为add并不与第一个操作数相加，而是返回总和。

另外，在开始循环之前，执行以下操作

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

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

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

startingBoundary.compareTo(finishingBoundary) < 0