java 使斐波那契更快

Making Fibonacci faster

提问by alainlompo

I was required to write a simple implementation of Fibonacci's algorithm and then to make it faster.

我被要求写一个简单的斐波那契算法实现，然后让它更快。

Here is my initial implementation

这是我的初步实现

public class Fibonacci {

    public static long getFibonacciOf(long n) {
        if (n== 0) {
            return 0;
        } else if (n == 1) {
            return 1;
        } else {
            return getFibonacciOf(n-2) + getFibonacciOf(n-1);
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner (System.in);
        while (true) {
            System.out.println("Enter n :");
            long n = scanner.nextLong();
            if (n >= 0) {
                long beginTime = System.currentTimeMillis();
                long fibo = getFibonacciOf(n);
                long endTime = System.currentTimeMillis();

                long delta = endTime - beginTime;

                System.out.println("F(" + n + ") = " + fibo + " ... computed     in " + delta + " milliseconds");
            } else {
                break;

            }
        }

    }

}

As you can see I am using System.currentTimeMillis() to get a simple measure of the time elapsed while computed Fibonacci.

如您所见，我正在使用 System.currentTimeMillis() 来获取计算斐波那契数列所用时间的简单度量。

This implementation get rapidly kind of exponentially slowas you can see on the following picture

正如您在下图中看到的那样，此实现会迅速呈指数级缓慢

So I've got a simple optimisation idea. To put previous values in a HashMap and instead of re-computing them each time, to simply take them back from the HashMap if they exist. If they don't exist, we then put them in the HashMap.

所以我有一个简单的优化想法。将以前的值放在 HashMap 中，而不是每次都重新计算它们，如果它们存在，只需从 HashMap 中取回它们。如果它们不存在，我们将它们放入 HashMap 中。

Here is the new version of the code

这是代码的新版本

public class FasterFibonacci {

