feat(guests): Add fibonacci implementation using matrix exponentiation

Originally tried by Dimo Dimov

Co-authored-by: Dimo99 <dimodimov1999@gmail.com>

1 files changed, 10 insertions, 0 deletions

diff --git a/guests/fibonacci_matrix/src/lib.rs b/guests/fibonacci_matrix/src/lib.rs
new file mode 100644
index 0000000..bc20dd2
--- /dev/null
+++ b/guests/fibonacci_matrix/src/lib.rs
@@ -0,0 +1,10 @@
+#![cfg_attr(feature = "no_std", no_std)]
+
+use nalgebra::Matrix2;
+
+#[guests_macro::proving_entrypoint]
+pub fn main(n: u8, fN: u64) -> bool {
+    let r = Matrix2::new(1, 1, 1, 0).pow((n - 1).into())[(0, 0)];
+
+    r == fN
+}