4 ms·
It’s even possible to compute arbitrary Fibonacci numbers exactly using Binet’s formula with arbitrary-precision floating point arithmetic. It’s not the fastes
by robinhouston 8y ago
It’s even possible to compute arbitrary Fibonacci numbers exactly using Binet’s formula with arbitrary-precision floating point arithmetic.
It’s not the fastest possible algorithm, but it’s fun. I implemented it here: https://github.com/robinhouston/fibonacci-float-calc https://github.com/robinhouston/fibonacci-float-calc
The implementation is pretty simple, using GMP. This is the whole function:
/**
* Compute the nth Fibonacci number with arbitrary-precision
* floating-point arithmetic, using the formula fib(n) ≈ phi ^ n / sqrt(5)
* (which is exact if you round the rhs to the nearest whole number).
*/
void fib_float(mpf_t *result, long n)
{
mpf_t sqrt5, phi;
mp_bitcnt_t bitcnt;
/* We need about n lg(phi) bits of precision */
bitcnt = n * 7 / 10;
/* Initialise sqrt5 to the square root of 5 */
mpf_init2(sqrt5, bitcnt);
mpf_sqrt_ui(sqrt5, 5);
/* Initialise phi to the Golden Ratio */
mpf_init2(phi, bitcnt);
mpf_set(phi, sqrt5);
mpf_add_ui(phi, phi, 1);
mpf_div_2exp(phi, phi, 1);
/* Compute phi ^ n / sqrt5 */
mpf_init2(*result, bitcnt);
mpf_pow_ui(*result, phi, n);
mpf_div(*result, *result, sqrt5);
/* Dispose of the temporary variables */
mpf_clear(sqrt5);
mpf_clear(phi);
}