Arbitrary precision fibonacci sequence

2012/01/04

An fibonacci sequence generator that uses arbitrary length integers.

/* Arbitrary precision fib() */

#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define DIGITS 418 /* buffer size used in addition algorithm, 2x the length of the total */

char* fib(int);

int main(int argc, char *argv[]) {
  int i;
  for (i=1; i<=1000; i++) {
    char *r = fib(i);
    printf("fib(%d) = %s\n", i, r);
    free(r);
  }
  return 0;
}

char* fib(int n) {
  unsigned short u[DIGITS] = {0}, v[DIGITS] = {0};
  u[0] = 1;
  v[0] = 1;

  char *p = (char *)malloc(sizeof(char) * 255);
  sprintf(p, "%d", INT_MAX);
  int b = strlen(p); /* radix */
  free(p);

  while (--n > 1) {
    unsigned short t[DIGITS];
    memcpy(t, v, DIGITS);

    /* addition sequence for w = v + u */
    /* knuth seminumerical algorithms 4.3.1 */
    unsigned short w[DIGITS] = {0};
    unsigned short j=0, k=0;
    for (j=0; j<DIGITS; j++) {
      w[j] = (u[j] + v[j] + k) % b;
      k = (unsigned short)((u[j] + v[j] + k) / b);
    }
    w[DIGITS-1] = k;
    /* end */

    memcpy(v, w, DIGITS);
    memcpy(u, t, DIGITS);
  }

  int i;
  char *o = (char *)malloc(sizeof(char) * b * DIGITS);
  char *q = (char *)malloc(sizeof(char) * b);
  o[0] = '\0';
  for (i=DIGITS-1; i>0; i--) {
    if (v[i] != 0) { break; } /* seek to first non-zero */
  }
  for (; i>=0; i--) {
    sprintf(q, "%d", v[i]);
    o = strcat(o, q);
  }
  free(q);

  return o;
}

Comments