62 lines
1.5 KiB
C
62 lines
1.5 KiB
C
#include <stdio.h>
|
|
#include <stdint.h>
|
|
|
|
/**
|
|
* @brief Computes the n-th Fibonacci number using matrix exponentiation.
|
|
*
|
|
* This implementation uses the identity:
|
|
* [F(n+1) F(n) ] = [1 1]^n
|
|
* [F(n) F(n-1)] [1 0]
|
|
*
|
|
* The matrix is exponentiated in O(log n) time using exponentiation by squaring.
|
|
*
|
|
* @param n The index of the Fibonacci number to compute.
|
|
* @return The n-th Fibonacci number.
|
|
*/
|
|
uint64_t fibonacci_matrix(uint32_t n);
|
|
|
|
// 2x2 matrix structure for Fibonacci computation
|
|
typedef struct {
|
|
uint64_t a, b;
|
|
uint64_t c, d;
|
|
} FibMatrix;
|
|
|
|
/**
|
|
* @brief Multiplies two 2x2 matrices.
|
|
*/
|
|
static FibMatrix matrix_multiply(FibMatrix x, FibMatrix y) {
|
|
FibMatrix result;
|
|
result.a = x.a * y.a + x.b * y.c;
|
|
result.b = x.a * y.b + x.b * y.d;
|
|
result.c = x.c * y.a + x.d * y.c;
|
|
result.d = x.c * y.b + x.d * y.d;
|
|
return result;
|
|
}
|
|
|
|
/**
|
|
* @brief Raises a 2x2 matrix to the power of n using exponentiation by squaring.
|
|
*/
|
|
static FibMatrix matrix_power(FibMatrix base, uint32_t n) {
|
|
FibMatrix result = {1, 0, 0, 1}; // Identity matrix
|
|
while (n > 0) {
|
|
if (n % 2 == 1)
|
|
result = matrix_multiply(result, base);
|
|
base = matrix_multiply(base, base);
|
|
n /= 2;
|
|
}
|
|
return result;
|
|
}
|
|
|
|
uint64_t fibonacci_matrix(uint32_t n) {
|
|
if (n == 0) return 0;
|
|
FibMatrix base = {1, 1, 1, 0};
|
|
FibMatrix result = matrix_power(base, n - 1);
|
|
return result.a;
|
|
}
|
|
|
|
int main() {
|
|
for (uint32_t i = 0; i <= 20; ++i) {
|
|
printf("F(%u) = %lu\n", i, fibonacci_matrix(i));
|
|
}
|
|
return 0;
|
|
}
|