If you anons had read your SICP, you would know that the nth fibonacci number can be computed in logarithmic time
#include <gmp.h>
#include <stdio.h>
mpz_t scratch1, scratch2;
void iter(mpz_t fib[3], unsigned long i) {
if (i == 1) return;
if (i % 2 == 0) {
mpz_mul(scratch1, fib[1], fib[1]);
mpz_add(scratch2, fib[0], fib[2]);
mpz_mul(fib[1], fib[1], scratch2);
mpz_mul(fib[0], fib[0], fib[0]);
mpz_add(fib[0], fib[0], scratch1);
mpz_mul(fib[2], fib[2], fib[2]);
mpz_add(fib[2], fib[2], scratch1);
iter(fib, i / 2);
} else {
iter(fib, i - 1);
mpz_add(scratch1, fib[0], fib[1]);
mpz_set(fib[2], fib[1]);
mpz_set(fib[1], fib[0]);
mpz_set(fib[0], scratch1);
}
}
int main() {
mpz_t fib[3];
mpz_init_set_ui(fib[0], 1);
mpz_init_set_ui(fib[1], 1);
mpz_init_set_ui(fib[2], 0);
mpz_init(scratch1);
mpz_init(scratch2);
iter(fib, 100000000);
printf("%s\n", mpz_get_str(NULL, 10, fib[0]));
return 0;
}
computes the 100 millionth fibonacci number (and prints it) in 4 seconds.
