Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: Tim Rentsch <tr.17687@z991.linuxsc.com>
Newsgroups: comp.lang.c++
Subject: Re: constexpr is really very smart!
Date: Tue, 17 Dec 2024 12:54:19 -0800
Organization: A noiseless patient Spider
Lines: 81
Message-ID: <86jzbyghdw.fsf@linuxsc.com>
References: <vjndub$2glcu$1@paganini.bofh.team> <20241216112808.00003f74@yahoo.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Injection-Date: Tue, 17 Dec 2024 21:54:22 +0100 (CET)
Injection-Info: dont-email.me; posting-host="bae58767cdb6c0b535f28978d104ae2f";
	logging-data="1993362"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX18Y52ZqEGYh8khxb5bVPTMYG4pGyrZN3hM="
User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux)
Cancel-Lock: sha1:0oVjdR5ND7fHF3chbtqe1Ba/MIk=
	sha1:ZjI1w5G0QxzrR4Q52c0lPZNO3Kg=
Bytes: 3222

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