How to sum numbers between two boundaries using biginteger

Question

I am trying to sum up all the numbers between 2 given numbers excluding the boundary.. E.g. addNumbers("5", "8") should return 13 since 6+7=13. This is the function I currently have.

 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;

}

The problem is that the while condition seems to be running infinitely despite me changing the value of it. Also when printing out the total object in each loop, it always prints out 0. I know I initialised it to 0 but i was expecting it to change as I am adding to it..

Answer 1

As already mentioned in another answer: Calls like

total.add(startingBoundary);

do not have any observable effect. The add method does not modify the total object. Instead, it returns a new BigInteger object. The reason for that is, more generally, that BigInteger is immutable. This means that the value of a BigInteger object cannot be changed after it has been created. For the reasons, have a look at Why BigInteger in java is designed to be immutable?

Changing the line to

total = total.add(startingBoundary);

will solve this (similarly, for the other lines - for a fixed implementation, see the example below).

---

A side note: Instead of new BigInteger("0") and new BigInteger("1"), you should usually use BigInteger.ZERO and BigInteger.ONE. There is no reason to create new objects for these frequently used values.

---

A possible improvement, though:

Unless the assignment explicitly says that this has to be solved with a loop, there is a far more efficient and elegant solution for this. You can use the Gauß'sche Summenformel (sorry, no English version of that one), which basically states that

The sum of the natural numbers from 1 to n is equal to (n*(n+1))/2

So you can compute these sums directly, for the limits of your range, and then just return the difference between the two.

The following contains a fixed version of your original code, and the alternative implementation, together with a (very basic) "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));
    }

}

The benchmark results for larger values are obvious:

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

These aren't even in the same league...

Answer 2

Note that the use of BigInteger implies that the numbers, and thus also the difference between the two numbers, might be huge. Looping from lower to upper boundary might take ages, literally. Instead, you could use a variant of the closed form sum(1..N) = (N*(N+1))/2. Use it to sum the number from 1 to upper and from 1 to lower, then combine the two to get your desired result.

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

(Note that your loop also seems to return 18 for this example, which seems to be 5+6+7 and thus not what you really wanted.)

Other than your loop, this will also work for truly BigInteger, e.g. the sums (inclusive and exclusive) for lower = 123456789123456789 and upper = 987654321987654321 are 480109740480109740075445815075445815 and 480109740480109738964334703964334705 respectively.

Answer 3

Use

total = total.add(startingBoundary);

and

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

Because add does not add to the first operand, but returns the sum.

Also, before starting the loop, do

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

to satisfy your condition that the starting boundary has to be excluded.

As defensive coding, don't use equals to zero, but use

startingBoundary.compareTo(finishingBoundary) < 0