Optimization of arithmetic operations on very large numbers

Question

I want to calculate the function H (n) where

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

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

C - an array of n elements

The following code takes too much time ... the best way to do this?

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

Try a dynamic programming approach. Instead of using recursion, the loop starts with the initial case H (0) and moves 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;
}

Answer 2

Try not to use the remainder at each iteration , it uses the division VERY slowly.

BigInteger.valueOf() . A B BigIntegers , .

Answer 3

, BigIntegers.

, , , :

1) BigIntegers 2) , Max Double.

.

, , , . .