    private static Map<Long, Long> previousValuesHolder;
    static {
        previousValuesHolder = new HashMap<Long, Long>();
        previousValuesHolder.put(Long.valueOf(0), Long.valueOf(0));
        previousValuesHolder.put(Long.valueOf(1), Long.valueOf(1));
    }
    public static long getFibonacciOf(long n) {
        if (n== 0) {

            return 0;
        } else if (n == 1) {
            return 1;
        } else {
            if (previousValuesHolder.containsKey(Long.valueOf(n))) {
                return previousValuesHolder.get(n);
            } {

                long newValue = getFibonacciOf(n-2) + getFibonacciOf(n-1);
                previousValuesHolder.put(Long.valueOf(n),     Long.valueOf(newValue));
                return newValue;
            }

        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner (System.in);
        while (true) {
            System.out.println("Enter n :");
            long n = scanner.nextLong();
            if (n >= 0) {
                long beginTime = System.currentTimeMillis();
                long fibo = getFibonacciOf(n);
                long endTime = System.currentTimeMillis();

                long delta = endTime - beginTime;

                System.out.println("F(" + n + ") = " + fibo + " ... computed     in " + delta + " milliseconds");
            } else {
                break;

            }
        }

    }

This change makes the computing extremely fast. I computes all the values from 2 to 103 in no time at all and I get a longoverflow at F(104) (Gives me F(104) = -7076989329685730859, which is wrong). I find it so fast that **I wonder if there is any mistakes in my code (Thank your checking and let me know please) **. Please take a look at the second picture:

这种变化使计算速度极快。我立即计算了从 2 到 103 的所有值，并且在 F(104) 处出现了长时间溢出（给了我 F(104) = -7076989329685730859，这是错误的）。我发现它太快了 ** 我想知道我的代码中是否有任何错误（感谢您的检查并让我知道）**。请看第二张图：

Is my faster fibonacci's algorithm's implementation correct (It seems it is to me because it gets the same values as the first version, but since the first version was too slow I could not compute bigger values with it such as F(75))? What other way can I use to make it faster? Or is there a better way to make it faster? Also how can I compute Fibonacci for greater values (such as 150, 200) without getting a **longoverflow**? Though it seems fast I would like to push it to the limits. I remember Mr Abrash saying 'The best optimiser is between your two ears', so I believe it can still be improved. Thank you for helping

我的更快的斐波那契算法的实现是否正确（对我来说似乎是因为它获得与第一个版本相同的值，但由于第一个版本太慢，我无法用它计算更大的值，例如 F(75)）？我还可以使用什么其他方法来使其更快？或者有没有更好的方法让它更快？另外，如何计算更大的值（例如 150、200）的斐波那契数，而不会出现 **long溢出**？虽然看起来很快，但我想把它推到极限。我记得 Abrash 先生说过'最好的优化器在你的两只耳朵之间'，所以我相信它仍然可以改进。谢谢你的帮忙

[Edition Note:]Though thisquestion adresses one of the main point in my question, you can see from above that I have additionnal issues.

[编辑注：]虽然这个问题解决了我问题中的一个要点，但您可以从上面看到我还有其他问题。

采纳答案by user2736738

Dynamic programming

动态规划

Idea:Instead of recomputing the same value multiple times you just store the value calculated and use them as you go along.

想法：不是多次重新计算相同的值，您只需存储计算出的值并在进行过程中使用它们。

f(n)=f(n-1)+f(n-2)with f(0)=0,f(1)=1. So at the point when you have calculated f(n-1) you can easily calculate f(n) if you store the values of f(n) and f(n-1).

f(n)=f(n-1)+f(n-2)f(0)=0,f(1)=1。因此，在计算 f(n-1) 时，如果存储 f(n) 和 f(n-1) 的值，则可以轻松计算 f(n)。

Let's take an array of Bignums first. A[1..200]. Initialize them to -1.

让我们先来看看 Bignum 的数组。A[1..200]。将它们初始化为 -1。

Pseudocode

伪代码

fact(n)
{
if(A[n]!=-1) return A[n];
A[0]=0;
A[1]=1;
for i=2 to n
  A[i]= addition of A[i],A[i-1];
return A[n]
}

This runs in O(n)time. Check it out yourself.

这在O(n)时间内运行。自己检查一下。

This technique is also called memoization.

这种技术也称为记忆。

The IDEA

想法

Dynamic programming(usually referred to as DP ) is a very powerful technique to solve a particular class of problems. It demands very elegant formulation of the approach and simple thinking and the coding part is very easy. The idea is very simple, If you have solved a problem with the given input, then save the result for future reference, so as to avoid solving the same problem again.. shortly 'Remember your Past'.

动态规划（通常称为 DP）是一种非常强大的技术，可以解决特定类别的问题。它需要非常优雅的方法表述和简单的思维，编码部分非常简单。这个想法很简单，如果你已经用给定的输入解决了一个问题，那么保存结果以备将来参考，以免再次解决同样的问题..简短的“记住你的过去”。

If the given problem can be broken up in to smaller sub-problems and these smaller subproblems are in turn divided in to still-smaller ones, and in this process, if you observe some over-lappping subproblems, then its a big hint for DP. Also, the optimal solutions to the subproblems contribute to the optimal solution of the given problem ( referred to as the Optimal Substructure Property).

如果给定的问题可以分解成更小的子问题，而这些更小的子问题又会被分解成更小的问题，在这个过程中，如果你观察到一些over-lappping subproblems，那么这对 DP 来说是一个很大的提示。此外，子问题的最优解有助于给定问题的最优解（称为Optimal Substructure Property）。

There are two ways of doing this.

有两种方法可以做到这一点。

1.) Top-Down : Start solving the given problem by breaking it down. If you see that the problem has been solved already, then just return the saved answer. If it has not been solved, solve it and save the answer. This is usually easy to think of and very intuitive. This is referred to as Memoization. (I have used this idea).

2.) Bottom-Up : Analyze the problem and see the order in which the sub-problems are solved and start solving from the trivial subproblem, up towards the given problem. In this process, it is guaranteed that the subproblems are solved before solving the problem. This is referred to as Dynamic Programming. (MinecraftShamrockused this idea)

1.) 自上而下：通过分解问题开始解决给定的问题。如果您发现问题已经解决，则只需返回保存的答案即可。如果还没有解决，解决它并保存答案。这通常很容易想到并且非常直观。这称为记忆化。（我已经使用了这个想法）。

