[][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
);