Re: constexpr is really very smart!

Michael S <already5chosen@yahoo.com> writes:

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

Slow for the problem, but not slow for the algorithm.  The
point of the video was to compare relative speeds of an
algorithm under two different compilation schemes (with and
without constexpr), not to compare absolute speeds to solve
the problem of computing fibonacci numbers.

#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;
}

Here is my second fastest fibonacci calculation code (for
relatively small inputs):

    typedef long unsigned long ULL;

    ULL
    fibonacci( unsigned n ){
        ULL  b = n&1,  a = b^1;

        if(  n & 2  )  a += b,  b += a;
        if(  n & 4  )  a += b,  b += a,  a += b,  b += a;
        if(  n & 8  ){
            ULL na = 13*a+21*b, nb = 21*a+34*b;
            a = na,  b = nb;
        }

        n >>= 4;
        while(  n--  ){
            ULL  na = 610*a + 987*b,  nb = 987*a + 1597*b;
            a = na,  b = nb;
        }

        return  b;
    }

My fastest fibonacci code uses recursion. :)