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

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

Re: constexpr is really very smart!

Show key headers only | View raw

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

Iterative:

static long long fib(long n)
{
  if (n <= 0)
    return 0;
  // find MS bit
  unsigned long tmp = n;
  unsigned long bit = 1;
  while (tmp > 1) {
    bit += bit;
    tmp /= 2;
  }
  // 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 long a = 0, b = 1;
  while (bit > 1) {
    long long c = a + b; // fib(n+1)
    bit /= 2;
    if ((n & bit)==0) { // (n-1,n) => (n*2-1,n*2)
      c += a;
      a = a*a + b*b;
      b = c*b;
    } else {            // (n-1,n) => (n*2,n*2+1)
      a = (a + c)*b;
      b = b*b + c*c;
    }
  }
  return b;
}


Both variants above are O(log(n)). 
In practice for n in range 0 to 92 my measurement gear does not detect
differences in speed vs simple loop. If anything, simple loop is a
little faster.

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