Crate fib_rs

fib-rs

A highly optimized Fibonacci number calculator for Rust that efficiently computes arbitrarily large Fibonacci numbers.

Features

• Fast doubling algorithm: Calculates Fibonacci numbers in O(log n) time
• Handles massive inputs: Compute Fibonacci numbers up to F(10,000,000) and beyond
• Range calculation: Generate sequences of consecutive Fibonacci numbers with parallel processing
• BigUint support: Uses arbitrary precision integers for handling large Fibonacci numbers

Examples

use fib_rs::Fib;
use num_bigint::BigUint;
use num_traits::Zero;

// Calculate a single Fibonacci number
let n = 100;
let result = Fib::single(n);
assert!(result > BigUint::zero());

// Calculate a range of Fibonacci numbers (F(3) through F(10))
let start = 3;
let end = 10;
let results = Fib::range(start, end);
assert_eq!(results.len(), (end - start + 1) as usize);

Algorithm Details

Single Fibonacci Number

For computing a single Fibonacci number, this implementation uses the fast doubling algorithm with logarithmic time complexity:

• For even n: F(2k) = F(k) * (2*F(k+1) - F(k))
• For odd n: F(2k+1) = F(k+1)^2 + F(k)^2

Fibonacci Range

The range implementation combines three approaches for optimal performance:

1. Parallel processing: Divides the requested range into optimal chunks based on available CPU threads
2. Smart initialization: Uses the fast doubling algorithm to efficiently find the starting values for each chunk
3. Iterative calculation: After finding starting values, computes subsequent Fibonacci numbers iteratively within each chunk

Structs

Fib

A utility struct for computing Fibonacci numbers efficiently.