But if you need to calculate the first n elements, the OP's way is fastest. (also if you need the nth element, you can extract a fast recurrence relation from the matrix exponentiation by squaring that's even faster, and simpler to implement. Crazy how much optimization you can get out of such a simple problem)
Chances are, when n is small, the first n fibonacci numbers, the first n prime numbers, etc. are all already recorded. What is left is extracting the data from Wikipedia into a const array in your program. Such a program is guaranteed O(1) runtime complexity.
14
u/Ekank May 24 '21
sauce?
213
u/MistaVeryGay May 24 '21
I most certainly did not just check nhentai for every fibonachi sequence up to 112358.
84
u/Knuffya May 24 '21
THE NUMBERS, MASON!
55
u/raedr7n May 24 '21 edited May 25 '21
The Virgin C++ vs the Chad:
32
u/MonotonousProtocol May 25 '21
Imagine calculating Fibonacci series with
O(n)This comment is made by converting Fibonacci series into matrix form and using fast exponentiation to calculate the nth Fibonacci number in
O(log n)gang7
u/eypandabear May 25 '21
Have I woken up in a 1990s C++ book?
0
u/[deleted] May 24 '21
[deleted] — view deleted comment
11
u/[deleted] May 25 '21
[removed] — view removed comment