Strange as it seems, the programmers who work on GNU GMP are people too.Heater wrote: ↑Thu Nov 22, 2018 9:31 pmjahboater,The C version using GMP we are using here simply calls the gmp function: mpz_fib_ui( res, 4784969 );I wonder how GMP is so fast.
No doubt that does not use the schoolboy algorithm I show above in fiboSlow. Rather they will use a fast fibo algorithm, perhaps as described here: Fast Fibonacci algorithms: https://www.nayuki.io/page/fast-fibonacci-algorithms
Which is what I implemented in JS using JS BigInts here: viewtopic.php?f=32&t=225927&start=25#p1388128
Quite often it is very wise to use a library rather than try to reinvent the wheel oneself. Where people far more knowledgeable have done the hard work to perfect an optimal solution and years of use by many users has shaken the bugs out of it.
One of the things I stress when teaching is that a wrong answer is often worse than no answer. Wrong answers are particularly dangerous when produced by a computer, because people tend to believe a computer without verifying the answer--sometimes because they don't know how to verify it.
One way to verify the correctness of an answer is to independently compute it using the simplest algorithm possible. Computing the n-th number in the Fibonacci sequence directly from the definition is a possible way to verify that the more efficient and complicated algorithms are coded correctly.
While benchmark problems such as computing the eigenvalues of a particular matrix, fluid flow over a backward facing step or finding the 4784969th Fibonacci number can be used to compare algorithms, it is not unreasonable to further specify the algorithm and then compare computers or compilers. For example, the Linpack benchmark not only solves systems of linear equations, but explicitly specifies that those equations should be solved using Gaussian elimination with partial pivoting--use of the Strassen algorithm is not allowed.
In the present case, it appears the expressiveness of BBC BASIC as demonstrated by the ability to efficiently code big-number arithmetic and then compute the Fibonacci sequence using the definition
F(n+1) = F(n) + F(n-1)
is being compared to the expressiveness of other programming languages in doing the same. It should also be noted that if the stated problem is to compute all numbers in the Fibonacci sequence up to and including the 4784969th, then the simple algorithm is likely optimal.