Re: constexpr is really very smart!

On Mon, 16 Dec 2024 13:43:11 +0100
David Brown <david.brown@hesbynett.no> wrote:

On 16/12/2024 12:23, Michael S wrote:

On Mon, 16 Dec 2024 11:18:46 +0100
David Brown <david.brown@hesbynett.no> wrote:
 

On 16/12/2024 10:28, Michael S wrote: 

 
 

 

My guess is that the OP is referring to some kind of naïve
recursive Fibonacci implementation. 

 
Something like that ?
static long long slow_fib(long n)
{
   if (n < 1)
     return 0;
   if (n == 1)
     return 1;
   return slow_fib(n-2)+slow_fib(n-1);
}
 
Yes, 270 usec could be considered fast relatively to that.
slow_fib(35) takes 20 msec on my old PC.
 

 
That's what I was guessing, yes.  Calculating Fibonacci numbers is
often used as an example for showing how to write recursive functions
with a structure like the one above, then looking at different
techniques for improving them - such as using a recursive function
that takes (n, a, b) and returns (n - 1, b, a + b), or perhaps
memoization.  (You could probably teach a term's worth of a Haskell
course based entirely on formulations for calculating Fibonacci
functions!)
 
It can also be an interesting exercise to look at the speed of
calculating Fibonacci numbers for different sizes.  I expect your
linear integer function will be fastest for small n, then powers of
phi will be faster for a bit, then you'd switch back to integers of
progressively larger but fixed sizes using the recursive formula for
double n :
 
fib(2 * n - 1) = fib(n) ** 2 + fib(n - 1) ** 2
fib(2 * n) = (2 * fib(n - 1) + fib(n)) * fib(n)
 
As you get even bigger, you would then want to use fancier ways to do
the multiplication - I don't know if those can be used in a way that
interacts well with formulas for the Fibonacci numbers.
 

There exist precise methods of integer multiplication with complexity
of O(N*Log(N)) where N is number of digits. Personally, I never had a
need for them, but I believe that they work.

I guess that can be left as an exercise for the OP !
 

Since OP's ideas of "fast" are very humble, he is likely to be
satisfied with the very first step above naive:

static long long less_slow_fib(long n)
{
  if (n < 3)
    return n < 1 ? 0 : 1;
  return less_slow_fib(n-2)*2+less_slow_fib(n-3);
}

On my old PC is calculates fib(35) in 24 usec. That is more than
10 times faster than his idea of fast.