目標是計算 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 回答
繁花不似錦
TA貢獻1851條經驗 獲得超4個贊
沒有必要使用，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 3
void 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 bits
0.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
但正如你所看到的，你早在這之前就已經衰老了......
慕仙森
TA貢獻1827條經驗 獲得超8個贊
為了幫助加快速度，我修改了你的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所建議的方法，并尋求基于數論進步的計算改進。
添加回答
舉報
0/150
提交
取消