Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: David Brown <david.brown@hesbynett.no>
Newsgroups: comp.lang.c++
Subject: Re: constexpr is really very smart!
Date: Mon, 16 Dec 2024 13:43:11 +0100
Organization: A noiseless patient Spider
Lines: 151
Message-ID: <vjp78v$14muv$1@dont-email.me>
References: <vjndub$2glcu$1@paganini.bofh.team>
 <20241216112808.00003f74@yahoo.com> <vjouq6$12khu$2@dont-email.me>
 <20241216132315.00007859@yahoo.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Mon, 16 Dec 2024 13:43:13 +0100 (CET)
Injection-Info: dont-email.me; posting-host="4e34d3707fdeb2bacac3b5acc43f1560";
	logging-data="1203167"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX184xGdLmUcC5SBOUId2ko58msvgvEpLvT0="
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101
 Thunderbird/102.11.0
Cancel-Lock: sha1:LKwbuuSVycnmauR02GUouGEJTsc=
Content-Language: en-GB
In-Reply-To: <20241216132315.00007859@yahoo.com>
Bytes: 6544

On 16/12/2024 12:23, Michael S wrote:
> 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))

Yes.

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

Sure, there comes a limit to what works here.  Doubles don't have the 
precision range of 64-bit integers.  (You may also see inaccuracies 
build up with floating point even before the range of the mantissa 
bits.)  Similarly, there is a limit to how high you can get with 64-bit 
integers.  But certainly multi-precision integer arithmetic will be a 
lot faster than multi-precision floating point.

There's also a big difference if you want to generate the sequence, or 
just the n'th number, or if you are only interested in the size of the 
n'th number, or some other property.


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

That's what I was guessing, yes.  Calculating Fibonacci numbers is often 
used as an example for showing how to write recursive functions with a 
structure like the one above, then looking at different techniques for 
improving them - such as using a recursive function that takes (n, a, b) 
and returns (n - 1, b, a + b), or perhaps memoization.  (You could 
probably teach a term's worth of a Haskell course based entirely on 
formulations for calculating Fibonacci functions!)

It can also be an interesting exercise to look at the speed of 
calculating Fibonacci numbers for different sizes.  I expect your linear 
integer function will be fastest for small n, then powers of phi will be 
faster for a bit, then you'd switch back to integers of progressively 
larger but fixed sizes using the recursive formula for double n :

	fib(2 * n - 1) = fib(n) ** 2 + fib(n - 1) ** 2
	fib(2 * n) = (2 * fib(n - 1) + fib(n)) * fib(n)

As you get even bigger, you would then want to use fancier ways to do 
the multiplication - I don't know if those can be used in a way that 
interacts well with formulas for the Fibonacci numbers.

I guess that can be left as an exercise for the OP !


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

My experience is that gcc will pre-calculate for a certain depth of 
recursion here, then give up and generate run-time code.  But you would 
not have to pre-calculate or expand very far before it made a fair 
difference to the run-time of slow_fib(35).

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

:-)