Path: ...!weretis.net!feeder9.news.weretis.net!news.quux.org!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: Michael S <already5chosen@yahoo.com>
Newsgroups: comp.lang.c++
Subject: Re: constexpr is really very smart!
Date: Wed, 18 Dec 2024 01:33:42 +0200
Organization: A noiseless patient Spider
Lines: 140
Message-ID: <20241218013342.0000518a@yahoo.com>
References: <vjndub$2glcu$1@paganini.bofh.team>
	<20241216112808.00003f74@yahoo.com>
	<86jzbyghdw.fsf@linuxsc.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: quoted-printable
Injection-Date: Wed, 18 Dec 2024 00:33:46 +0100 (CET)
Injection-Info: dont-email.me; posting-host="b9b47f030a8936d1360dde1a260912d6";
	logging-data="2069230"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/CBKnHi6mq6Zuc0mm4i2K0k8oH1/P+N5s="
Cancel-Lock: sha1:OwbUNUn7EMu0XFJf6mAQITD0s1A=
X-Newsreader: Claws Mail 4.1.1 (GTK 3.24.34; x86_64-w64-mingw32)
Bytes: 4897

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

> Michael S <already5chosen@yahoo.com> writes:
>=20
> > On Sun, 15 Dec 2024 20:20:42 +0000
> > Student Project <student@invalid.invalid> wrote:
> > =20
> >> 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=3Diy1UimoWcaLG31Xi>
> >>
> >> 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.
> >> =20
> >>> D:\CmdLine\C_Cpp\Chrono02>program =20
> >>> Fibonacci_c: 9227465
> >>> Time Taken: 270 =20
> >>> D:\CmdLine\C_Cpp\Chrono02>program =20
> >>> Fibonacci_c: 9227465
> >>> Time Taken: 257 =20
> >>> D:\CmdLine\C_Cpp\Chrono02>program =20
> >>> Fibonacci_c: 9227465
> >>> Time Taken: 171 =20
> >>> D:\CmdLine\C_Cpp\Chrono02>program =20
> >>> Fibonacci_c: 9227465
> >>> Time Taken: 176 =20
> >>
> >> Amazing. =20
> >
> > I didn't see the video (I never see that type of videos), but 270
> > microseconds sound astonishingly slow for fib(35). =20
>=20
> 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.
>=20
> > #include <stdio.h>
> > #include <stdlib.h>
> > #include <intrin.h>
> >
> > static long long fib(long n)
> > {
> >   if (fib <=3D 0)
> >     return 0;
> >   long long f0 =3D 0, f1 =3D 1;
> >   for (long i =3D 1; i < n; ++i) {
> >     long long f2 =3D f0 + f1;
> >     f0 =3D f1;
> >     f1 =3D f2;
> >   }
> >   return f1;
> > } =20
>=20
> Here is my second fastest fibonacci calculation code (for
> relatively small inputs):
>=20
>     typedef long unsigned long ULL;
>=20
>     ULL
>     fibonacci( unsigned n ){
>         ULL  b =3D n&1,  a =3D b^1;
>=20
>         if(  n & 2  )  a +=3D b,  b +=3D a;
>         if(  n & 4  )  a +=3D b,  b +=3D a,  a +=3D b,  b +=3D a;
>         if(  n & 8  ){
>             ULL na =3D 13*a+21*b, nb =3D 21*a+34*b;
>             a =3D na,  b =3D nb;
>         }
>=20
>         n >>=3D 4;
>         while(  n--  ){
>             ULL  na =3D 610*a + 987*b,  nb =3D 987*a + 1597*b;
>             a =3D na,  b =3D nb;
>         }
>=20
>         return  b;
>     }
>=20



=46rom 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 =3D n/2;
  long b =3D 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 =3D n/2;
  long b =3D n-a;
  if (a =3D=3D b) {
    long long f0 =3D fib(a-1);
    long long f1 =3D fib(a);
    long long f2 =3D f0+f1;
    return (f0+f2)*f1;
  } else { // b =3D=3D a+1
    long long f0 =3D fib(a);
    long long f1 =3D 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.