Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c++ > #121224

Re: constexpr is really very smart!

Show key headers only | View raw

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

Back to comp.lang.c++ | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

constexpr is really very smart! Student Project <student@invalid.invalid> - 2024-12-15 20:20 +0000
  Re: constexpr is really very smart! Michael S <already5chosen@yahoo.com> - 2024-12-16 11:28 +0200
    Re: constexpr is really very smart! David Brown <david.brown@hesbynett.no> - 2024-12-16 11:18 +0100
      Re: constexpr is really very smart! Michael S <already5chosen@yahoo.com> - 2024-12-16 13:23 +0200
        Re: constexpr is really very smart! David Brown <david.brown@hesbynett.no> - 2024-12-16 13:43 +0100
          Re: constexpr is really very smart! Michael S <already5chosen@yahoo.com> - 2024-12-17 11:08 +0200
            Re: constexpr is really very smart! David Brown <david.brown@hesbynett.no> - 2024-12-17 11:10 +0100
        Re: constexpr is really very smart! Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-12-18 03:26 -0800
          Re: constexpr is really very smart! Michael S <already5chosen@yahoo.com> - 2024-12-18 14:39 +0200
            Re: constexpr is really very smart! Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-12-18 07:42 -0800
    Re: constexpr is really very smart! Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-12-17 12:54 -0800
      Re: constexpr is really very smart! Michael S <already5chosen@yahoo.com> - 2024-12-18 01:33 +0200
        Re: constexpr is really very smart! Michael S <already5chosen@yahoo.com> - 2024-12-18 13:51 +0200
          Re: constexpr is really very smart! Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-12-19 00:40 -0800
            Re: constexpr is really very smart! Michael S <already5chosen@yahoo.com> - 2024-12-20 02:17 +0200
              Re: constexpr is really very smart! Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-12-20 14:59 -0800
                Re: constexpr is really very smart! Michael S <already5chosen@yahoo.com> - 2024-12-22 00:07 +0200
                Re: constexpr is really very smart! Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-12-22 10:25 -0800
                Re: constexpr is really very smart! Michael S <already5chosen@yahoo.com> - 2024-12-23 17:47 +0200
                Re: constexpr is really very smart! Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-12-24 05:21 -0800
                Bignum multiplication in Python vs GMP (was: constexpr is really very smart!) Michael S <already5chosen@yahoo.com> - 2024-12-25 11:05 +0200
                Re: Bignum multiplication in Python vs GMP (was: constexpr is really very smart!) Michael S <already5chosen@yahoo.com> - 2024-12-25 13:33 +0200
                Re: Bignum multiplication in Python vs GMP (was: constexpr is really very smart!) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-12-26 18:54 -0800
                Re: Bignum multiplication in Python vs GMP (was: constexpr is really very smart!) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-12-26 18:42 -0800
          Re: constexpr is really very smart! Student Project <student@invalid.invalid> - 2024-12-19 19:14 +0000
        Re: constexpr is really very smart! Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-12-18 09:45 -0800
          Re: constexpr is really very smart! Michael S <already5chosen@yahoo.com> - 2024-12-18 22:00 +0200
            Re: constexpr is really very smart! Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-12-19 00:57 -0800
              Re: constexpr is really very smart! Michael S <already5chosen@yahoo.com> - 2024-12-19 23:45 +0200
                Re: constexpr is really very smart! Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-12-20 14:31 -0800
                Re: constexpr is really very smart! Michael S <already5chosen@yahoo.com> - 2024-12-22 00:14 +0200
                Re: constexpr is really very smart! James Kuyper <jameskuyper@alumni.caltech.edu> - 2024-12-21 17:55 -0500
                Re: constexpr is really very smart! Michael S <already5chosen@yahoo.com> - 2024-12-22 02:22 +0200
                Re: constexpr is really very smart! Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-12-22 10:33 -0800
                Re: constexpr is really very smart! Michael S <already5chosen@yahoo.com> - 2024-12-23 00:05 +0200
                Re: constexpr is really very smart! Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-12-22 17:17 -0800
  Re: constexpr is really very smart! Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2024-12-17 12:20 -0800
    Re: constexpr is really very smart! Student Project <student@invalid.invalid> - 2024-12-18 04:45 +0000
      Re: constexpr is really very smart! Michael S <already5chosen@yahoo.com> - 2024-12-18 14:17 +0200

csiph-web