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: Tue, 17 Dec 2024 11:08:02 +0200
Organization: A noiseless patient Spider
Lines: 73
Message-ID: <20241217110802.00007f6d@yahoo.com>
References: <vjndub$2glcu$1@paganini.bofh.team>
	<20241216112808.00003f74@yahoo.com>
	<vjouq6$12khu$2@dont-email.me>
	<20241216132315.00007859@yahoo.com>
	<vjp78v$14muv$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
Injection-Date: Tue, 17 Dec 2024 10:07:07 +0100 (CET)
Injection-Info: dont-email.me; posting-host="bd70fc695941a594d8791060d23b8081";
	logging-data="1764261"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX18ZdJXVNBNonvyl8Rmhw2vDAxAWqjWigsU="
Cancel-Lock: sha1:+sc0b59RxUoiHMzSYeatgimUCb0=
X-Newsreader: Claws Mail 3.19.1 (GTK+ 2.24.33; x86_64-w64-mingw32)
Bytes: 3740

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:
> >  =20
> >> On 16/12/2024 10:28, Michael S wrote: =20
>=20
>=20
> >  =20
> >> My guess is that the OP is referring to some kind of na=C3=AFve
> >> recursive Fibonacci implementation. =20
> >=20
> > Something like that ?
> > static long long slow_fib(long n)
> > {
> >    if (n < 1)
> >      return 0;
> >    if (n =3D=3D 1)
> >      return 1;
> >    return slow_fib(n-2)+slow_fib(n-1);
> > }
> >=20
> > Yes, 270 usec could be considered fast relatively to that.
> > slow_fib(35) takes 20 msec on my old PC.
> >  =20
>=20
> 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!)
>=20
> It can also be an interesting exercise to look at the speed of=20
> 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 :
>=20
> 	fib(2 * n - 1) =3D fib(n) ** 2 + fib(n - 1) ** 2
> 	fib(2 * n) =3D (2 * fib(n - 1) + fib(n)) * fib(n)
>=20
> As you get even bigger, you would then want to use fancier ways to do=20
> the multiplication - I don't know if those can be used in a way that=20
> interacts well with formulas for the Fibonacci numbers.
>=20

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 !
>=20

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.