Re: constexpr is really very smart!

On Tue, 17 Dec 2024 12:54:19 -0800
Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:

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

From BigO perspective this code looks like it's still O(n) so no better
than simple loop.
According to my measurement gear, in range 0 to 92 there are few points
where it is faster than simple loop, but in majority of cases it is
slower.

My fastest fibonacci code uses recursion. :)

There is 1st atempts at recursive code with better than exponential BigO

static long long fib(long n)
{
  if (n < 3)
    return n < 1 ? 0 : 1;
  long a = n/2;
  long b = n-a;
  return fib(a)*fib(b-1)+fib(a+1)*fib(b);
}

O(n*n) - not exponential but still pretty bad.
A small obvious modification (specialization) turns it into O(n):

static long long fib(long n)
{
  if (n < 3)
    return n < 1 ? 0 : 1;
  long a = n/2;
  long b = n-a;
  if (a == b) {
    long long f0 = fib(a-1);
    long long f1 = fib(a);
    long long f2 = f0+f1;
    return (f0+f2)*f1;
  } else { // b == a+1
    long long f0 = fib(a);
    long long f1 = fib(a+1);
    return f0*f0+f1*f1;
  }
}

Still, despite being the same as yours and as a simple loop in BigO
sence, it is several times slower in absolute speed.

I am pretty sure that better variant exists, but for tonight it's
enough.