Merge pull request #51 from dewert99/main

Fib with BigInts

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"
             }
         ]
     },