C compact matrix Fibonacci (GMP)

main.c

#include "gmp.h"

typedef struct {
  mpz_t step, ident;
} flm;

// these variables are used in the functions as storage
// they're exterior so that I can initialize them once each.
mpz_t s0, s1, s2;
flm base;

#define INITIALIZERS                                                           \
  mpz_init(base.step);                                                         \
  mpz_init(base.ident);                                                        \
  mpz_init(s0);                                                                \
  mpz_init(s1);                                                                \
  mpz_init(s2);

void flm_mul(flm *rop, const flm op) {
  mpz_add(s2, rop->step, rop->ident);
  mpz_add(s0, op.step, op.ident);

  mpz_mul(s1, s0, s2);

  mpz_mul(s0, rop->ident, op.ident);
  mpz_sub(s1, s1, s0);

  mpz_addmul(s0, rop->step, op.step);

  mpz_set(rop->step, s1);
  mpz_set(rop->ident, s0);
}

void flm_pow(flm *ret, unsigned long idx) {
  mpz_set(base.step, ret->step);
  mpz_set(base.ident, ret->ident);
  idx--;
  while (idx) {
    if (idx % 2) {
      flm_mul(ret, base);
    }
    idx /= 2;
    if (idx)
      flm_mul(&base, base);
  }
}

#include <stdio.h>

int main(void) {
  INITIALIZERS;

  flm step;
  mpz_init(step.step);
  mpz_init(step.ident);
  mpz_set_ui(step.step, 1);

  unsigned long n = 0b1 << 27;

  flm_pow(&step, n);

  // gmp_printf("fib(%u) = %Zd\n", n, step.step);
}