Re: constexpr is really very smart!

On Fri, 20 Dec 2024 14:59:07 -0800
Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:

>
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!
>

This one does fib(10M) in 89 msec on my very old home PC.

#include "gmp.h"

void fib(mpz_t rop, long n)
{
  if (n <= 0) {
    mpz_set_ui(rop, 0);
    return;
  }

  // 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)
  mpz_t a, b, aa, bb;
  mpz_init_set_si(a, 0);
  mpz_init_set_si(b, 1);
  mpz_init(aa);
  mpz_init(bb);
  while (bit > 1) {
    mpz_mul(aa, a, a);
    mpz_mul(bb, b, b);
    mpz_add(aa, aa, bb); // aa = a*a+b*b

    mpz_add(a, a, a);
    mpz_add(a, a, b);
    mpz_mul(bb, a, b); // bb = (a*2+b)*b

    bit /= 2;
    if (n & bit) {
      mpz_add(aa, aa, bb);
      mpz_swap(aa, bb);
    }
    mpz_swap(a, aa);
    mpz_swap(b, bb);
  }
  mpz_swap(rop, b);
  mpz_clear(a);
  mpz_clear(b);
  mpz_clear(aa);
  mpz_clear(bb);
}