2.) 自下而上：分析问题并查看子问题的解决顺序，然后从琐碎的子问题开始解决，直至解决给定的问题。在这个过程中，保证在解决问题之前先解决子问题。这称为动态规划。（MinecraftShamrock使用这个想法）

---

---

There's more!

还有更多！

(Other ways to do this)

（其他方法可以做到这一点）

Look our quest to get a better solution doesn't end here. You will see a different approach-

看来我们对获得更好解决方案的追求并没有就此结束。你会看到一种不同的方法——

If you know how to solve recurrence relationthen you will find a solution to this relation

如果您知道如何解决，recurrence relation那么您将找到此关系的解决方案

f(n)=f(n-1)+f(n-2) given f(0)=0,f(1)=1

f(n)=f(n-1)+f(n-2) given f(0)=0,f(1)=1

You will arrive at the formula after solving it-

解决后你会得到公式 -

f(n)= (1/sqrt(5))((1+sqrt(5))/2)^n - (1/sqrt(5))((1-sqrt(5))/2)^n

f(n)= (1/sqrt(5))((1+sqrt(5))/2)^n - (1/sqrt(5))((1-sqrt(5))/2)^n

which can be written in more compact form

可以写成更紧凑的形式

f(n)=floor((((1+sqrt(5))/2)^n) /sqrt(5) + 1/2)

f(n)=floor((((1+sqrt(5))/2)^n) /sqrt(5) + 1/2)

Complexity

复杂

You can get the power a number in O(logn)operations. You have to learn the Exponentiation by squaring.

您可以在O(logn)操作中获得一个数字的幂。你必须通过平方来学习幂运算。

EDIT: It is good to point out that this doesn't necessarily mean that the fibonacci number can be found in O(logn). Actually the number of digits we need to calculate frows linearly. Probably because of the position where I stated that it seems to claim the wrong idea that factorial of a number can be calculated in O(logn) time. [Bakurui,MinecraftShamrock commented on this]

编辑：很好地指出，这并不一定意味着可以在 O(logn) 中找到斐波那契数。实际上我们需要计算的数字是线性排列的。可能是因为我声明的立场似乎声称错误的想法是可以在 O(logn) 时间内计算一个数字的阶乘。[Bakurui，MinecraftShamrock 对此发表了评论]

回答by MinecraftShamrock

If you need to compute nth fibonacci numbers very frequently I suggest using amalsom's answer.

如果您需要非常频繁地计算第n个斐波那契数，我建议使用 amalsom 的答案。

But if you want to compute a very big fibonacci number, you will run out of memory because you are storing allsmaller fibonacci numbers. The following pseudocode only keeps the last two fibonacci numbers in memory, i.e. it requires much less memory:

但是如果你想计算一个非常大的斐波那契数，你就会耗尽内存，因为你要存储所有较小的斐波那契数。下面的伪代码只在内存中保留最后两个斐波那契数，即它需要更少的内存：

fibonacci(n) {
    if n = 0: return 0;
    if n = 1: return 1;
    a = 0;
    b = 1;
    for i from 2 to n: {
        sum = a + b;
        a = b;
        b = sum;
    }
    return b;
}

