Path: ...!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: Fri, 20 Dec 2024 02:17:03 +0200
Organization: A noiseless patient Spider
Lines: 104
Message-ID: <20241220021703.00003e9e@yahoo.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>
MIME-Version: 1.0
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: 7bit
Injection-Date: Fri, 20 Dec 2024 01:17:07 +0100 (CET)
Injection-Info: dont-email.me; posting-host="cd72757de727eb0edb19146209da36f1";
	logging-data="3256597"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19PjceM9FU4Nl9wE47jr+Z55lPoGYhOTZU="
Cancel-Lock: sha1:LkbEw7o7Bp0Vjx85mIRwrZ7s3zk=
X-Newsreader: Claws Mail 4.1.1 (GTK 3.24.34; x86_64-w64-mingw32)
Bytes: 3474

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