Re: constexpr is really very smart!

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:
 

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?
 
 

Not really. But I can cheat.
Below is slightly modified iterative algorithm coded as recursion.

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);
}

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);
}