Analysis
This can compute very high fibonacci numbers with quite low memory consumption: We have O(n) timeas the loop repeats n-1times. The space complexity is interesting as well: The nth fibonacci number has a length of O(n), which can easily be shown:
F_n<= 2 * F_n-1
Which means that the nth fibonacci number is at most twice as big as its predecessor. Doubling a number in binary is equivalent with a single left-shift, which increases the number of necessary bits by one. So representing the nth fibonacci number takes at most O(n) space. We have at most three successive fibonacci numbers in memory which makes O(n) + O(n-1) + O(n-2) = O(n) total space consumption. In contrast to this the memoization algorithm always keeps the first n fibonacci numbers in memory, which makes O(n) + O(n-1) + O(n-2) + ... + O(1) = O(n^2)space consumption.

分析
这可以以非常低的内存消耗计算非常高的斐波那契数：我们有O(n) 时间，因为循环重复n-1次。空间复杂度也很有趣：第 n 个斐波那契数的长度为 O(n)，可以很容易地表示出来：
F _n<= 2 * F _n-1
这意味着第 n 个斐波那契数最多是原来的两倍作为它的前身。将二进制数加倍等同于一次左移，这会将必要的位数增加一。所以表示第 n 个斐波那契数最多需要 O(n) 空间。我们在内存中最多有三个连续的斐波那契数，这使得 O(n) + O(n-1) + O(n-2) = O(n) 总空间消耗. 与此相反，记忆算法总是在内存中保留前 n 个斐波那契数，这使得 O(n) + O(n-1) + O(n-2) + ... + O(1) = O(n ^2)空间消耗。

So which way should one use?
The only reason to keep all lower fibonacci numbers in memory is if you need fibonacci numbers very frequently. It is a question of balancing time with memory consumption.

那么应该使用哪种方式呢？
将所有较低的斐波那契数保留在内存中的唯一原因是如果您非常频繁地需要斐波那契数。这是一个平衡时间和内存消耗的问题。

回答by David E Speyer

Get away from the Fibonacci recursion and use the identities

远离斐波那契递归并使用恒等式

(F(2n), F(2n-1)) = (F(n)^2 + 2 F(n) F(n-1), F(n)^2+F(n-1)^2)
(F(2n+1), F(2n)) = (F(n+1)^2+F(n)^2, 2 F(n+1) F(n) - F(n)^2)

