Optimise arithmetic operations on very large numbers

Question

I want to compute the function H(n) where

H(0)=0;
H(i)=H(i-1)×A+Ci mod B;

10<=A,B<=10^15;

C is an array of n elements

But it is taking too much time...any better way of doing this..Please help

public BigInteger H(int no)
  {  

        if(no>0)
        {
                bi=H(no-1);
                bi=bi.multiply(BigInteger.valueOf(A));
                bi=bi.add(BigInteger.valueOf(c[no-1]));
                bi=bi.remainder(BigInteger.valueOf(B));
               return bi;
        }

        return BigInteger.ZERO;
   }

Answer 1

Yeah, welcome to the world of BigIntegers.

One thing I remember is that you can do two paths for this:

1) A slow path with BigIntegers 2) A fast path with double primitive types when both the arguments are less than Max Double.

That should pump up the speed a little bit.

Tell us here how it went and post times if you can. This is really interesting.

Answer 2

Try not using the remainder every iteration, it uses division which is VERY slow.

You should also not use BigInteger.valueOf() every iteration. Only create A and B as BigIntegers one time and save them, there is no need for doing it more times.

Answer 3

Try using a dynamic programming approach. Rather than using recursion, loop starting at the initial case H(0) and moving up from there. Example:

public static BigInteger H(BigInteger[] c, int no, BigInteger A, BigInteger B) {

    if (c.length < no - 1) {
        throw new IllegalArgumentException("no is too large");
    }

    BigInteger bi = BigInteger.ZERO;  // Initial case H(0) = 0

    for (int i = 1; i <= no; i++) {   // From H(1) -> H(no)
        bi = bi.multiply(A).add(c[i - 1]).remainder(B);
    }

    return bi;
}