3

我想计算函数 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;

}

4

3 回答 3

3

尝试使用动态编程方法。不是使用递归，而是从初始情况 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;
}
于 2010-08-08T17:53:00.920 回答
2

尽量不要每次迭代都使用余数，它使用非常慢的除法。

您也不应该在每次迭代时都使用 BigInteger.valueOf()。只需一次将 A 和 B 创建为 BigInteger 并保存它们，无需多次执行。

于 2010-08-08T17:00:34.460 回答
-1

是的，欢迎来到 BigIntegers 的世界。

我记得的一件事是你可以为此做两条路径：

1) BigIntegers 的慢路径 2) 当两个参数都小于 Max Double 时，具有双基本类型的快速路径。

这应该会提高一点速度。

如果可以，请在此处告诉我们进展情况和发布时间。这真的很有趣。

于 2010-08-08T16:50:53.723 回答