[−][src]Function fast_fibonacci::bigfib_with_mod
pub fn bigfib_with_mod(n: &BigUint, modulo: &BigUint) -> BigUint
BigUint version of fib_with_mod. Finds the nth fibonacci number with modulo. Runtime O(log(n))
Uses linear recurrence under the covers.
Examples
use num::FromPrimitive; let ns = vec![0, 1, 2, 3, 10, 1_000_000_000_000_000, 1_000_000_000_000_000, 1_955_995_342_096_516]; let modulos = vec![10, 10, 20, 30, 100, 1_000_000, 1_000, u64::MAX]; let expected_results = vec![0, 1, 1, 2, 55, 546_875, 875, 2_886_946_313_980_141_317]; for i in 0..ns.len() { assert_eq!( fast_fibonacci::bigfib_with_mod( &FromPrimitive::from_u64(ns[i]).unwrap(), &FromPrimitive::from_u64(modulos[i]).unwrap() ), FromPrimitive::from_u64(expected_results[i]).unwrap() ); }
use num_bigint::BigUint; let big_n: BigUint = BigUint::from_slice(&[100u32, 100, 100, 100, 15129, 12319]); let big_modulo: BigUint = BigUint::from_slice(&[14u32, 12, 1923876123, 12]); let expected_result: BigUint = BigUint::from_slice(&[2743227343u32, 920986447, 1158660944, 5]); assert_eq!( fast_fibonacci::bigfib_with_mod(&big_n, &big_modulo), expected_result );