java - 如何计算出我的系统可以表示的最大斐波那契数？

Question

我被要求找出可以在我的系统上显示的最大斐波那契数。知道该怎么做吗？

Answer 1

确定可以在我的系统上显示的最大斐波那契数

为此，您需要使用 BigInteger

运行此程序，直到您的应用程序因资源不足而停止。

public static void main(String... args) {
    BigInteger a = BigInteger.ONE;
    BigInteger b = BigInteger.ONE;
    String last = null;
    try {
        for (long count = 1; ; count++) {
            BigInteger c = a.add(b);
            last = c.toString();
            a = b;
            b = c;
            if (count % 10000 == 0)
                System.out.println("... " + count);
        }
    } catch (Throwable e) {
        System.out.println("The largest value which was calculated was");
        System.out.println(last);
    }
}

我会先尝试使用少量内存，例如-mx16m

更新：即使有 16 MB 的限制，它也计算了 13K 项并且仍在运行。

Answer 2

intJava中最大的斐波那契数：

public class FibonacciTest
{
    public static void main(String[] args)
    {
        System.out.printf("%d\n", largestFibonacciInt());
    }

    public static int largestFibonacciInt()
    {
        int temp;
        int last = 1;
        int fib = 1;

        while (fib + last > fib) {
            temp = fib;
            fib += last;
            last = temp;
        }

        return fib;
    }
}

您也可以long通过简单地替换所有出现的 来做到这一点int。

Answer 3

If your goal is to find the largest fibonacci number that can be represented as an int in Java, you could simply calculate the next number until it overflows:

public static void main(String[] args) {
    System.out.println("Largest integer Fibonacci number: " + maxFibonacci());
}

public static int maxFibonacci() {
    int n = Integer.MAX_VALUE;
    int fib = 1;
    int temp = 0;

    for (int i = 2; i < n; i++) {
        int last = fib;
        fib += temp;
        if (fib < 0) return last; //overflow, we are done
        temp = last;
    }
    return 0; //unreachable
}

Now obviously, your system is able to calculate a much higher number, for example by using a BigInteger. In that scenario, the limit will be one of:

• processing time
• available memory or
• (if you have a lot of memory and a lot of time) limitation of BigInteger which is backed by an int[] and therefore limited to an array size of 2^31.

---

Finally, it is probably worth saying that your problem can be better solved mathematically.

If you need to find the largest Fibonacci number that is less than a certain number N, you can also use the rounding calculation:

phi^n / sqrt(5) < N

which gives you:

n < log(N x sqrt(5)) / log(phi)

Then you can calculate the right hand side part for your chosen N, round it down to find n, and calculate the corresponding Fibonacci number with:

F(n) = floor(phi^n / sqrt(5))

Answer 4

您可以计算 100K 甚至更多。对于我电脑里的100k，计算结果只需要1.4s。

private static final Map<Integer, BigInteger> fbNumbers = new HashMap<>();

public static void main(String[] args) {
    fbNumbers.put(0, BigInteger.valueOf(1));
    fbNumbers.put(1, BigInteger.valueOf(1));
    long start = System.currentTimeMillis();
    System.out.println(fbCalculationForBigNumbers(100000));
    System.out.println(String.format("%d ms", System.currentTimeMillis() - start));
}

private static BigInteger fbCalculationForBigNumbers(int num) {
    return IntStream.rangeClosed(0, num).mapToObj(i -> fbCalculation(i)).max((x,y) -> x.compareTo(y)).get();
}

private static BigInteger fbCalculation(int num) {

    if (fbNumbers.containsKey(num)) {
        return fbNumbers.get(num);
    }

    BigInteger result = fbCalculation(num - 1).add(fbCalculation(num - 2));
    fbNumbers.put(num, result);
    return result;

}