Re: constexpr is really very smart!

On 17/12/2024 10:08, Michael S wrote:

On Mon, 16 Dec 2024 13:43:11 +0100
David Brown <david.brown@hesbynett.no> wrote:
 

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:

>
>

  

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

 There exist precise methods of integer multiplication with complexity
of O(N*Log(N)) where N is number of digits. Personally, I never had a
need for them, but I believe that they work.

I've never needed them either.  In fact, in the case of the O(n . log n) algorithm, /nobody/ has needed it - the algorithm is only an improvement over higher big-O complexity algorithms for at least 2 ** 1729 ** 12 digits.  That means you need 39 decimal digits just to express the number of digits in the numbers you are going to multiply.  Maybe the factor of 1729 will be reduced somewhat in the future, but I really don't see it being added to the GMP library any time soon :-)
<https://mattermodeling.stackexchange.com/questions/1355/did-the-2019-discovery-of-on-logn-multiplication-have-a-practical-outcome>
There are other algorithms that have practical uses when dealing with /really/ big numbers.  But I think it will be very rare to need anything beyond Karatsuba, which is reasonably easy to understand - it splits the numbers into two halves, does a bit of re-arrangement, and ends up with 3 smaller multiplications and some additions and subtractions instead of the traditional 4 smaller multiplications.
(You'll find Karatsuba in RSA algorithms, but no algorithms beyond that.)

 

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

 Since OP's ideas of "fast" are very humble, he is likely to be
satisfied with the very first step above naive:
 static long long less_slow_fib(long n)
{
   if (n < 3)
     return n < 1 ? 0 : 1;
   return less_slow_fib(n-2)*2+less_slow_fib(n-3);
}
 On my old PC is calculates fib(35) in 24 usec. That is more than
10 times faster than his idea of fast.