diff options
| -rw-r--r-- | entries/dewert99/big_fib.rs | 40 | ||||
| -rw-r--r-- | people.json | 4 |
2 files changed, 44 insertions, 0 deletions
diff --git a/entries/dewert99/big_fib.rs b/entries/dewert99/big_fib.rs new file mode 100644 index 0000000..f5cddbb --- /dev/null +++ b/entries/dewert99/big_fib.rs @@ -0,0 +1,40 @@ +use num_bigint::{BigUint, ToBigUint}; + +/// Returns (fib(n-1), fib(n), fib(n+1)) +fn fib_helper(n: u64) -> [BigUint; 3] { + let [fm1, f0, f1] = if n == 0 { + [ + 1.to_biguint().unwrap(), + 0.to_biguint().unwrap(), + 1.to_biguint().unwrap(), + ] + } else { + fib_helper2(n / 2) + }; + if n % 2 == 1 { + let [mut fm2, fm1, f0] = [fm1, f0, f1]; + fm1.clone_into(&mut fm2); + let f1 = fm2 + &f0; + [fm1, f0, f1] + } else { + [fm1, f0, f1] + } +} + +/// Returns (fib(2n-1), fib(2n), fib(2n+1)) +fn fib_helper2(n: u64) -> [BigUint; 3] { + let [fm1, fp0, fp1] = fib_helper(n); + // f2m1 = fm1^2 + fp0^2 + // f2p0 = fp1*fp0 + fp0*fm1 = fp0*(fp1+fm1) + // f2p1 = fp1^2 + fp0^2 + let f2p0 = (fp1.clone() + &fm1) * &fp0; + let fp0sqr = fp0.pow(2); + let f2m1 = fm1.pow(2) + &fp0sqr; + let f2p1 = fp1.pow(2) + fp0sqr; + [f2m1, f2p0, f2p1] +} + +pub fn fib(n: u64) -> BigUint { + let [_, res, _] = fib_helper(n); + res +} diff --git a/people.json b/people.json index b2a3b69..a88c3bc 100644 --- a/people.json +++ b/people.json @@ -410,6 +410,10 @@ { "name": "O(1)", "link": "./entries/dewert99/fib.rs" + }, + { + "name": "efficient bigint", + "link": "./entries/dewert99/big_fib.rs" } ] }, |