#fibonacci-number #fibonacci #linear #recurrence #performance

fast-fibonacci

Quickly find nth fibonacci number with modulo. Supports u64 and BigUint.

4 releases

0.2.0 Oct 20, 2020
0.1.2 Oct 19, 2020
0.1.1 Oct 19, 2020
0.1.0 Oct 19, 2020

#19 in #fibonacci-number

23 downloads per month

GPL-3.0-or-later

16KB
168 lines

fast-fibonacci Crate Build Status

Quickly find nth fibonacci number, with modulo.

fn fib_with_mod(n: u64, modulo: u64) -> u64

Uses linear recurrence to find nth fibonacci number with modulo. O(log(n))

fn bigfib_with_mod(n: &BigUint, modulo: &BigUint) -> BigUint

BigUint version of fib_with_mod. Uses linear recurrence to find nth fibonacci number with modulo. O(log(n))


lib.rs:

fast-fibonacci

fast-fibonacci uses linear recurrence to quickly find fib(n, mod) in O(log(n)) time.

Adapted from http://fusharblog.com/solving-linear-recurrence-for-programming-contest/

Dependencies

~2MB
~36K SLoC