我计算非常大的斐波那契数模的算法太慢
目标是计算 F(n) 模 m（m 最大为 10 的 5 次方），其中 n 可能非常大：最大为 10 的 18 次方。
我的算法太慢了。
我的方法：计算并存储最多 m 的所有斐波那契数，然后迭代该数组并对斐波那契数应用模。
一旦找到皮萨诺周期的长度，我可以使用这个长度来计算任何的模F(n)
我的代码：
import java.math.BigInteger;
import java.util.*;
public class FibonacciAgain {
private static ArrayList<BigInteger> calc_fib() {
ArrayList<BigInteger> fib = new ArrayList<>();
fib.add(BigInteger.ZERO);
fib.add(BigInteger.ONE);
for (int i = 2; i <= 100000; i++) {
fib.add(fib.get(i - 2).add(fib.get(i - 1)));
}
return fib;
}
private static long calculatePeriod(ArrayList<BigInteger> fib, long modulo) {
long periodLength = 0;
boolean periodFound = false;
long[] period = new long[1000000];
period[0] = 0;
period[1] = 1;
period[2] = 1;
int i = 3;
while (!periodFound) {
//period[i] = fib.get(i)
//period[i]= fib.get(i).divide(new BigInteger(String.valueOf(i))).longValue();
//System.out.println("Fib at " + i + ": " + fib.get(i));
period[i] = fib.get(i).mod(new BigInteger(String.valueOf(modulo))).longValue();
//System.out.println("1:" + period[i]);
//System.out.println("2:" + period[i - 1]);
// System.out.println("3: " + period[i - 2]);
if (i == 100000){
periodFound = true;
periodLength = i - 1;
}
// if (period[i] == 1 && period[i - 1] == 1 && period[i - 2] == 0) {
if (period[i - 1] == 1 && period[i - 2] == 0) {
periodFound = true;
periodLength = i - 2;
//System.out.println("found");
}
i++;
}
//System.out.println("Period Length:" + periodLength);
return periodLength;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
long n = scanner.nextLong();
long m = scanner.nextLong();
}
}
有什么建议，如何让它更快？
白猪掌柜的2回答
-
繁花不似锦
没有必要使用，BigInteger因为：1*2*3*4*...*N mod M 1+2+3+4+...+N mod M是相同的(...(((1*2 mod M)*3 mod M)*4 mod M)...*N mod M) (...(((1+2 mod M)+3 mod M)+4 mod M)...+N mod M)这应该会加速很多......从（假设的Karatsuba乘法）O(3*N*(n^log2(3)))和/或加法O(N*n) 到线性O(N)，其中n乘数/加法的位宽成比例，并且还有更好的恒定时间......IIRC 那里还有快速斐波那契计算的公式（转换O(N)成接近的东西）O(log(N))这里是朴素 ( ) 和快速（使用 2x2 矩阵平方的幂）算法的C++示例：modfib0modfib1//---------------------------------------------------------------------------int modfib0(int n,int m) { for (int i=0,x0=0,x1=1;;) { if (i>=n) return x1; x0+=x1; x0%=m; i++; if (i>=n) return x0; x1+=x0; x1%=m; i++; } }//---------------------------------------------------------------------------// matrix 2x2: 0 1// 2 3void modmul2x2(int *c,int *a,int *b,int m) // c[4] = a[4]*b[4] %m { int t[4]; t[0]=((a[0]*b[0])+(a[1]*b[2]))%m; t[1]=((a[0]*b[1])+(a[1]*b[3]))%m; t[2]=t[1]; // result is symetric so no need to compute: t[2]=((a[2]*b[0])+(a[3]*b[2]))%m; t[3]=((a[2]*b[1])+(a[3]*b[3]))%m; c[0]=t[0]; c[1]=t[1]; c[2]=t[2]; c[3]=t[3]; }void modpow2x2(int *c,int *a,int n,int m) // c[4] = a[4]^n %m { int t[4]; t[0]=a[0]; c[0]=1; t[1]=a[1]; c[1]=0; t[2]=a[2]; c[2]=0; t[3]=a[3]; c[3]=1; for (;;) { if (int(n&1)!=0) modmul2x2(c,c,t,m); n>>=1; if (!n) break; modmul2x2(t,t,t,m); } }int modfib1(int n,int m) { if (n<=0) return 0; int a[4]={1,1,1,0}; modpow2x2(a,a,n,m); return a[0]; }//---------------------------------------------------------------------------请注意，为了符合您的限制，所使用的int变量必须至少为 64 位宽！我在旧的 32 位环境中，不想用 bigint 类破坏代码，所以我只用这个进行测试：int x,m=30000,n=0x7FFFFFFF;x=modfib0(n,m);x=modfib1(n,m);结果如下：[10725.614 ms] modfib0:17301 O(N)[ 0.002 ms] modfib1:17301 O(log2(N))正如你所看到的，快速算法比线性算法快得多...但是对于 Windows 环境来说，测量的时间太短了，而且它的大部分时间很可能是开销而不是函数本身，所以我认为即使是它也应该足够快因为我估计n=10^18它的复杂性是：O(log2(N))64-31 = 33 bits0.002 ms * 33 = 0.066 ms因此，64 位计算的执行时间应该远远低于0.1 ms我的机器（AMD A8-5500 3.2 GHz）上的执行时间，我认为这是可以接受的......64 位的线性算法如下：10.725614 s * 2^33 = 865226435999039488 s = 27.417*10^9 years但正如你所看到的，你早在这之前就已经衰老了...... -
慕仙森
为了帮助加快速度，我修改了你的calculatePeriod()方法。我做了以下几件事。更改了要记忆的 fib 缓存。它是动态计算的并添加到列表中。如果您反复提示输入值，这会派上用场。那么就不需要重新计算缓存了。我还添加了一个映射来存储fibFirst斐波那契及其模数。我将您的 BigInteger 调用从 更改new BigInteger(String.valueOf(modulo))为BigInteger.valueOf(modulo)。不确定它是否更快，但更干净。最后，我移动了重新计算但在任何循环之外没有更改的值。这是修改后的方法： static Map<Long, Map<Long,Long>> fibFirstMap = new HashMap<>(); static List<BigInteger> fibs = new ArrayList<>() { { add(BigInteger.ZERO); add(BigInteger.ONE); add(BigInteger.ONE); add(BigInteger.TWO); } }; private static long calculateFirst(long nthfib, long modulo) { long fibFirst = fibFirstMap.computeIfAbsent(nthfib, k -> new HashMap<>()).getOrDefault( modulo, -1L); if (fibFirst > 0L) { return fibFirst; } long periodLength = 0; boolean periodFound = false; long[] period = new long[1000000]; period[0] = 0; period[1] = 1; period[2] = 1; int i = 3; BigInteger cons = BigInteger.valueOf(modulo); BigInteger nextFib; while (!periodFound) { if (i >= fibs.size()) { fibs.add(fibs.get(i - 2).add(fibs.get(i - 1))); } nextFib = fibs.get(i); period[i] = nextFib.mod(cons).longValue(); if (i == 100000) { periodFound = true; periodLength = i - 1; } else if (period[i - 1] == 1 && period[i - 2] == 0) { periodFound = true; periodLength = i - 2; } i++; } fibFirst = nthfib % periodLength; fibFirstMap.get(nthfib).put(modulo, fibFirst); return fibFirst; }更好的方法可能是研究摆脱BigInteger所建议的方法，并寻求基于数论进步的计算改进。
随时随地看视频慕课网APP
相关分类
Java