Skip to content

Instantly share code, notes, and snippets.

@garymacindoe
Created September 12, 2015 18:32
Show Gist options
  • Save garymacindoe/56634830bff5a79a096d to your computer and use it in GitHub Desktop.
Save garymacindoe/56634830bff5a79a096d to your computer and use it in GitHub Desktop.
Calculation of the nth term of the Fibonacci sequence in constant time
#include <stdio.h>
#include <inttypes.h>
#include <math.h>
uint64_t fibonacci(uint64_t n) {
static const double golden = 1.61803398874989484820;
return (uint64_t)floor((pow(golden, (double)n) / sqrt(5.0)) + 0.5);
}
int main(int argc, char * argv[]) {
if (argc != 2) {
fprintf(stderr, "Prints the nth number in the fibonacci sequence (0, 1, 1,"
" 2, 3, 5,...)\n"
"Usage: %s <n>\nwhere:\n\tn is a non-negative integer\n",
argv[0]);
return -1;
}
uint64_t n;
if (sscanf(argv[1], "%" SCNu64, &n) != 1) {
fprintf(stderr, "Failed to parse integer from '%s'\n", argv[1]);
return -2;
}
printf("%" PRIu64 "\n", fibonacci(n));
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment