如何使用 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 = 26BigInteger 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{&nbsp; &nbsp; public static void main(String[] args)&nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; simpleExample();&nbsp; &nbsp; &nbsp; &nbsp; simpleBenchmark();&nbsp; &nbsp; }&nbsp; &nbsp; private static void simpleExample()&nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; System.out.println(addNumbers("5", "8"));&nbsp; &nbsp; &nbsp; &nbsp; System.out.println(addNumbersFast("5", "8"));&nbsp; &nbsp; &nbsp; &nbsp; System.out.println(addNumbers("15", "78"));&nbsp; &nbsp; &nbsp; &nbsp; System.out.println(addNumbersFast("15", "78"));&nbsp; &nbsp; }&nbsp; &nbsp; private static void simpleBenchmark()&nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; int blackHole = 0;&nbsp; &nbsp; &nbsp; &nbsp; for (long min = 10000; min <= 20000; min += 10000)&nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for (long max = 10000000; max <= 20000000; max += 10000000)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; String from = String.valueOf(min);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; String to = String.valueOf(max);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; long before = 0;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; long after = 0;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; before = System.nanoTime();&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; BigInteger slow = addNumbers(from, to);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; after = System.nanoTime();&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; blackHole += slow.hashCode();&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; System.out.printf("Compute %10d to %10d slow took %8.3f ms\n",&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; min, max, (after - before) / 1e6);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; before = System.nanoTime();&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; BigInteger fast = addNumbersFast(from, to);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; after = System.nanoTime();&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; blackHole += fast.hashCode();&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; System.out.printf(Locale.ENGLISH,&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; "Compute %10d to %10d fast took %8.3f ms\n", min, max,&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; (after - before) / 1e6);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; System.out.println("blackHole " + blackHole);&nbsp; &nbsp; }&nbsp; &nbsp; public static BigInteger addNumbers(String from, String to)&nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; BigInteger total = BigInteger.ZERO;&nbsp; &nbsp; &nbsp; &nbsp; BigInteger startingBoundary = new BigInteger(from);&nbsp; &nbsp; &nbsp; &nbsp; BigInteger finishingBoundary = new BigInteger(to);&nbsp; &nbsp; &nbsp; &nbsp; if (startingBoundary.compareTo(finishingBoundary) < 0)&nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; startingBoundary = new BigInteger(from);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; finishingBoundary = new BigInteger(to);&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; else&nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; finishingBoundary = new BigInteger(from);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; startingBoundary = new BigInteger(to);&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; startingBoundary = startingBoundary.add(BigInteger.ONE);&nbsp; &nbsp; &nbsp; &nbsp; while (startingBoundary.compareTo(finishingBoundary) != 0)&nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; total = total.add(startingBoundary);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; startingBoundary = startingBoundary.add(BigInteger.ONE);&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; return total;&nbsp; &nbsp; }&nbsp; &nbsp; public static BigInteger addNumbersFast(String from, String to)&nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; BigInteger f = new BigInteger(from);&nbsp; &nbsp; &nbsp; &nbsp; BigInteger t = new BigInteger(to);&nbsp; &nbsp; &nbsp; &nbsp; BigInteger sf = computeSum(f);&nbsp; &nbsp; &nbsp; &nbsp; BigInteger st = computeSum(t.subtract(BigInteger.ONE));&nbsp; &nbsp; &nbsp; &nbsp; return st.subtract(sf);&nbsp; &nbsp; }&nbsp; &nbsp; // Compute the sum of 1...n&nbsp; &nbsp; public static BigInteger computeSum(BigInteger n)&nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; BigInteger n1 = n.add(BigInteger.ONE);&nbsp; &nbsp; &nbsp; &nbsp; return n.multiply(n1).divide(BigInteger.valueOf(2));&nbsp; &nbsp; }}较大值的基准结果是显而易见的：Compute&nbsp; &nbsp; &nbsp; 10000 to&nbsp; &nbsp;10000000 slow took&nbsp; 635,506 msCompute&nbsp; &nbsp; &nbsp; 10000 to&nbsp; &nbsp;10000000 fast took&nbsp; &nbsp; 0.089 msCompute&nbsp; &nbsp; &nbsp; 10000 to&nbsp; &nbsp;20000000 slow took 1016,381 msCompute&nbsp; &nbsp; &nbsp; 10000 to&nbsp; &nbsp;20000000 fast took&nbsp; &nbsp; 0.037 msCompute&nbsp; &nbsp; &nbsp; 20000 to&nbsp; &nbsp;10000000 slow took&nbsp; 477,258 msCompute&nbsp; &nbsp; &nbsp; 20000 to&nbsp; &nbsp;10000000 fast took&nbsp; &nbsp; 0.038 msCompute&nbsp; &nbsp; &nbsp; 20000 to&nbsp; &nbsp;20000000 slow took&nbsp; 987,400 msCompute&nbsp; &nbsp; &nbsp; 20000 to&nbsp; &nbsp;20000000 fast took&nbsp; &nbsp; 0.040 ms这些根本就不是一个档次的……

Answer 3

使用total&nbsp;=&nbsp;total.add(startingBoundary);和startingBoundary&nbsp;=&nbsp;startingBoundary.add(new&nbsp;BigInteger("1"));因为add并不与第一个操作数相加，而是返回总和。另外，在开始循环之前，执行以下操作startingBoundary&nbsp;=&nbsp;startingBoundary.add(new&nbsp;BigInteger("1"));以满足必须排除起始边界的条件。作为防御性编码，不要使用等于零，而是使用startingBoundary.compareTo(finishingBoundary)&nbsp;<&nbsp;0