# I am working with fibonacci numbers, where the "n" for the n-th number is in 5-6 digits. how can i reduce the time taken for execution?

go评论55阅读模式

I am working with fibonacci numbers, where the "n" for the n-th number is in 5-6 digits. how can i reduce the time taken for execution?

# 问题

``````import java.util.*;
import java.math.*;
public class FibonacciSumSquares {
private static BigInteger getFibonacciSumSquares(int n) {

if (n &lt;= 1)
return BigInteger.valueOf(n);

BigInteger sum = BigInteger.valueOf(0);
BigInteger a[] = new BigInteger[n];
a[0] = a[1] = BigInteger.ONE;
for (int i = 2; i &lt; n; i++) {
a[i] = a[i - 1].add(a[i - 2]);
a[i] = a[i].pow(2);
}
return sum;

}

public static void main(String[] args) {

Scanner scanner = new Scanner(System.in);

int n = scanner.nextInt();

System.out.println(getFibonacciSumSquares(n));
}
}
``````

In this specific problem, what I had to do is find the Fibonacci numbers, square them, and then find the sum of those squared numbers. Which was fine up until the range limit of the long data type.

Here's what I've got till now... I switched to BigInteger after noticing that the range of long couldn't handle the large Fibonacci numbers, and that did the trick but increased the time complexity exponentially. And since I needed to retain most of the numbers, I needed to make an array for the numbers to store them.

``````import java.util.*;
import java.math.*;
public class FibonacciSumSquares {
private static BigInteger getFibonacciSumSquares(int n) {

if (n &lt;= 1)
return BigInteger.valueOf(n);

BigInteger sum = BigInteger.valueOf(0);
BigInteger a[] = new BigInteger[n];
a[0] = a[1] = BigInteger.ONE;
for (int i = 2; i &lt; n; i++) {
a[i] = a[i - 1].add(a[i - 2]);
a[i] = a[i].pow(2);
}
return sum;

}

public static void main(String[] args) {

Scanner scanner = new Scanner(System.in);

int n = scanner.nextInt();

System.out.println(getFibonacciSumSquares(n));
}
}
``````

After accepting the first answer I ran some stress tests on the code snippet and the correction that was needed was an "=" sign in the code. hope that helps. For more details please refer to the answer's comments.

# 答案1

BigInteger在处理比起Java原始数据类型要慢很多，因此在长范围内请使用原始数据类型。以下是您的代码和结果：

``````public class FibonacciSumSquares {
private static BigInteger getFibonacciSumSquares(int n) {
if (n <= 1)
return BigInteger.valueOf(n);
BigInteger sum = BigInteger.ZERO;
long last = 1, lastTwo = 1, current = 0;
BigInteger lastBigInteger = BigInteger.ONE;
BigInteger lastTwoBigInteger = BigInteger.ONE;
BigInteger currentBigInteger;
boolean isUsePrimary = true;

for (int i = 2; i <= n; i++) {
if (isUsePrimary) {
current = last + lastTwo;
current = current * current;
if (current > (last + lastTwo)) {
lastTwo = last;
last = current;
} else {
isUsePrimary = false;
lastTwoBigInteger = BigInteger.valueOf(lastTwo);
lastBigInteger = BigInteger.valueOf(last);
currentBigInteger = currentBigInteger.pow(2);

}
} else {
currentBigInteger = currentBigInteger.pow(2);
}
}
return sum;
}

public static void main(String[] args) {
long start = System.currentTimeMillis();
System.out.println(getFibonacciSumSquares(10000));
System.out.println("used time(ms): " + (System.currentTimeMillis() - start));
/**
* 在：MacBook Pro (Retina, 15-inch, Mid 2014)
*
* n = 10000
* 811453295998950457153326378602357232029212
* used time(ms): 24
*
* n = 20000
* 1623556274380606238932066737816445867589212
* used time(ms): 32
*
* n = 999999
* 81209566945485034687670444066761210743605656
* used time(ms): 368
*/
}
}
``````

BigInteger runs more slower than java primitive types, so use primitive in long range.
here is my code and result:

``````public class FibonacciSumSquares {
private static BigInteger getFibonacciSumSquares(int n) {
if (n &lt;= 1)
return BigInteger.valueOf(n);
BigInteger sum = BigInteger.ZERO;
long last = 1, lastTwo = 1, current = 0;
BigInteger lastBigInteger = BigInteger.ONE;
BigInteger lastTwoBigInteger = BigInteger.ONE;
BigInteger currentBigInteger;
boolean isUsePrimary = true;
for (int i = 2; i &lt;= n; i++) {
if (isUsePrimary) {
current = last + lastTwo;
current = current * current;
if (current &gt; (last + lastTwo)) {
lastTwo = last;
last = current;
} else {
isUsePrimary = false;
lastTwoBigInteger = BigInteger.valueOf(lastTwo);
lastBigInteger = BigInteger.valueOf(last);
currentBigInteger = currentBigInteger.pow(2);
}
} else {
currentBigInteger = currentBigInteger.pow(2);
}
}
return sum;
}
public static void main(String[] args) {
long start = System.currentTimeMillis();
System.out.println(getFibonacciSumSquares(10000));
System.out.println(&quot;used time(ms): &quot; + (System.currentTimeMillis() - start));
/**
* On: MacBook Pro (Retina, 15-inch, Mid 2014)
*
* n = 10000
* 811453295998950457153326378602357232029212
* used time(ms): 24
*
* n = 20000
* 1623556274380606238932066737816445867589212
* used time(ms): 32
*
* n = 999999
* 81209566945485034687670444066761210743605656
* used time(ms): 368
*/
}
``````

}

• 本文由 发表于 2020年8月26日 16:31:05
• 转载请务必保留本文链接：https://go.coder-hub.com/63593643.html
• java

go 51