fib-rs

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

Try the web demo

Table of Contents

• Features
• Installation
• Usage
• Performance
• Algorithm Details
• Web Demo
• License
• Contributing

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
• CLI application: Simple command-line interface for quick calculations of single values or ranges

Installation

Library

To use as a dependency in your project:

cargo add fib-rs --no-default-features

CLI Tool

To install the command-line tool with cargo for all platforms (recommended):

cargo install fib-rs

Or for Linux only:

curl -fsSL https://raw.githubusercontent.com/excoffierleonard/fib-rs/main/scripts/install.sh | sh

Usage

As a library

use fib_rs::Fib;

// Calculate F(100)
let n = 100;
let result = Fib::single(n);
// Print the result
println!("F({}) = {}", n, result);

// Calculate a range of Fibonacci numbers (F(3) through F(10))
let start = 3;
let end = 10;
let results = Fib::range(start, end);
// Print the results
(start..=end)
    .zip(results.iter())
    .for_each(|(i, result)| println!("F({}) = {}", i, result));

Command-line application

Single

fib single 100

F(100) = 354224848179261915075

Range

fib range 6 10

F(6) = 8
F(7) = 13
F(8) = 21
F(9) = 34
F(10) = 55

Performance

Specifications:

• 15-inch MacBook Air (2025)
• M4 Chip, 10C CPU, 10C GPU
• 32GB Unified Memory
• macOS Tahoe 26.2

Single	Computation Time
F(1,000)	~876ns
F(10,000)	~8.38μs
F(100,000)	~332μs
F(1,000,000)	~10.6ms
F(10,000,000)	~323ms

Range	Computation Time
F(0) -> F(1,000)	~55.1μs
F(0) -> F(10,000)	~436μs
F(0) -> F(100,000)	~20.2ms

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) (2F(k+1) - F(k))

For odd n: F(2k+1) = F(k+1)^2 + F(k)^2

This divide-and-conquer approach is vastly more efficient than naive recursive or iterative methods for large inputs.

Fibonacci Range

The range implementation combines two 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

This hybrid approach provides excellent performance for generating sequences of consecutive Fibonacci numbers, especially for large ranges, by leveraging multi-core processing while maintaining mathematical efficiency.

Web Demo

Try the interactive web demo to calculate Fibonacci numbers directly in your browser. The demo showcases the library's performance and capabilities through a WebAssembly implementation.

License

This project is licensed under the MIT License.

Contributing

Contributions are welcome! Please feel free to submit a Pull Request.