diff options
| -rw-r--r-- | .editorconfig | 11 | ||||
| -rw-r--r-- | .gitignore | 3 | ||||
| -rw-r--r-- | .gitmodules | 3 | ||||
| -rw-r--r-- | README.md | 24 | ||||
| -rw-r--r-- | entries/Tarcisio-Teixeira/fib.py | 5 | ||||
| -rw-r--r-- | entries/adirar111/y86/fib.s (renamed from entries/adirar111/y86/fib.ys) | 11 | ||||
| -rw-r--r-- | entries/ionathanch/agda/Fib.agda | 19 | ||||
| -rw-r--r-- | entries/margoseltzer/efficiency.c | 23 | ||||
| -rw-r--r-- | entries/nritschel/fib-java/fib.iml | 13 | ||||
| -rw-r--r-- | entries/nritschel/fib-java/src/CachedFibonacciNumberFactory.java | 13 | ||||
| -rw-r--r-- | entries/nritschel/fib-java/src/FibonacciCalculator.java | 3 | ||||
| -rw-r--r-- | entries/nritschel/fib-java/src/FibonacciCalculatorImpl.java | 17 | ||||
| -rw-r--r-- | entries/nritschel/fib-java/src/FibonacciNumber.java | 19 | ||||
| -rw-r--r-- | entries/nritschel/fib-java/src/FibonacciNumberFactory.java | 3 | ||||
| -rw-r--r-- | entries/nritschel/fib-java/src/Main.java | 21 | ||||
| -rw-r--r-- | entries/nritschel/fib-java/src/NaiveFibonacciNumberFactory.java | 6 | ||||
| -rw-r--r-- | entries/shayanh/matrix.go | 40 | ||||
| m--------- | entries/wilbowma/fib-lang | 0 |
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 @@ -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 @@ -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 |