Re: constexpr is really very smart!

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))
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.

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.

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.

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.