Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c++ > #121282

Re: constexpr is really very smart!

Show key headers only | View raw

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!

Back to comp.lang.c++ | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

constexpr is really very smart! Student Project <student@invalid.invalid> - 2024-12-15 20:20 +0000
  Re: constexpr is really very smart! Michael S <already5chosen@yahoo.com> - 2024-12-16 11:28 +0200
    Re: constexpr is really very smart! David Brown <david.brown@hesbynett.no> - 2024-12-16 11:18 +0100
      Re: constexpr is really very smart! Michael S <already5chosen@yahoo.com> - 2024-12-16 13:23 +0200
        Re: constexpr is really very smart! David Brown <david.brown@hesbynett.no> - 2024-12-16 13:43 +0100
          Re: constexpr is really very smart! Michael S <already5chosen@yahoo.com> - 2024-12-17 11:08 +0200
            Re: constexpr is really very smart! David Brown <david.brown@hesbynett.no> - 2024-12-17 11:10 +0100
        Re: constexpr is really very smart! Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-12-18 03:26 -0800
          Re: constexpr is really very smart! Michael S <already5chosen@yahoo.com> - 2024-12-18 14:39 +0200
            Re: constexpr is really very smart! Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-12-18 07:42 -0800
    Re: constexpr is really very smart! Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-12-17 12:54 -0800
      Re: constexpr is really very smart! Michael S <already5chosen@yahoo.com> - 2024-12-18 01:33 +0200
        Re: constexpr is really very smart! Michael S <already5chosen@yahoo.com> - 2024-12-18 13:51 +0200
          Re: constexpr is really very smart! Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-12-19 00:40 -0800
            Re: constexpr is really very smart! Michael S <already5chosen@yahoo.com> - 2024-12-20 02:17 +0200
              Re: constexpr is really very smart! Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-12-20 14:59 -0800
                Re: constexpr is really very smart! Michael S <already5chosen@yahoo.com> - 2024-12-22 00:07 +0200
                Re: constexpr is really very smart! Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-12-22 10:25 -0800
                Re: constexpr is really very smart! Michael S <already5chosen@yahoo.com> - 2024-12-23 17:47 +0200
                Re: constexpr is really very smart! Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-12-24 05:21 -0800
                Bignum multiplication in Python vs GMP (was: constexpr is really very smart!) Michael S <already5chosen@yahoo.com> - 2024-12-25 11:05 +0200
                Re: Bignum multiplication in Python vs GMP (was: constexpr is really very smart!) Michael S <already5chosen@yahoo.com> - 2024-12-25 13:33 +0200
                Re: Bignum multiplication in Python vs GMP (was: constexpr is really very smart!) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-12-26 18:54 -0800
                Re: Bignum multiplication in Python vs GMP (was: constexpr is really very smart!) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-12-26 18:42 -0800
          Re: constexpr is really very smart! Student Project <student@invalid.invalid> - 2024-12-19 19:14 +0000
        Re: constexpr is really very smart! Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-12-18 09:45 -0800
          Re: constexpr is really very smart! Michael S <already5chosen@yahoo.com> - 2024-12-18 22:00 +0200
            Re: constexpr is really very smart! Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-12-19 00:57 -0800
              Re: constexpr is really very smart! Michael S <already5chosen@yahoo.com> - 2024-12-19 23:45 +0200
                Re: constexpr is really very smart! Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-12-20 14:31 -0800
                Re: constexpr is really very smart! Michael S <already5chosen@yahoo.com> - 2024-12-22 00:14 +0200
                Re: constexpr is really very smart! James Kuyper <jameskuyper@alumni.caltech.edu> - 2024-12-21 17:55 -0500
                Re: constexpr is really very smart! Michael S <already5chosen@yahoo.com> - 2024-12-22 02:22 +0200
                Re: constexpr is really very smart! Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-12-22 10:33 -0800
                Re: constexpr is really very smart! Michael S <already5chosen@yahoo.com> - 2024-12-23 00:05 +0200
                Re: constexpr is really very smart! Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-12-22 17:17 -0800
  Re: constexpr is really very smart! Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2024-12-17 12:20 -0800
    Re: constexpr is really very smart! Student Project <student@invalid.invalid> - 2024-12-18 04:45 +0000
      Re: constexpr is really very smart! Michael S <already5chosen@yahoo.com> - 2024-12-18 14:17 +0200

csiph-web