This allows you to compute (F(m+1), F(m)) in terms of (F(k+1), F(k)) for k half the size of m. Written iteratively with some bit shifting for division by 2, this should give you the theoretical O(log n) speed of exponentiation by squaring while staying entirely within integer arithmetic. (Well, O(log n) arithmetic operations. Since you will be working with numbers with roughly n bits, it won't be O(log n) time once you are forced to switch to a large integer library. After F(50), you will overflow the integer data type, which only goes up to 2^(31).)

这允许您根据 (F(k+1), F(k)) 计算 (F(m+1), F(m)) ，其中 k 的大小是 m 的一半。用一些位移位迭代地写成除以 2，这应该给你理论上的 O(log n) 平方取幂速度，同时完全保持在整数算术范围内。（好吧，O(log n) 算术运算。由于您将使用大约 n 位的数字，因此一旦您被迫切换到大型整数库，就不会是 O(log n) 时间。在 F(50 )，您将溢出整数数据类型，最多只能达到 2^(31)。）

(Apologies for not remembering Java well enough to implement this in Java; anyone who wants to is free to edit it in.)

（抱歉没有很好地记住 Java 以在 Java 中实现它；任何想要的人都可以自由编辑它。）

回答by coderz

• Fibonacci(0) = 0
• Fibonacci(1) = 1
• Fibonacci(n) = Fibonacci(n - 1) + Fibonacci(n - 2), when n >= 2

• 斐波那契(0) = 0
• 斐波那契(1) = 1
• Fibonacci(n) = Fibonacci(n - 1) + Fibonacci(n - 2)，当 n >= 2

Usually there are 2 ways to calculate Fibonacci number:

通常有两种计算斐波那契数的方法：

1. Recursion:

   public long getFibonacci(long n) {
     if(n <= 1) {
       return n;
     } else {
       return getFibonacci(n - 1) + getFibonacci(n - 2);
     }
   }
   

   This way is intuitive and easy to understand, while because it does not reuse calculated Fibonacci number, the time complexity is about O(2^n), but it does not store calculated result, so it saves space a lot, actually the space complexity is O(1).

2. Dynamic Programming:

   public long getFibonacci(long n) {
     long[] f = new long[(int)(n + 1)];
     f[0] = 0;
     f[1] = 1;
     for(int i=2;i<=n;i++) {
       f[i] = f[i - 1] + f[i - 2];
     }
     return f[(int)n];
   }
   

   This Memoizationway calculated Fibonacci numbers and reuse them when calculate next one. The time complexity is pretty good, which is O(n), while space complexity is O(n). Let's investigate whether the space complexity can be optimized... Since f(i)only requires f(i - 1)and f(i - 2), there is not necessary to store all calculated Fibonacci numbers.

   The more efficient implementation is:

   public long getFibonacci(long n) {
     if(n <= 1) {
       return n;
     }
     long x = 0, y = 1;
     long ans;
     for(int i=2;i<=n;i++) {
       ans = x + y;
       x = y;
       y = ans;
     }
     return ans;
   }
   

   With time complexity O(n), and space complexity O(1).

1. 递归：

   public long getFibonacci(long n) {
     if(n <= 1) {
       return n;
     } else {
       return getFibonacci(n - 1) + getFibonacci(n - 2);
     }
   }
   

   这种方式非常直观，易于理解，同时因为它不重用计算Fibonacci数，时间复杂度约为O(2^n)，但它不会存储计算出的结果，因此节省了空间很多，其实空间复杂度O(1)。

2. 动态规划：

   public long getFibonacci(long n) {
     long[] f = new long[(int)(n + 1)];
     f[0] = 0;
     f[1] = 1;
     for(int i=2;i<=n;i++) {
       f[i] = f[i - 1] + f[i - 2];
     }
     return f[(int)n];
   }
   

   这种记忆方式计算斐波那契数，并在计算下一个时重复使用它们。时间复杂度非常好，即O(n)，而空间复杂度为O(n)。让我们来研究一下空间复杂度是否可以优化... 由于f(i)只需要f(i - 1)和f(i - 2)，所以没有必要存储所有计算出的斐波那契数。

   更有效的实现是：

   public long getFibonacci(long n) {
     if(n <= 1) {
       return n;
     }
     long x = 0, y = 1;
     long ans;
     for(int i=2;i<=n;i++) {
       ans = x + y;
       x = y;
       y = ans;
     }
     return ans;
   }
   

   有时间复杂度O(n)，还有空间复杂度O(1)。

Added:Since Fibonacci number increase amazing fast, longcan only handle less than 100 Fibonacci numbers. In Java, we can use BigIntegerto store more Fibonacci numbers.

补充：由于斐波那契数增长惊人之快，long只能处理不到100个斐波那契数。在 Java 中，我们可以使用BigInteger来存储更多的斐波那契数。

回答by MushinNoShin

Precompute a large number of fib(n)results, and store them as a lookup table inside your algorithm. Bam, free "speed"

预先计算大量fib(n)结果，并将它们存储为算法中的查找表。砰，自由的“速度”

Now if you need to compute fib(101)and you already have fibs 0 to 100 stored, this is just like trying to compute fib(1).

现在，如果您需要计算fib(101)并且您已经存储了 fibs 0 到 100，这就像尝试计算fib(1).

Chances are this isn't what this homework is looking for, but it's a completely legit strategy and basically the idea of caching extracted further away from running the algorithm. If you know you're likely to be computing the first 100 fibs often and you need to do it really really fast, there's nothing faster than O(1). So compute those values entirely out of band and store them so they can be looked up later.

很有可能这不是本作业所要寻找的，但它是一个完全合法的策略，基本上是从运行算法更远的地方提取缓存的想法。如果你知道你可能经常计算前 100 个 fibs 并且你需要非常快地完成它，那么没有比 O(1) 更快的了。因此，完全在带外计算这些值并存储它们，以便以后查找。

Of course, cache values as you compute them too :) Duplicated computation is waste.

