From 6d818f6b49ba07f58e2447a659a4ea40da6c7894 Mon Sep 17 00:00:00 2001
From: David Ewert
Date: Wed, 26 Oct 2022 10:44:25 -0700
Subject: Create big_fib.rs

---
 entries/dewert99/big_fib.rs | 40 ++++++++++++++++++++++++++++++++++++++++
 1 file changed, 40 insertions(+)
 create mode 100644 entries/dewert99/big_fib.rs

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
+}
-- 
cgit v1.2.3-70-g09d2


From 75e2d41032b561a897da703f7c1938fe8be6a2d8 Mon Sep 17 00:00:00 2001
From: David Ewert
Date: Wed, 26 Oct 2022 10:46:09 -0700
Subject: Update people.json

---
 people.json | 6 +++++-
 1 file changed, 5 insertions(+), 1 deletion(-)

diff --git a/people.json b/people.json
index 7ec29e3..840da7f 100644
--- a/people.json
+++ b/people.json
@@ -296,7 +296,11 @@
             {
                 "name": "O(1)",
                 "link": "./entries/dewert99/fib.rs"
-            }
+            },
+			{
+                "name": "efficient bigint",
+                "link": "./entries/dewert99/big_fib.rs"
+            },
         ]
     }
 ]
-- 
cgit v1.2.3-70-g09d2


From b95216698ab68b13d11d3c60fd63b9d03d100b8d Mon Sep 17 00:00:00 2001
From: David Ewert
Date: Wed, 26 Oct 2022 10:49:49 -0700
Subject: -,

---
 people.json | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/people.json b/people.json
index 840da7f..b3d3f75 100644
--- a/people.json
+++ b/people.json
@@ -300,7 +300,7 @@
 			{
                 "name": "efficient bigint",
                 "link": "./entries/dewert99/big_fib.rs"
-            },
+            }
         ]
     }
 ]
-- 
cgit v1.2.3-70-g09d2