BigInteger Performance

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; 
} 

my intention is to add any 2 numbers within the range., let's say 2 to 5(2+3+4+5) or A raise to B. I have other option to get it done within BigInteger, but can anybody say what's wrong with the above snippet in which

1. Its producing longggggggggggggggggggggggggggggggg strange number(instead of original) and
2. Its struggling/juggling so much to increment by 1 as it normally increment outside/without loop?
3. When will it reach just one increment(time or space factor/performance)?

Answer 1

A better way to solve this would be by applying simple arithmetic. We know that:

Sum of natural numbers up to n = n * (n + 1) / 2

Sum of natural numbers from m to n = Sum of natural numbers up to n minus 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.

Demo:

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);
    }
}

Output:

480109740075445815

What is wrong with your code?

1. The loop terminates when A becomes equal to B whereas it should terminate when A becomes greater than B. For this, you can use the terminating condition as i.compareTo(B.add(BigInteger.ONE)) != 0.
2. A BigInteger is an immutable arbitrary-precision integer. Therefore, i.add(BigInteger.ONE) won't modify the value of i. You need to assign the result to i i.e. i = i.add(BigInteger.ONE) in order to increment the value referenced by i by one.
3. You have started with a value 1 (i.e. BigInteger res=BigInteger.ONE) instead of 0.

Correct code:

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;
    }
}

Output:

14

Although you can get the correct result after correcting your code this way, it's performance will be extremely bad.

Answer 2

my option for A raises to B without generating multiple instances

public static BigInteger find(BigInteger A,BigInteger B)
    {
        BigInteger res=BigInteger.ONE;
        int b=B.intValue();
        for(int i=1;i<=b;i++)
            res=res.multiply(A);
        return res;
    }

Answer 3

It seems there is an issue with storing value of the loop variable after increment.

The sum of arithmetic progression should include both A and 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; 
}

Tests:

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

Output:

14
105350

Answer 4

The sum of all integers in a range can be calculated as the average value multiplied by the number of values, aka the "count".

If A and B are both inclusive, as indicated by the "2 to 5(2+3+4+5)" text in the question, then we have:

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

In Java code, using BigInteger, that means:

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