java - 优化非常大的数字的算术运算

Question

我想计算函数 H(n)哪里

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

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

C是n个元素的数组

下面的代码太花时间了……还有更好的方法吗？

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

尝试使用动态规划方法。不是使用递归，而是从初始情况 H(0) 开始循环并从那里向上移动。示例:

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