优化上非常大的数字运算

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

}

来源

2010-08-08 user414442

Ci的本质是什么;它的长度是多少？它是否是随机的？它是否包含很多零，相似的值或类似的模式？如果是这样，算法的改变可能会加快速度。 – mvds 2010-08-08 17:07:26

似乎公式中缺少一些括号。 – starblue 2010-08-09 09:16:19

-1

呀，欢迎BigIntegers的世界。

有一件事我记得的是，你能做到这两条路径：

1）BigIntegers 2）双原始类型的快速路径时，双方的观点都小于最大双A慢速路径。

这应该提高一点速度。

请告诉我们这是怎么回事，如果可以的话，张贴时间。这真的很有趣。

来源

2010-08-08 16:50:53 Rui

尝试不使用其余的每个迭代，它使用的分区是很慢很慢。

你也不应该在每次迭代中使用BigInteger.valueOf（）。 只有一次创建A和B作为BigIntegers，并将它们保存，不需要多做更多次。

来源

2010-08-08 17:00:34

尝试使用动态编程方法。不是使用递归，而是从最初的情况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-08 17:53:00

优化上非常大的数字运算

回答

相关问题