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: Thu, 19 Dec 2024 00:40:32 -0800
Organization: A noiseless patient Spider
Lines: 108
Message-ID: <86zfksf4lb.fsf@linuxsc.com>
References: <vjndub$2glcu$1@paganini.bofh.team> <20241216112808.00003f74@yahoo.com> <86jzbyghdw.fsf@linuxsc.com> <20241218013342.0000518a@yahoo.com> <20241218135131.00000006@yahoo.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Injection-Date: Thu, 19 Dec 2024 09:40:33 +0100 (CET)
Injection-Info: dont-email.me; posting-host="c511f684fbfa549a35877bd49c9b418c";
	logging-data="2924801"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX18PWJSd45crUj2pQGwbZWR+wqxNXOeq1fI="
User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux)
Cancel-Lock: sha1:o5f9ceWSbZqcgbH8RJLEJpCSilA=
	sha1:Td5Pd6oJWmqce86iqpkOKrDTU7w=
Bytes: 3710

Michael S <already5chosen@yahoo.com> writes:

> On Wed, 18 Dec 2024 01:33:42 +0200
> Michael S <already5chosen@yahoo.com> wrote:
>
>> I am pretty sure that better variant exists, but for tonight it's
>> enough.
>
> Morning fibs.
>
> Recursive:
>
> struct pair_t {
>   long long a,b;
> };
>
> // return .a=fib(n), .b=fib(n+1)
> static struct pair_t fib2(long n)
> {
>   if (n <= 0) {
>     struct pair_t ret = { .a = 0, .b = n==0 ? 1 : 0 };
>     return ret;
>   }
>   // for n > 0
>   // fib(n*2)   = (fib(n-1)+fib(n+1))*fib(n)
>   // fib(n*2+1) = fib(n)*fib(n)+fib(n+1)*fib(n+1)
>   long m = (n-1) >> 1;
>   struct pair_t ret = fib2(m);
>   long long a = ret.a, b = ret.b;
>   long long c = a + b;
>   if ((n & 1)==0) { // (m,m+1) => ((m+1)*2,(m+1)*2*2+1)
>     ret.a = (a + c)*b;
>     ret.b = b*b + c*c;
>   } else {          // (m,m+1) => (m*2+1,(m+1)*2)
>     ret.a = a*a + b*b;
>     ret.b = (a + c)*b;
>   }
>   return ret;
> }
>
> static long long fib(long n)
> {
>   struct pair_t x = fib2(n-1);
>   return x.b;
> }

I may have inadvertently misled you.  Here is a simple linear
formulation that uses recursion:

    typedef  unsigned long long  NN;

    static NN fibonacci_3( NN, NN, unsigned );

    NN
    fibonacci( unsigned n ){
        return  fibonacci_3( 1, 0, n );
    }

    NN
    fibonacci_3( NN a, NN b, unsigned n ){
        return  n == 0  ? b  :  fibonacci_3( b, a+b, n-1 );
    }

Can you apply this idea to your logarithmic scheme?


> Iterative:
>
> static long long fib(long n)
> {
>   if (n <= 0)
>     return 0;
>   // find MS bit
>   unsigned long tmp = n;
>   unsigned long bit = 1;
>   while (tmp > 1) {
>     bit += bit;
>     tmp /= 2;
>   }
>   // for n > 0
>   // fib(n*2)   = (fib(n-1)+fib(n+1))*fib(n)
>   // fib(n*2+1) = fib(n)*fib(n)+fib(n+1)*fib(n+1)
>   long long a = 0, b = 1;
>   while (bit > 1) {
>     long long c = a + b; // fib(n+1)
>     bit /= 2;
>     if ((n & bit)==0) { // (n-1,n) => (n*2-1,n*2)
>       c += a;
>       a = a*a + b*b;
>       b = c*b;
>     } else {            // (n-1,n) => (n*2,n*2+1)
>       a = (a + c)*b;
>       b = b*b + c*c;
>     }
>   }
>   return b;
> }
>
>
> Both variants above are O(log(n)).
> In practice for n in range 0 to 92 my measurement gear does not detect
> differences in speed vs simple loop.  If anything, simple loop is a
> little faster.

Yes, the log(n) can be beaten by simpler schemes for small n.

I wrote a (recursive) log(n) fibonacci in python.  It was able
to compute fibonacci( 10000000 ) in just under 3 seconds.