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: Fri, 20 Dec 2024 14:59:07 -0800
Organization: A noiseless patient Spider
Lines: 99
Message-ID: <86msgqezb8.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> <86zfksf4lb.fsf@linuxsc.com> <20241220021703.00003e9e@yahoo.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Injection-Date: Fri, 20 Dec 2024 23:59:08 +0100 (CET)
Injection-Info: dont-email.me; posting-host="7b456885956cc1389d72eb0540418a63";
	logging-data="3851431"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19zFosYsCL6mtTY7aApLXvv6cwzsWjTzK4="
User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux)
Cancel-Lock: sha1:CbKRMn27e09YiyX/SXkN8Z8wros=
	sha1:+DdBNtKejIFfEfr+auHbNc/vxBw=
Bytes: 4000

Michael S <already5chosen@yahoo.com> writes:

> On Thu, 19 Dec 2024 00:40:32 -0800
> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
>
>> Michael S <already5chosen@yahoo.com> writes:
>>
>>> On Wed, 18 Dec 2024 01:33:42 +0200
>>> Michael S <already5chosen@yahoo.com> wrote:
>>>
>>>> [a recursive logarithmic formulation]
>>
>> 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?
>
> Not really.  But I can cheat.
> Below is slightly modified iterative algorithm coded as recursion.

I don't think of your code below as cheating at all.  It resembles
an earlier recursive version that I did, and is pretty much the
sort of thing I had in mind.

> static
> long long fib_3(long long a, long long b, unsigned long rev_n) {
>   if (rev_n == 1)
>     return b;
>
>   long long c = a + b;
>   if ((rev_n & 1) == 0)
>     return fib_3(a*a+b*b, (a+c)*b, rev_n/2);
>   else
>     return fib_3((a+c)*b, b*b+c*c, rev_n/2);
> }

The factoring with 'c' is a nice improvement.  Thank you for
that.

> static
> long long fib_bitrev(unsigned long a, unsigned long b) {
>   return a==1 ? fib_3(0, 1, b) : fib_bitrev( a / 2, b * 2 + a % 2);
> }
>
> long long fib(long n) {
>   return n <= 0 ? 0 : fib_bitrev(n, 1);
> }

The intermediate function fib_bitrev() reverses the bits so they
can be processed from high to low.  I did that by passing two
arguments, a mask and the value of n, and shifting the mask.
Combining that with your 'c' expression factoring, I got this:

    typedef unsigned long long NN;

    static  unsigned   high_bit( unsigned );
    static  NN         lfib4( NN, NN, unsigned, unsigned );

    NN
    logarithmic_fibonacci( unsigned n ){
        return  lfib4( 1, 0, high_bit( n ), n );
    }

    unsigned
    high_bit( unsigned n ){
        n |= n>>1;
        n |= n>>2;
        n |= n>>4;;
        n |= n>>8;;
        n |= n>>16;;
        return  n ^ n>>1;
    }

    NN
    lfib4( NN a, NN b, unsigned m, unsigned n ){
        NN c = a+b;
        return
            m & n   ?  lfib4(          (a+c)*b, b*b+c*c,  m>>1, n ) :
            m       ?  lfib4( a*a+b*b, (a+c)*b,           m>>1, n ) :
            /*****/    b;
    }

I ran a python version to compute fibonacci( 10000000 ).  This code
ran 30% faster than the previous version, which I would be is
almost entirely due to the expression factoring with 'c'.  Great!