当然，在计算它们时也缓存值 :) 重复计算是浪费。

回答by nazar_art

Here is snipped of code with iterative approach instead of recursion.

这是使用迭代方法而不是递归的代码片段。

Output example:

输出示例：

Enter n: 5
F(5) = 5 ... computed in 1 milliseconds
Enter n: 50
F(50) = 12586269025 ... computed in 0 milliseconds
Enter n: 500
F(500) = ...4125 ... computed in 2 milliseconds
Enter n: 500
F(500) = ...4125 ... computed in 0 milliseconds
Enter n: 500000
F(500000) = ...453125 ... computed in 5,718 milliseconds
Enter n: 500000
F(500000) = ...453125 ... computed in 0 milliseconds

Some pieces of results are omitted with ...for better view.

...为了更好地查看，省略了一些结果。

Code snippet:

代码片段：

public class CachedFibonacci {
    private static Map<BigDecimal, BigDecimal> previousValuesHolder;
    static {
        previousValuesHolder = new HashMap<>();
        previousValuesHolder.put(BigDecimal.ZERO, BigDecimal.ZERO);
        previousValuesHolder.put(BigDecimal.ONE, BigDecimal.ONE);
    }

    public static BigDecimal getFibonacciOf(long number) {
        if (0 == number) {
            return BigDecimal.ZERO;
        } else if (1 == number) {
            return BigDecimal.ONE;
        } else {
            if (previousValuesHolder.containsKey(BigDecimal.valueOf(number))) {
                return previousValuesHolder.get(BigDecimal.valueOf(number));
            } else {
                BigDecimal olderValue = BigDecimal.ONE,
                        oldValue = BigDecimal.ONE,
                        newValue = BigDecimal.ONE;

                for (int i = 3; i <= number; i++) {
                    newValue = oldValue.add(olderValue);
                    olderValue = oldValue;
                    oldValue = newValue;
                }
                previousValuesHolder.put(BigDecimal.valueOf(number), newValue);
                return newValue;
            }
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (true) {
            System.out.print("Enter n: ");
            long inputNumber = scanner.nextLong();
            if (inputNumber >= 0) {
                long beginTime = System.currentTimeMillis();
                BigDecimal fibo = getFibonacciOf(inputNumber);
                long endTime = System.currentTimeMillis();
                long delta = endTime - beginTime;

                System.out.printf("F(%d) = %.0f ... computed in %,d milliseconds\n", inputNumber, fibo, delta);
            } else {
                System.err.println("You must enter number > 0");
                System.out.println("try, enter number again, please:");
                break;
            }
        }
    }
}

This approach runs much faster than the recursive version.

这种方法比递归版本运行得快得多。

In such a situation, the iterative solution tends to be a bit faster, because each recursive method call takes a certain amount of processor time. In principle, it is possible for a smart compiler to avoid recursive method calls if they follow simple patterns, but most compilers don't do that. From that point of view, an iterative solution is preferable.

在这种情况下，迭代解决方案往往会快一些，因为每个递归方法调用都需要一定的处理器时间。原则上，如果遵循简单的模式，智能编译器可以避免递归方法调用，但大多数编译器不会这样做。从这个角度来看，迭代解决方案是可取的。

回答by abligh

Here's a way of provably doing it in O(log n) (as the loop runs log ntimes):

这是一种可证明在O(log n) 中执行此操作的方法（作为循环运行log n时间）：

/* 
 * Fast doubling method
 * F(2n) = F(n) * (2*F(n+1) - F(n)).
 * F(2n+1) = F(n+1)^2 + F(n)^2.
 * Adapted from:
 *    https://www.nayuki.io/page/fast-fibonacci-algorithms
 */
private static long getFibonacci(int n) {
    long a = 0;
    long b = 1;
    for (int i = 31 - Integer.numberOfLeadingZeros(n); i >= 0; i--) {
        long d = a * ((b<<1) - a);
        long e = (a*a) + (b*b);
        a = d;
        b = e;
        if (((n >>> i) & 1) != 0) {
            long c = a+b;
            a = b;
            b = c;
        }
    }
    return a;
}

I am assuming here (as is conventional) that one multiply / add / whatever operation is constant time irrespective of number of bits, i.e. that a fixed-length data type will be used.

我在这里假设（按照惯例）无论位数如何，乘法/加法/任何操作都是恒定时间，即将使用固定长度的数据类型。

This pageexplains several methods of which this is the fastest. I simply translated it away from using BigIntegerfor readability. Here's the BigIntegerversion:

本页解释了几种方法，其中这是最快的。我只是BigInteger为了可读性而将其翻译成使用。这是BigInteger版本：

/* 
 * Fast doubling method.
 * F(2n) = F(n) * (2*F(n+1) - F(n)).
 * F(2n+1) = F(n+1)^2 + F(n)^2.
 * Adapted from:
 *    http://www.nayuki.io/page/fast-fibonacci-algorithms
 */
private static BigInteger getFibonacci(int n) {
    BigInteger a = BigInteger.ZERO;
    BigInteger b = BigInteger.ONE;
    for (int i = 31 - Integer.numberOfLeadingZeros(n); i >= 0; i--) {
        BigInteger d = a.multiply(b.shiftLeft(1).subtract(a));
        BigInteger e = a.multiply(a).add(b.multiply(b));
        a = d;
        b = e;
        if (((n >>> i) & 1) != 0) {
            BigInteger c = a.add(b);
            a = b;
            b = c;
        }
    }
    return a;
}

回答by AMADANON Inc.

Having followed a similar approach some time ago, I've just realized there's another optimization you can make.

前段时间采用了类似的方法，我刚刚意识到您可以进行另一种优化。

If you know two large consecutive answers, you can use this as a starting point. For example, if you know F(100)and F(101), then calculating F(104)is approximately as difficult (*) as calculating F(4)based on F(0)and F(1).

如果您知道两个连续的大答案，您可以以此为起点。例如，如果您知道F(100)和F(101)，那么计算F(104)与基于F(0)和F(1)计算F(4)的难度大致相同 (* )。

Calculating iteratively up is as efficient calculation-wise as doing the same using cached-recursion, but uses less memory.

迭代计算与使用缓存递归计算一样有效，但使用更少的内存。

Having done some sums, I have also realized that, for any given z < n:

做了一些总结后，我也意识到，对于任何给定的z < n：

F(n)=F(z) * F(n-z) + F(z-1) * F(n-z-1)

F(n)=F(z) * F(nz) + F(z-1) * F(nz-1)

If n is odd, and you choose z=(n+1)/2, then this is reduced to

如果 n 是奇数，而您选择z=(n+1)/2，则将其简化为

F(n)=F(z)^2+F(z-1)^2

F(n)=F(z)^2+F(z-1)^2

It seems to me that you should be able to use this by a method I have yet to find, that you should be able use the above info to find F(n) in the number of operations equal to:

在我看来，您应该能够通过我尚未找到的方法来使用它，您应该能够使用上述信息在等于以下操作的次数中找到 F(n)：

the number of bits in n doublings (as per above) + the number of 1bits in n addings; in the case of 104, this would be (7 bits, 3 '1' bits) = 14 multiplications (squarings), 10 additions.

1n 次加法中的位数（如上所述）+ n 次加法中的位数；在 104 的情况下，这将是（7 位，3 个“1”位）= 14 次乘法（平方），10 次加法。

(*) assuming adding two numberstakes the same time, irrelevant of the size of the two numbers.

(*) 假设添加两个数字需要相同的时间，与两个数字的大小无关。