Re: constexpr is really very smart!

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:

On Sun, 15 Dec 2024 20:20:42 +0000
Student Project <student@invalid.invalid> wrote:
  

The constexpr is really very smart because it can speed up
algorithms 1000 times according to Dave, Microsoft retired
engineer. He has proved it by creating this video:
>
<https://youtu.be/8-VZoXn8f9U?si=iy1UimoWcaLG31Xi>
>
On my computer it took 270 microseconds to calculate fib(35) like
in his example. It was almost instant at the blink of the eyes.
 

D:\CmdLine\C_Cpp\Chrono02>program
Fibonacci_c: 9227465
Time Taken: 270
D:\CmdLine\C_Cpp\Chrono02>program
Fibonacci_c: 9227465
Time Taken: 257
D:\CmdLine\C_Cpp\Chrono02>program
Fibonacci_c: 9227465
Time Taken: 171
D:\CmdLine\C_Cpp\Chrono02>program
Fibonacci_c: 9227465
Time Taken: 176

>
Amazing.
 

>
I didn't see the video (I never see that type of videos), but 270
microseconds sound astonishingly slow for fib(35).
>
#include <stdio.h>
#include <stdlib.h>
#include <intrin.h>
>
static long long fib(long n)
{
    if (fib <= 0)
      return 0;
    long long f0 = 0, f1 = 1;
    for (long i = 1; i < n; ++i) {
      long long f2 = f0 + f1;
      f0 = f1;
      f1 = f2;
    }
    return f1;
}
  

>
There are a dozen different ways to calculate Fibonacci numbers,
ranging from very fast to very slow - but demonstrating different
things.  Even your program is going to be very slow compared to just
using φⁿ / √5.
>

 My news reader is not sure about equation above.
You probably meant ceil(pow((1+sqrt(5))/2, n)/sqrt(5))

Yes.

It works well with double precision math up to n=75. After that it
would need high precision fp library, so probably [much] slower than
simple loop above at least up to n=92 where we run out of range of int64
result.

Sure, there comes a limit to what works here.  Doubles don't have the precision range of 64-bit integers.  (You may also see inaccuracies build up with floating point even before the range of the mantissa bits.)  Similarly, there is a limit to how high you can get with 64-bit integers.  But certainly multi-precision integer arithmetic will be a lot faster than multi-precision floating point.
There's also a big difference if you want to generate the sequence, or just the n'th number, or if you are only interested in the size of the n'th number, or some other property.

 

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.
I guess that can be left as an exercise for the OP !

If the function is declared "constexpr"
and the values used are compile-time constants, then maybe the use of
"constexpr" leads to more of it being pre-calculated at compile time.
>

 But then, how long would it take to compile?
I'd guess for n=35 it's not too bad, but what about n=92?
Slow algorithm is a slow algorithm. Doing it in compile time can only
exaggerate the slowness.
 

My experience is that gcc will pre-calculate for a certain depth of recursion here, then give up and generate run-time code.  But you would not have to pre-calculate or expand very far before it made a fair difference to the run-time of slow_fib(35).

The OP is right that "constexpr" can be very "smart" - but I'm not
sure this is the best calculation for demonstrating that.  However, I
have not watched the video either, and maybe it's well presented.
>

 If it is video and it is about programming then it can not be good.
 

:-)