Merge branch 'main' of github.com:braxtonhall/fib

18 files changed, 229 insertions, 5 deletions

diff --git a/.editorconfig b/.editorconfig
new file mode 100644
index 0000000..c57f5e7
--- /dev/null
+++ b/.editorconfig
@@ -0,0 +1,11 @@
+root = true
+
+[*]
+charset = utf-8
+trim_trailing_whitespace = true
+insert_final_newline = true
+indent_style = tab
+indent_size = 4
+
+[*.md]
+trim_trailing_whitespace = false
diff --git a/.gitignore b/.gitignore
index b25ede3..c7e318c 100644
--- a/.gitignore
+++ b/.gitignore
@@ -1,3 +1,4 @@
 node_modules
 *.log
-*.pem
\ No newline at end of file
+*.pem
+.DS_Store
diff --git a/.gitmodules b/.gitmodules
new file mode 100644
index 0000000..1088a73
--- /dev/null
+++ b/.gitmodules
@@ -0,0 +1,3 @@
+[submodule "entries/wilbowma/fib-lang"]
+	path = entries/wilbowma/fib-lang
+	url = git@github.com:wilbowma/fib-lang.git
diff --git a/README.md b/README.md
index fffae69..4eb6fa1 100644
--- a/README.md
+++ b/README.md
@@ -5,7 +5,7 @@ Can you please give me a Fibonacci function? Ideally (but not necessarily) one t
 For a submission to the upcoming "Reclaim your space" exhibition at [Hatch Art Gallery](https://www.instagram.com/hatch_artgallery).
 
 ### [`adirar111`](https://github.com/adirar111)
-- [`y86`](./entries/adirar111/y86/fib.ys)
+- [`y86`](./entries/adirar111/y86/fib.s)
 
 ### [`braxtonhall`](https://github.com/braxtonhall)
 - [`adam`](./entries/braxtonhall/adam/main.py) (WIP)
@@ -15,12 +15,34 @@ For a submission to the upcoming "Reclaim your space" exhibition at [Hatch Art G
 <!-- - `smt` compiles to SMT, and the solver gives you the fib sequence -->
 <!-- - `imperitive-church` imperitive implementation in the lambda calculus -->
 
+### [`ionathanch`](https://github.com/ionathanch)
+- [`agda`](./entries/ionathanch/agda/Fib.agda)
+
+### [`funemy`](https://github.com/funemy)
+- [`agda`](./entries/funemy/agda/fib1.agda)
+- [`z3`](./entries/funemy/z3/z3fib.sh)
+
 ### [`jyoo980`](https://github.com/jyoo980)
 - [`scala`](./entries/jyoo980/scala/Fib.scala)
 
+### [`margoseltzer`](https://github.com/margoseltzer)
+- [`efficiency`](./entries/margoseltzer/efficiency.c)
+
 ### [`Metroxe`](https://github.com/Metroxe)
 - [`html`](./entries/Metroxe/index.html)
 
+### [`nritschel`](https://github.com/nritschel)
+- [`fib-java`](./entries/nritschel/fib-java/src)
+
+### [`shayanh`](https://github.com/shayanh)
+- [`matrix`](./entries/shayanh/matrix.go)
+
+### [`Tarcisio-Teixeira`](https://github.com/Tarcisio-Teixeira)
+- [`logn?`](./entries/Tarcisio-Teixeira/fib.py)
+
+### [`wilbowma`](https://github.com/wilbowma)
+- [`fib-lang`](https://github.com/wilbowma/fib-lang/tree/2ec2d1dfd141220882d824cf3dac5b374ed291f3)
+
 ## Contributing
 To contribute just make a PR into the `main` branch!
 
diff --git a/entries/Tarcisio-Teixeira/fib.py b/entries/Tarcisio-Teixeira/fib.py
new file mode 100644
index 0000000..a73cdd2
--- /dev/null
+++ b/entries/Tarcisio-Teixeira/fib.py
@@ -0,0 +1,5 @@
+def fib(n,arr={},v =-1):
+    if v>=0:
+        arr[n]=v
+        return v
+    return arr[n] if n in arr.keys() else fib(n, arr, (2*n*n*n - 9*n*n+13*n)//6 if  n <= 3 else fib(n//2-1,arr)*fib(n-n//2,arr) + fib(n//2,arr)*fib(n-n//2+1,arr))
diff --git a/entries/adirar111/y86/fib.ys b/entries/adirar111/y86/fib.s
index 156c1ae..8aa62d2 100644
--- a/entries/adirar111/y86/fib.ys
+++ b/entries/adirar111/y86/fib.s
@@ -1,8 +1,13 @@
 # y86 implementation of
+#
 # def fibonacci(n):
-# if n <= 1:
-# return n
-# return fibonacci(n-1) + fibonacci(n-2)
+#     if n <= 1:
+#         return n
+#     return fibonacci(n-1) + fibonacci(n-2)
+#
+# run it:
+#  * https://www.students.cs.ubc.ca/~cs-313/simulator/?arch=y86&impl=seq
+#  * https://www.eecs.yorku.ca/~jonatan/simulator/?arch=y86&impl=seq
 
 .pos 0
 main:
diff --git a/entries/ionathanch/agda/Fib.agda b/entries/ionathanch/agda/Fib.agda
new file mode 100644
index 0000000..a12b0a5
--- /dev/null
+++ b/entries/ionathanch/agda/Fib.agda
@@ -0,0 +1,19 @@
+
+open import Agda.Builtin.Nat
+open import Agda.Builtin.List
+open import Agda.Builtin.Reflection
+
+data Fib : Nat → Nat → Set where
+  instance F0 : Fib 0 0
+  instance F1 : Fib 1 1
+  instance Fk : ∀ {k n m} → ⦃ Fib k n ⦄ → ⦃ Fib (suc k) m ⦄ → Fib (suc (suc k)) (n + m)
+
+fib' : ∀ k {n} → ⦃ Fib k n ⦄ → Nat
+fib' k {n} ⦃ fib ⦄ = n
+
+macro
+  fib : Term → Term → TC _
+  fib t hole = unify hole (def (quote fib') (arg i t ∷ []))
+    where i = arg-info visible (modality relevant quantity-ω)
+
+{- Get the [n]th Fibonacci number by normalization via C-n `fib [n]`. -}
diff --git a/entries/margoseltzer/efficiency.c b/entries/margoseltzer/efficiency.c
new file mode 100644
index 0000000..6e017f3
--- /dev/null
+++ b/entries/margoseltzer/efficiency.c
@@ -0,0 +1,23 @@
+unsigned long foo(unsigned long n) {
+     if (n < 2) return (n);
+     return(foo(n - 1) + foo(n - 2));
+}
+
+// Efficiency of expression
+
+unsigned long bar(unsigned long n) {
+    unsigned long i, last;
+    unsigned long sum, tmp;
+
+    if (n < 2) return (n);
+    last = 0;
+    sum = 1;
+    for (i = 2; i <= n; i++) {
+        tmp = sum;
+        sum += last;
+        last = tmp;
+    }
+    return (sum);
+}
+
+// Efficiency in resource utilization
diff --git a/entries/nritschel/fib-java/fib.iml b/entries/nritschel/fib-java/fib.iml
new file mode 100644
index 0000000..815e958
--- /dev/null
+++ b/entries/nritschel/fib-java/fib.iml
@@ -0,0 +1,13 @@
+<?xml version="1.0" encoding="UTF-8"?>
+<module type="JAVA_MODULE" version="4">
+  <component name="NewModuleRootManager" inherit-compiler-output="true">
+    <exclude-output />
+    <content url="file://$MODULE_DIR$">
+      <sourceFolder url="file://$MODULE_DIR$/src" isTestSource="false" />
+    </content>
+    <orderEntry type="inheritedJdk" />
+    <orderEntry type="sourceFolder" forTests="false" />
+    <orderEntry type="module-library">
+    </orderEntry>
+  </component>
+</module>
\ No newline at end of file
diff --git a/entries/nritschel/fib-java/src/CachedFibonacciNumberFactory.java b/entries/nritschel/fib-java/src/CachedFibonacciNumberFactory.java
new file mode 100644
index 0000000..5c404e8
--- /dev/null
+++ b/entries/nritschel/fib-java/src/CachedFibonacciNumberFactory.java
@@ -0,0 +1,13 @@
+import java.util.HashMap;
+
+public class CachedFibonacciNumberFactory implements FibonacciNumberFactory {
+    private final HashMap<Integer, FibonacciNumber> cachedNumbers = new HashMap<>();
+
+    @Override
+    public FibonacciNumber getFibonacciNumber(int num) {
+        if (!cachedNumbers.containsKey(num)) {
+            cachedNumbers.put(num, new FibonacciNumber(num));
+        }
+        return cachedNumbers.get(num);
+    }
+}
diff --git a/entries/nritschel/fib-java/src/FibonacciCalculator.java b/entries/nritschel/fib-java/src/FibonacciCalculator.java
new file mode 100644
index 0000000..8806c20
--- /dev/null
+++ b/entries/nritschel/fib-java/src/FibonacciCalculator.java
@@ -0,0 +1,3 @@
+public interface FibonacciCalculator {
+    public int calculateFibonacci(FibonacciNumber fib);
+}
diff --git a/entries/nritschel/fib-java/src/FibonacciCalculatorImpl.java b/entries/nritschel/fib-java/src/FibonacciCalculatorImpl.java
new file mode 100644
index 0000000..7bb5ee9
--- /dev/null
+++ b/entries/nritschel/fib-java/src/FibonacciCalculatorImpl.java
@@ -0,0 +1,17 @@
+public class FibonacciCalculatorImpl implements FibonacciCalculator {
+    private final FibonacciNumberFactory factory;
+
+    public FibonacciCalculatorImpl(FibonacciNumberFactory factory) {
+        this.factory = factory;
+    }
+
+    @Override
+    public int calculateFibonacci(FibonacciNumber fib) {
+        if (fib.getNumber() <= 2) {
+            return 1;
+        }
+        else {
+            return factory.getFibonacciNumber(fib.getNumber() - 1).calculate(this) + factory.getFibonacciNumber(fib.getNumber() - 2).calculate(this);
+        }
+    }
+}
diff --git a/entries/nritschel/fib-java/src/FibonacciNumber.java b/entries/nritschel/fib-java/src/FibonacciNumber.java
new file mode 100644
index 0000000..fc9381f
--- /dev/null
+++ b/entries/nritschel/fib-java/src/FibonacciNumber.java
@@ -0,0 +1,19 @@
+public class FibonacciNumber {
+    private final int number;
+    private Integer result;
+
+    public FibonacciNumber(int number) {
+        this.number = number;
+    }
+
+    public int getNumber() {
+        return number;
+    }
+
+    public int calculate(FibonacciCalculator calculator) {
+        if (result == null) {
+            result = calculator.calculateFibonacci(this);
+        }
+        return result;
+    }
+}
diff --git a/entries/nritschel/fib-java/src/FibonacciNumberFactory.java b/entries/nritschel/fib-java/src/FibonacciNumberFactory.java
new file mode 100644
index 0000000..42ef6c2
--- /dev/null
+++ b/entries/nritschel/fib-java/src/FibonacciNumberFactory.java
@@ -0,0 +1,3 @@
+public interface FibonacciNumberFactory {
+    public FibonacciNumber getFibonacciNumber(int num);
+}
diff --git a/entries/nritschel/fib-java/src/Main.java b/entries/nritschel/fib-java/src/Main.java
new file mode 100644
index 0000000..8ae46f1
--- /dev/null
+++ b/entries/nritschel/fib-java/src/Main.java
@@ -0,0 +1,21 @@
+public class Main {
+    public static void main(String[] args) {
+        if (args.length < 1) {
+            System.out.println("""
+                    Please provide:
+                    1. fibonacci number to compute, and
+                    2. (optional) the calculation method (naive or cached).""");
+        }
+        else {
+            FibonacciNumberFactory factory;
+            if (args.length >= 2 && args[1].equals("naive")) {
+                factory = new NaiveFibonacciNumberFactory();
+            }
+            else {
+                factory = new CachedFibonacciNumberFactory();
+            }
+            FibonacciCalculator calculator = new FibonacciCalculatorImpl(factory);
+            System.out.println(factory.getFibonacciNumber(Integer.parseInt(args[0])).calculate(calculator));
+        }
+    }
+}
diff --git a/entries/nritschel/fib-java/src/NaiveFibonacciNumberFactory.java b/entries/nritschel/fib-java/src/NaiveFibonacciNumberFactory.java
new file mode 100644
index 0000000..5185a8b
--- /dev/null
+++ b/entries/nritschel/fib-java/src/NaiveFibonacciNumberFactory.java
@@ -0,0 +1,6 @@
+public class NaiveFibonacciNumberFactory implements FibonacciNumberFactory {
+    @Override
+    public FibonacciNumber getFibonacciNumber(int num) {
+        return new FibonacciNumber(num);
+    }
+}
diff --git a/entries/shayanh/matrix.go b/entries/shayanh/matrix.go
new file mode 100644
index 0000000..3f374cb
--- /dev/null
+++ b/entries/shayanh/matrix.go
@@ -0,0 +1,40 @@
+package main
+
+type fibmat [2][2]int
+
+func matmul(m1 fibmat, m2 fibmat) (m3 fibmat) {
+	for i := 0; i < 2; i++ {
+		for j := 0; j < 2; j++ {
+			for k := 0; k < 2; k++ {
+				m3[i][j] += m1[i][k] * m2[k][j]
+			}
+		}
+	}
+	return
+}
+
+func matpow(m fibmat, n int) fibmat {
+	if n == 0 {
+		return [2][2]int{
+			{1, 0},
+			{0, 1},
+		}
+	} else if n%2 == 0 {
+		t := matpow(m, n/2)
+		return matmul(t, t)
+	} else {
+		t := matpow(m, n-1)
+		return matmul(t, m)
+	}
+}
+
+func fib(n int) int {
+	m := matpow(
+		[2][2]int{
+			{1, 1},
+			{1, 0},
+		},
+		n,
+	)
+	return m[0][1]
+}
diff --git a/entries/wilbowma/fib-lang b/entries/wilbowma/fib-lang
new file mode 160000
+Subproject 2ec2d1dfd141220882d824cf3dac5b374ed291f