Struct Fib

pub struct Fib;

A utility struct for computing Fibonacci numbers efficiently.

This struct provides static methods for calculating Fibonacci numbers using highly optimized algorithms. It supports both single Fibonacci number calculation and generating ranges of consecutive Fibonacci numbers.

The implementation uses a fast doubling algorithm for O(log n) time complexity and leverages parallel processing for range calculations to maximize performance.

For Fibonacci numbers beyond F(185), the implementation automatically switches to using BigUint for arbitrary precision, ensuring correct results for extremely large Fibonacci numbers.

Implementations

impl Fib

pub fn single(n: u128) -> BigUint

Calculate the nth Fibonacci number using an optimized fast doubling algorithm.

This method efficiently computes Fibonacci numbers of arbitrary size by using a divide-and-conquer approach based on matrix identities.

Arguments

• n - The index of the Fibonacci number to calculate (0-indexed, where F(0)=0, F(1)=1)

Returns

• The nth Fibonacci number as a BigUint

Complexity

• Time complexity: O(log n) due to the fast doubling algorithm
• Space complexity: O(log n) for the recursive call stack

Examples

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

assert_eq!(Fib::single(0), BigUint::zero()); // F(0) = 0
assert_eq!(Fib::single(10), BigUint::from(55u32)); // F(10) = 55
assert!(Fib::single(200) > BigUint::from(u128::MAX)); // Large value example (would overflow primitive types)

pub fn range(start: u128, end: u128) -> Vec<BigUint>

Generates Fibonacci numbers for indices in the given inclusive range.

This method efficiently computes a sequence of consecutive Fibonacci numbers using parallel processing for improved performance. It divides the requested range into optimal chunks based on the available CPU threads, calculates each chunk in parallel, and then combines the results.

The implementation uses a hybrid approach that:

1. Uses the fast doubling algorithm to efficiently find the starting values for each chunk
2. Computes subsequent Fibonacci numbers iteratively within each chunk
3. Processes chunks in parallel using the Rayon library

Arguments

• start - The starting index of the range
• end - The ending index of the range (inclusive)

Returns

• A Vec<BigUint> containing ordered Fibonacci numbers for indices in the specified inclusive range.

Complexity

• Time complexity: Approximately O(n/t + log(start)) where n is the range size and t is the number of threads.
• Space complexity: O(n) for storing the Fibonacci numbers in a vector.

Performance

Performance scales with the number of available CPU cores. For large ranges, the parallelization provides significant speedup compared to sequential calculation.

Examples

use fib_rs::Fib;
use num_bigint::BigUint;
use num_traits::{Zero, One};

// Generate Fibonacci numbers from index 3 to 10 (both 3 and 10 inclusive)
let fibs = Fib::range(3, 10);

assert_eq!(fibs.len(), 8); // indices 3 to 10
assert_eq!(fibs[0], BigUint::from(2u32)); // F(3) = 2
assert_eq!(fibs[7], BigUint::from(55u32)); // F(10) = 55

For large ranges, the parallel implementation provides significant performance improvements:

use fib_rs::Fib;

// Generate 10,000 consecutive Fibonacci numbers efficiently
let large_range = Fib::range(1000, 10999);
assert_eq!(large_range.len(), 10000);