Re: constexpr is really very smart!

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!