From 77a33a73cc11e2a4a66db549f43ec5f0e0c6eb56 Mon Sep 17 00:00:00 2001
From: braxtonhall
Date: Sun, 23 Oct 2022 19:29:26 -0700
Subject: Add Reid's contribution
---
.../Fibonacci series in JavaScript - Stack Overflow.webloc | 8 ++++++++
1 file changed, 8 insertions(+)
create mode 100644 entries/rtholmes/Fibonacci series in JavaScript - Stack Overflow.webloc
(limited to 'entries')
diff --git a/entries/rtholmes/Fibonacci series in JavaScript - Stack Overflow.webloc b/entries/rtholmes/Fibonacci series in JavaScript - Stack Overflow.webloc
new file mode 100644
index 0000000..939529d
--- /dev/null
+++ b/entries/rtholmes/Fibonacci series in JavaScript - Stack Overflow.webloc
@@ -0,0 +1,8 @@
+
+
+
+
+ URL
+ https://stackoverflow.com/a/55764043
+
+
--
cgit v1.2.3-70-g09d2
From 4c717196fd630c5c207e114ffa9ca9c301eb1198 Mon Sep 17 00:00:00 2001
From: Jonathan Chan
Date: Sun, 23 Oct 2022 23:07:43 -0400
Subject: Fortran :) (also moved my Agda file up a dir)
---
README.md | 3 ++-
entries/ionathanch/Fib.agda | 19 +++++++++++++++++++
entries/ionathanch/agda/Fib.agda | 19 -------------------
entries/ionathanch/fib.f90 | 21 +++++++++++++++++++++
4 files changed, 42 insertions(+), 20 deletions(-)
create mode 100644 entries/ionathanch/Fib.agda
delete mode 100644 entries/ionathanch/agda/Fib.agda
create mode 100644 entries/ionathanch/fib.f90
(limited to 'entries')
diff --git a/README.md b/README.md
index 51ade8f..0fcbc53 100644
--- a/README.md
+++ b/README.md
@@ -16,7 +16,8 @@ For a submission to the upcoming "Reclaim your space" exhibition at [Hatch Art G
### [`ionathanch`](https://github.com/ionathanch)
-- [`agda`](./entries/ionathanch/agda/Fib.agda)
+- [`agda`](./entries/ionathanch/Fib.agda)
+- [`fortran`](./entries/ionathanch/fib.f90)
### [`funemy`](https://github.com/funemy)
- [`agda`](./entries/funemy/agda/fib1.agda)
diff --git a/entries/ionathanch/Fib.agda b/entries/ionathanch/Fib.agda
new file mode 100644
index 0000000..a12b0a5
--- /dev/null
+++ b/entries/ionathanch/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/ionathanch/agda/Fib.agda b/entries/ionathanch/agda/Fib.agda
deleted file mode 100644
index a12b0a5..0000000
--- a/entries/ionathanch/agda/Fib.agda
+++ /dev/null
@@ -1,19 +0,0 @@
-
-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/ionathanch/fib.f90 b/entries/ionathanch/fib.f90
new file mode 100644
index 0000000..3cf1850
--- /dev/null
+++ b/entries/ionathanch/fib.f90
@@ -0,0 +1,21 @@
+PROGRAM main
+ ! The 93rd Fibonacci number is the largest that fits in 64 bits anyway
+ CHARACTER(3) :: kth
+ INTEGER :: k
+ CALL get_command_argument(1, kth)
+ READ(kth, *) k
+ WRITE(*, *) fib(k)
+CONTAINS
+
+PURE RECURSIVE INTEGER*8 FUNCTION fib(k) RESULT(n)
+ INTEGER, INTENT (IN) :: k
+ IF (k == 0) THEN
+ n = 0
+ ELSE IF (k == 1) THEN
+ n = 1
+ ELSE
+ n = fib(k - 1) + fib(k - 2)
+ END IF
+END FUNCTION fib
+
+END PROGRAM
--
cgit v1.2.3-70-g09d2
From 5a918f5a59e0e3b3af1ef75b5251b9f7ae7a15e8 Mon Sep 17 00:00:00 2001
From: Perry Liao
Date: Sun, 23 Oct 2022 20:17:53 -0700
Subject: Create Jenkins groovy pipeline for fib
---
entries/perryliao/fib.groovy | 48 ++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 48 insertions(+)
create mode 100644 entries/perryliao/fib.groovy
(limited to 'entries')
diff --git a/entries/perryliao/fib.groovy b/entries/perryliao/fib.groovy
new file mode 100644
index 0000000..af1c4df
--- /dev/null
+++ b/entries/perryliao/fib.groovy
@@ -0,0 +1,48 @@
+pipeline {
+ agent any
+
+ parameters {
+ string defaultValue: '2', description: 'Number to compute in the Fibonacci Sequence', name: 'num', trim: true
+ }
+
+ stages {
+ stage('Create Cache') {
+ steps {
+ script {
+ if (!fileExists("fibbonacciCache")) {
+ sh 'echo "0\n1" > fibbonacciCache'
+ }
+ }
+ }
+ }
+ stage('Validate Parameter') {
+ steps {
+ script {
+ assert params.num.isInteger()
+ }
+ }
+ }
+ stage('Get Fibbonacci') {
+ steps {
+ script {
+ result = fib(params.num.toInteger())
+ println("The result is F(${params.num}) = ${result}")
+ }
+ }
+ }
+ }
+}
+
+int fib(int n, cache = 'fibbonacciCache') {
+ nComputed = sh(returnStdout: true, script: "wc -l < ${cache}").trim().toInteger()
+ if (n >= nComputed) {
+ // Need to do more recursion
+ result = fib(n - 2, cache) + fib(n - 1, cache)
+ sh "echo '${result}' >> ${cache}"
+ return result
+ } else {
+ // Already have what we need, so read from cache
+ return sh(returnStdout: true, script: "sed -n '${n + 1}p' ${cache}").trim().toInteger()
+ }
+}
+
--
cgit v1.2.3-70-g09d2
From f426d8a9b0b17336838b8840a4e5374f34949383 Mon Sep 17 00:00:00 2001
From: Megha Singhania
Date: Sun, 23 Oct 2022 20:29:52 -0700
Subject: bash: add fib function
---
entries/meghasinghania22/bash/script.sh | 27 +++++++++++++++++++++++++++
1 file changed, 27 insertions(+)
create mode 100644 entries/meghasinghania22/bash/script.sh
(limited to 'entries')
diff --git a/entries/meghasinghania22/bash/script.sh b/entries/meghasinghania22/bash/script.sh
new file mode 100644
index 0000000..0cbba4d
--- /dev/null
+++ b/entries/meghasinghania22/bash/script.sh
@@ -0,0 +1,27 @@
+#!/bin/bash
+int_regex='^[0-9]+$'
+function fib(){
+ if [ "$1" -le 1 ]; then
+ echo $1
+ else
+ echo $[`fib $[$1 - 1]` + `fib $[$1 - 2]` ]
+ fi
+}
+
+function main(){
+ echo -n "Enter a whole number: "
+ read num
+
+ if [ -z "$num" ]; then
+ echo "Uh oh! Argument required!"
+ elif ! [[ "$num" =~ $int_regex ]]; then
+ echo "Uh oh! Argument must be a number :|"
+ elif [ "$num" -lt 0 ]; then
+ echo "Uh oh! Argument must be a whole number :|"
+ else
+ fib $num
+ fi
+
+}
+
+main
\ No newline at end of file
--
cgit v1.2.3-70-g09d2
From 1df988400399d3147514cf42a132141b7f5d8194 Mon Sep 17 00:00:00 2001
From: Perry Liao
Date: Sun, 23 Oct 2022 20:46:17 -0700
Subject: make only 1 wc call
---
entries/perryliao/fib.groovy | 14 ++++++++------
1 file changed, 8 insertions(+), 6 deletions(-)
(limited to 'entries')
diff --git a/entries/perryliao/fib.groovy b/entries/perryliao/fib.groovy
index af1c4df..168913f 100644
--- a/entries/perryliao/fib.groovy
+++ b/entries/perryliao/fib.groovy
@@ -9,8 +9,8 @@ pipeline {
stage('Create Cache') {
steps {
script {
- if (!fileExists("fibbonacciCache")) {
- sh 'echo "0\n1" > fibbonacciCache'
+ if (!fileExists("fibCache")) {
+ sh 'echo "0\n1" > fibCache'
}
}
}
@@ -25,6 +25,7 @@ pipeline {
stage('Get Fibbonacci') {
steps {
script {
+ nComputed = sh(returnStdout: true, script: "wc -l < fibCache").trim().toInteger()
result = fib(params.num.toInteger())
println("The result is F(${params.num}) = ${result}")
}
@@ -33,16 +34,17 @@ pipeline {
}
}
-int fib(int n, cache = 'fibbonacciCache') {
- nComputed = sh(returnStdout: true, script: "wc -l < ${cache}").trim().toInteger()
+def nComputed
+
+int fib(int n, cache = 'fibCache') {
if (n >= nComputed) {
// Need to do more recursion
result = fib(n - 2, cache) + fib(n - 1, cache)
+ nComputed++
sh "echo '${result}' >> ${cache}"
return result
} else {
// Already have what we need, so read from cache
- return sh(returnStdout: true, script: "sed -n '${n + 1}p' ${cache}").trim().toInteger()
+ return sh(returnStdout: true, script: "sed -n '${n + 1}p' ${cache}").toInteger()
}
}
-
--
cgit v1.2.3-70-g09d2
From 2f4fab9864a91d69d2b705430f6633bdfe7f5dd5 Mon Sep 17 00:00:00 2001
From: Perry Liao
Date: Sun, 23 Oct 2022 20:56:25 -0700
Subject: validation should probably come first lol
---
entries/perryliao/fib.groovy | 12 ++++++------
1 file changed, 6 insertions(+), 6 deletions(-)
(limited to 'entries')
diff --git a/entries/perryliao/fib.groovy b/entries/perryliao/fib.groovy
index 168913f..d625d68 100644
--- a/entries/perryliao/fib.groovy
+++ b/entries/perryliao/fib.groovy
@@ -6,19 +6,19 @@ pipeline {
}
stages {
- stage('Create Cache') {
+ stage('Validate Parameter') {
steps {
script {
- if (!fileExists("fibCache")) {
- sh 'echo "0\n1" > fibCache'
- }
+ assert params.num.isInteger()
}
}
}
- stage('Validate Parameter') {
+ stage('Create Cache') {
steps {
script {
- assert params.num.isInteger()
+ if (!fileExists("fibCache")) {
+ sh 'echo "0\n1" > fibCache'
+ }
}
}
}
--
cgit v1.2.3-70-g09d2
From 81fdbeb7fa4d8a80d028a988c353c3fa16d4953b Mon Sep 17 00:00:00 2001
From: Aymen Dirar
Date: Sun, 23 Oct 2022 23:06:51 -0700
Subject: wasm lol
---
entries/adirar111/wasm/fib.wasm | Bin 0 -> 144 bytes
entries/adirar111/wasm/fib.wat | 46 ++++++++++++++++++++++++++++++++++++++
entries/adirar111/wasm/index.html | 21 +++++++++++++++++
entries/adirar111/wasm/index.js | 21 +++++++++++++++++
entries/adirar111/wasm/style.css | 27 ++++++++++++++++++++++
5 files changed, 115 insertions(+)
create mode 100644 entries/adirar111/wasm/fib.wasm
create mode 100644 entries/adirar111/wasm/fib.wat
create mode 100644 entries/adirar111/wasm/index.html
create mode 100644 entries/adirar111/wasm/index.js
create mode 100644 entries/adirar111/wasm/style.css
(limited to 'entries')
diff --git a/entries/adirar111/wasm/fib.wasm b/entries/adirar111/wasm/fib.wasm
new file mode 100644
index 0000000..6a93250
Binary files /dev/null and b/entries/adirar111/wasm/fib.wasm differ
diff --git a/entries/adirar111/wasm/fib.wat b/entries/adirar111/wasm/fib.wat
new file mode 100644
index 0000000..b9eba78
--- /dev/null
+++ b/entries/adirar111/wasm/fib.wat
@@ -0,0 +1,46 @@
+;; iterative fib(n) in web assembly text format (wat)
+;; this gets compiled to fib.wasm binary
+;; and gets fetched via a data URL in index.js
+(module
+ (export "fib" (func $fib))
+ (func $fib (param $n i32) (result i32)
+ (local $last i32)
+ (local $sum i32)
+ (local $i i32)
+ (local $tmp i32)
+ (if
+ (i32.lt_s
+ (local.get $n)
+ (i32.const 2)
+ )
+ (return (local.get $n))
+ )
+ (local.set $last (i32.const 0))
+ (local.set $sum (i32.const 1))
+ (local.set $i (i32.const 2))
+ (local.set $n (i32.add (local.get $n) (i32.const 1)))
+ (loop $loop
+ (local.set $tmp (local.get $sum))
+ (local.set $sum
+ (i32.add
+ (local.get $sum)
+ (local.get $last)
+ )
+ )
+ (local.set $last (local.get $tmp))
+ (local.set $i
+ (i32.add
+ (local.get $i)
+ (i32.const 1)
+ )
+ )
+ (br_if $loop
+ (i32.lt_s
+ (local.get $i)
+ (local.get $n)
+ )
+ )
+ )
+ (return (local.get $sum))
+ )
+)
diff --git a/entries/adirar111/wasm/index.html b/entries/adirar111/wasm/index.html
new file mode 100644
index 0000000..8357a55
--- /dev/null
+++ b/entries/adirar111/wasm/index.html
@@ -0,0 +1,21 @@
+
+
+
+ wasm fib
+
+
+
+
+ go ahead, type a number
+
+
+
+
+ fib.wasm says:
+
+
+
+
diff --git a/entries/adirar111/wasm/index.js b/entries/adirar111/wasm/index.js
new file mode 100644
index 0000000..43ee9a6
--- /dev/null
+++ b/entries/adirar111/wasm/index.js
@@ -0,0 +1,21 @@
+const wasmBinaryBase64 = "AGFzbQEAAAABBgFgAX8BfwMCAQAHBwEDZmliAAAKRwFFAQR/IABBAkgEQCAADwtBACEBQQEhAkECIQMgAEEBaiEAA0AgAiEEIAIgAWohAiAEIQEgA0EBaiEDIAMgAEgNAAsgAg8LACgEbmFtZQEGAQADZmliAhkBAAUAAW4BBGxhc3QCA3N1bQMBaQQDdG1w"
+const wasmBinaryDataURL = `data:application/wasm;base64,${wasmBinaryBase64}`;
+
+WebAssembly.instantiateStreaming(fetch(wasmBinaryDataURL)).then(
+ (wasmObj) => {
+ const {fib: fibWasm} = wasmObj.instance.exports
+ const fib = (event) => {
+ event.preventDefault()
+ const input = document.getElementById("input")
+ const result = document.getElementById("result")
+ const n = parseInt(input.value)
+ if (isNaN(n)) {
+ result.textContent = "that's not a number..."
+ return
+ }
+ result.textContent = fibWasm(n)
+ }
+ const button = document.getElementById("compute")
+ button.onclick = fib
+ }
+);
diff --git a/entries/adirar111/wasm/style.css b/entries/adirar111/wasm/style.css
new file mode 100644
index 0000000..8ab403f
--- /dev/null
+++ b/entries/adirar111/wasm/style.css
@@ -0,0 +1,27 @@
+html {
+ background: #5a46ee;
+ color: #fff;
+ font-family: "Source Code Pro"
+}
+
+body {
+ display: flex;
+ flex-direction: column;
+ justify-content: center;
+ align-items: center;
+}
+
+#input-area {
+ display: flex;
+ flex-direction: row;
+ justify-content: space-between;
+}
+
+#input {
+ height: 40px;
+ font-size: 30px
+}
+
+#result {
+ font-size: 50px
+}
--
cgit v1.2.3-70-g09d2
From 51ebb554063aa504668e939c766236967829b94b Mon Sep 17 00:00:00 2001
From: Aymen Dirar
Date: Sun, 23 Oct 2022 23:16:59 -0700
Subject: comment
---
entries/adirar111/wasm/fib.wat | 2 +-
1 file changed, 1 insertion(+), 1 deletion(-)
(limited to 'entries')
diff --git a/entries/adirar111/wasm/fib.wat b/entries/adirar111/wasm/fib.wat
index b9eba78..255fa12 100644
--- a/entries/adirar111/wasm/fib.wat
+++ b/entries/adirar111/wasm/fib.wat
@@ -1,5 +1,5 @@
;; iterative fib(n) in web assembly text format (wat)
-;; this gets compiled to fib.wasm binary
+;; this gets compiled to the fib.wasm binary
;; and gets fetched via a data URL in index.js
(module
(export "fib" (func $fib))
--
cgit v1.2.3-70-g09d2
From 5e2b3d53917bb6a39dbffd0db6888bacaa283536 Mon Sep 17 00:00:00 2001
From: Aymen Dirar
Date: Sun, 23 Oct 2022 23:29:34 -0700
Subject: handle negative
---
entries/adirar111/wasm/index.js | 6 ++++--
1 file changed, 4 insertions(+), 2 deletions(-)
(limited to 'entries')
diff --git a/entries/adirar111/wasm/index.js b/entries/adirar111/wasm/index.js
index 43ee9a6..667ff82 100644
--- a/entries/adirar111/wasm/index.js
+++ b/entries/adirar111/wasm/index.js
@@ -10,8 +10,10 @@ WebAssembly.instantiateStreaming(fetch(wasmBinaryDataURL)).then(
const result = document.getElementById("result")
const n = parseInt(input.value)
if (isNaN(n)) {
- result.textContent = "that's not a number..."
- return
+ return result.textContent = "that wasn't very wasm of you"
+ }
+ if (n < 0) {
+ return result.textContent = "why are you being so negative"
}
result.textContent = fibWasm(n)
}
--
cgit v1.2.3-70-g09d2
From dcf99fd7ebf54474ea6d81ced6e00c28fba614fa Mon Sep 17 00:00:00 2001
From: rhiannon morris
Date: Mon, 24 Oct 2022 08:48:36 +0200
Subject: add maude & ATS
---
entries/lizard-business/fib.dats | 25 +++++++++++++++++++++++++
entries/lizard-business/fib.maude | 27 +++++++++++++++++++++++++++
people.json | 15 +++++++++++++++
3 files changed, 67 insertions(+)
create mode 100644 entries/lizard-business/fib.dats
create mode 100644 entries/lizard-business/fib.maude
(limited to 'entries')
diff --git a/entries/lizard-business/fib.dats b/entries/lizard-business/fib.dats
new file mode 100644
index 0000000..f6bd5a1
--- /dev/null
+++ b/entries/lizard-business/fib.dats
@@ -0,0 +1,25 @@
+#include "share/atspre_define.hats"
+#include "share/atspre_staload.hats"
+
+dataprop is_fib(int, int) =
+| F0(0, 0) | F1(1, 1)
+| {i, m, n : nat} Fplus(i + 2, m + n) of (is_fib(i, m), is_fib(i + 1, n))
+
+typedef fib(i : int) = [n : nat] (is_fib(i, n) | int(n))
+
+
+fun fib {t : nat} .<>. (t : int(t)) :<> fib(t) =
+let
+ fun go {m, n, i : nat | i <= t} ..
+ (M : is_fib(i, m), N : is_fib(i + 1, n) |
+ m : int(m), n : int(n), i : int(i)) :<>
+ fib(t) =
+ if i = t then (M | m)
+ else go(N, Fplus(M, N) | n, m + n, i + 1)
+in
+ go(F0, F1 | 0, 1, 0)
+end
+
+fun fib_(i : Nat) : Nat = let val (_ | res) = fib(i) in res end
+
+implement main0 () = println!("fib(15) = ", fib_(15))
diff --git a/entries/lizard-business/fib.maude b/entries/lizard-business/fib.maude
new file mode 100644
index 0000000..20bc428
--- /dev/null
+++ b/entries/lizard-business/fib.maude
@@ -0,0 +1,27 @@
+smod FIB is
+ pr LIST{Nat} .
+
+ vars M N : Nat .
+ var Ns : List{Nat} .
+
+ rl [start]: nil => 0 1 .
+ rl [next]: Ns M N => Ns M N (M + N) .
+ rl [drop] : Ns N => N .
+
+ strats fib fibgo : Nat @ List{Nat} .
+ sd fib(N) := start ; fibgo(N) .
+ sd fibgo(0) := top(drop) .
+ sd fibgo(s(N)) := top(next) ; fibgo(N) .
+endsm
+
+***(
+ Maude> srew nil using fib(10) .
+ srewrite in FIB : nil using fib(10) .
+
+ Solution 1
+ rewrites: 8330 in 12ms cpu (12ms real) (694166 rewrites/second)
+ result NzNat: 89
+
+ No more solutions.
+ rewrites: 8469 in 12ms cpu (13ms real) (705750 rewrites/second)
+)
diff --git a/people.json b/people.json
index cc5e8e3..526da06 100644
--- a/people.json
+++ b/people.json
@@ -70,6 +70,21 @@
}
]
},
+ {
+ "github": "lizard-business",
+ "name": "rhiannon morris",
+ "title": "amateur type system liker",
+ "entries": [
+ {
+ "name": "maude",
+ "link": "./entries/lizard-business/fib.maude"
+ },
+ {
+ "name": "ats",
+ "link": "./entries/lizard-business/fib.dats"
+ }
+ ]
+ },
{
"github": "margoseltzer",
"name": "Margo Seltzer",
--
cgit v1.2.3-70-g09d2
From b42ea5e994de56ffc7d4ec0e723261a147179b15 Mon Sep 17 00:00:00 2001
From: Felipe Bañados Schwerter
Date: Mon, 24 Oct 2022 10:46:18 -0600
Subject: Specified implementation in coq
---
entries/fbanados/fib.v | 90 ++++++++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 90 insertions(+)
create mode 100644 entries/fbanados/fib.v
(limited to 'entries')
diff --git a/entries/fbanados/fib.v b/entries/fbanados/fib.v
new file mode 100644
index 0000000..e9fe796
--- /dev/null
+++ b/entries/fbanados/fib.v
@@ -0,0 +1,90 @@
+Require Import Coq.Arith.Wf_nat. (* import strong induction on naturals *)
+Require Import Lia. (* Linear Integer Arithmetic solver *)
+
+(* First, simple specification *)
+
+Fixpoint fib_simpl (n : nat) {struct n} : nat :=
+ match n with
+ | 0 => 1
+ | S n => match n with
+ | 0 => 1
+ | S m => fib_simpl n + fib_simpl m
+ end
+ end.
+
+Example fib_3 : (fib_simpl 2 = 2). reflexivity. Qed.
+Example fib_4 : (fib_simpl 3 = 3). reflexivity. Qed.
+Example fib_5 : (fib_simpl 4 = 5). reflexivity. Qed.
+
+Lemma fib_simpl_spec : forall n, (* useful lemma for rewriting *)
+ fib_simpl (S (S n)) = fib_simpl (S n) + fib_simpl n.
+Proof.
+ destruct n.
+ - (* case n := 0 *)
+ reflexivity.
+ - (* case n := (S n) *)
+ destruct n; reflexivity.
+Qed.
+
+(* For a (slightly) faster version *)
+
+Fixpoint fib_acc_aux (n : nat) (acc : nat) (prev : nat) {struct n} : nat :=
+ match n with
+ | 0 => acc + prev
+ | S n => fib_acc_aux n (acc + prev) acc
+ end.
+
+Definition fib_faster (n : nat) : nat :=
+ match n with
+ | 0 => 1
+ | S n => match n with
+ | 0 => 1
+ | S m => (fib_acc_aux m 1 1)
+ end
+ end.
+
+Example fib_faster_3 : (fib_faster 2 = 2). reflexivity. Qed.
+Example fib_faster_4 : (fib_faster 3 = 3). reflexivity. Qed.
+Example fib_faster_5 : (fib_faster 4 = 5). reflexivity. Qed.
+
+Lemma fib_acc_aux_rewrite : forall n a b c d,
+ fib_acc_aux n a c + fib_acc_aux n b d = fib_acc_aux n (a + b) (c + d).
+Proof.
+ induction n; intros.
+ - (* case n := 0 *)
+ simpl; lia.
+ - (* case n := (S n) *)
+ simpl.
+ rewrite IHn.
+ f_equal.
+ lia.
+Qed.
+
+Theorem fib_faster_spec: forall n, fib_simpl n = fib_faster n.
+Proof.
+ induction n using lt_wf_ind. (* use strong induction *)
+ rename H into strong_induction_hypothesis.
+ destruct n. (* lt_wf_ind does not deal immediately with cases *)
+ - (* case n := 0 *)
+ reflexivity.
+ - (* case n := (S n) *)
+ destruct n.
+ + (* case n := 1 *)
+ reflexivity.
+ + (* case n := (S (S n)) *)
+ rewrite ?fib_simpl_spec.
+ do 2 rewrite strong_induction_hypothesis by lia.
+ enough (forall n, fib_faster (S n) + fib_faster n = fib_faster (S (S n))) as lemma by apply lemma.
+ clear.
+ destruct n.
+ * (* for lemma, case n := 0 *)
+ reflexivity.
+ * (* for lemma, case n := S n *)
+ destruct n.
+ -- (* for lemma, case n := 1 *)
+ reflexivity.
+ -- (* for lemma, case n := S (S n) *)
+ simpl.
+ apply fib_acc_aux_rewrite.
+Qed.
+
--
cgit v1.2.3-70-g09d2
From b0644202ce201774445a09f103908498f3838820 Mon Sep 17 00:00:00 2001
From: Felipe Bañados Schwerter
Date: Mon, 24 Oct 2022 11:27:43 -0600
Subject: Base smalltalk export
---
entries/fbanados/fib.st | 1 +
1 file changed, 1 insertion(+)
create mode 100644 entries/fbanados/fib.st
(limited to 'entries')
diff --git a/entries/fbanados/fib.st b/entries/fbanados/fib.st
new file mode 100644
index 0000000..8431a09
--- /dev/null
+++ b/entries/fbanados/fib.st
@@ -0,0 +1 @@
+'From Pharo10.0.0 of 15 June 2022 [Build information: Pharo-10.0.0+build.521.sha.14f541319d443f4261f84f4fa19fbb34460a5edb (64 Bit)] on 24 October 2022 at 11:26:20.436554 am'!
!Integer methodsFor: '*Fibonacci' stamp: 'FelipeBanados 10/24/2022 11:13'!
fibonacciNumber
self <= 2 ifTrue: [ ^ 1 ].
^ (self - 1) fibonacciNumber + (self - 2) fibonacciNumber.! !
\ No newline at end of file
--
cgit v1.2.3-70-g09d2
From ac7935ad693adac61f7fe0a6c9ec1344f3297c48 Mon Sep 17 00:00:00 2001
From: Felipe Bañados Schwerter
Date: Mon, 24 Oct 2022 11:33:02 -0600
Subject: Ok made it readable
---
entries/fbanados/fib.st | 9 ++++++++-
1 file changed, 8 insertions(+), 1 deletion(-)
(limited to 'entries')
diff --git a/entries/fbanados/fib.st b/entries/fbanados/fib.st
index 8431a09..099407c 100644
--- a/entries/fbanados/fib.st
+++ b/entries/fbanados/fib.st
@@ -1 +1,8 @@
-'From Pharo10.0.0 of 15 June 2022 [Build information: Pharo-10.0.0+build.521.sha.14f541319d443f4261f84f4fa19fbb34460a5edb (64 Bit)] on 24 October 2022 at 11:26:20.436554 am'!
!Integer methodsFor: '*Fibonacci' stamp: 'FelipeBanados 10/24/2022 11:13'!
fibonacciNumber
self <= 2 ifTrue: [ ^ 1 ].
^ (self - 1) fibonacciNumber + (self - 2) fibonacciNumber.! !
\ No newline at end of file
+'From Pharo10.0.0 of 15 June 2022 [Build information: Pharo-10.0.0+build.521.sha.14f541319d443f4261f84f4fa19fbb34460a5edb (64 Bit)] on 24 October 2022 at 11:26:20.436554 am'!
+
+!Integer methodsFor: '*Fibonacci' stamp: 'FelipeBanados 10/24/2022 11:13'!
+fibonacciNumber
+ self <= 2 ifTrue: [ ^ 1 ].
+ ^ (self - 1) fibonacciNumber + (self - 2) fibonacciNumber.
+
+! !
--
cgit v1.2.3-70-g09d2
From f540b8058f8ed83c9230662f9d02fad898da008e Mon Sep 17 00:00:00 2001
From: Justin Frank
Date: Mon, 24 Oct 2022 14:12:11 -0400
Subject: Added fib in befunge
---
entries/laelath/fib.bf | 3 +++
people.json | 11 +++++++++++
2 files changed, 14 insertions(+)
create mode 100644 entries/laelath/fib.bf
(limited to 'entries')
diff --git a/entries/laelath/fib.bf b/entries/laelath/fib.bf
new file mode 100644
index 0000000..ff7d67a
--- /dev/null
+++ b/entries/laelath/fib.bf
@@ -0,0 +1,3 @@
+>101p011p&:v:-1 <
+ v+g11g10_11g.@
+ >11g01p11p ^
diff --git a/people.json b/people.json
index 2543c07..26dc1db 100644
--- a/people.json
+++ b/people.json
@@ -202,5 +202,16 @@
"link": "./entries/fbanados/fib.st"
}
]
+ },
+ {
+ "github": "laelath",
+ "name": "Justin Frank",
+ "title": "PhD Student, UMD",
+ "entries": [
+ {
+ "name": "befunge",
+ "link": "./entries/laelath/fib.bf"
+ }
+ ]
}
]
--
cgit v1.2.3-70-g09d2
From 7972ad88012a56f6afd54ada46cd45206418682a Mon Sep 17 00:00:00 2001
From: braxtonhall
Date: Mon, 24 Oct 2022 12:03:21 -0700
Subject: Add Nico's new fibs
---
entries/nritschel/assets/scratch.png | Bin 0 -> 752302 bytes
entries/nritschel/scratch/README.md | 1 +
entries/nritschel/scratch/fib.sb3 | Bin 0 -> 43364 bytes
entries/nritschel/xlsx/fib.xlsx | Bin 0 -> 11704 bytes
people.json | 8 ++++++++
5 files changed, 9 insertions(+)
create mode 100644 entries/nritschel/assets/scratch.png
create mode 100644 entries/nritschel/scratch/README.md
create mode 100644 entries/nritschel/scratch/fib.sb3
create mode 100644 entries/nritschel/xlsx/fib.xlsx
(limited to 'entries')
diff --git a/entries/nritschel/assets/scratch.png b/entries/nritschel/assets/scratch.png
new file mode 100644
index 0000000..5883245
Binary files /dev/null and b/entries/nritschel/assets/scratch.png differ
diff --git a/entries/nritschel/scratch/README.md b/entries/nritschel/scratch/README.md
new file mode 100644
index 0000000..e059267
--- /dev/null
+++ b/entries/nritschel/scratch/README.md
@@ -0,0 +1 @@
+
\ No newline at end of file
diff --git a/entries/nritschel/scratch/fib.sb3 b/entries/nritschel/scratch/fib.sb3
new file mode 100644
index 0000000..a3cf2cc
Binary files /dev/null and b/entries/nritschel/scratch/fib.sb3 differ
diff --git a/entries/nritschel/xlsx/fib.xlsx b/entries/nritschel/xlsx/fib.xlsx
new file mode 100644
index 0000000..e1b662d
Binary files /dev/null and b/entries/nritschel/xlsx/fib.xlsx differ
diff --git a/people.json b/people.json
index 26dc1db..fa3f624 100644
--- a/people.json
+++ b/people.json
@@ -130,6 +130,14 @@
{
"name": "fib-java",
"link": "./entries/nritschel/fib-java/src"
+ },
+ {
+ "name": "xlsx",
+ "link": "./entries/nritschel/xlsx/fib.xlsx"
+ },
+ {
+ "name": "scratch",
+ "link": "./entries/nritschel/scratch"
}
]
},
--
cgit v1.2.3-70-g09d2
From 06ad8853e86b5c270f31f6d7b99081323f2f677a Mon Sep 17 00:00:00 2001
From: Zack Grannan
Date: Mon, 24 Oct 2022 12:02:15 -0700
Subject: Add submission for zgrannan
---
entries/zgrannan/Fib.hs | 18 ++++++++++++++++++
people.json | 11 +++++++++++
2 files changed, 29 insertions(+)
create mode 100644 entries/zgrannan/Fib.hs
(limited to 'entries')
diff --git a/entries/zgrannan/Fib.hs b/entries/zgrannan/Fib.hs
new file mode 100644
index 0000000..1918fc8
--- /dev/null
+++ b/entries/zgrannan/Fib.hs
@@ -0,0 +1,18 @@
+-- Point-less fibonacci
+fib :: Int -> Int
+fib = fix fib'
+ where
+ fib' =
+ ap (when 0 . (0 ==)) .
+ ap (when 1 . (1 ==)) .
+ ap (ap . ((+) .) . (. subtract 1)) (. subtract 2)
+
+ when t c e = if c then t else e
+
+ ap mf m = mf >>= (\f -> m >>= return . f)
+
+ fix f = f (fix f)
+
+
+main :: IO ()
+main = mapM_ (print . fib) [0 .. 10]
diff --git a/people.json b/people.json
index 26dc1db..a9d5fa0 100644
--- a/people.json
+++ b/people.json
@@ -213,5 +213,16 @@
"link": "./entries/laelath/fib.bf"
}
]
+ },
+ {
+ "github": "zgrannan",
+ "name": "Zack Grannan",
+ "title": "MS Student, UBC",
+ "entries": [
+ {
+ "name": "haskell",
+ "link": "./entries/zgrannan/Fib.hs"
+ }
+ ]
}
]
--
cgit v1.2.3-70-g09d2
From 0aa0d695f8fef33b02cbf04fbd6825bd2cbc6de1 Mon Sep 17 00:00:00 2001
From: Xu, Junfeng
Date: Mon, 24 Oct 2022 12:24:50 -0700
Subject: add haskell entry
---
entries/nxjfxu/fib.hs | 5 +++++
people.json | 11 +++++++++++
2 files changed, 16 insertions(+)
create mode 100644 entries/nxjfxu/fib.hs
(limited to 'entries')
diff --git a/entries/nxjfxu/fib.hs b/entries/nxjfxu/fib.hs
new file mode 100644
index 0000000..0f0d871
--- /dev/null
+++ b/entries/nxjfxu/fib.hs
@@ -0,0 +1,5 @@
+fib :: Int -> Int
+fib = (fibs !!)
+ where
+ fibs = 0 : 1 : [fibs !! (i - 2) + fibs !! (i - 1) | i <- [2..]]
+
diff --git a/people.json b/people.json
index 26dc1db..e63fc4d 100644
--- a/people.json
+++ b/people.json
@@ -213,5 +213,16 @@
"link": "./entries/laelath/fib.bf"
}
]
+ },
+ {
+ "github": "nxjfxu",
+ "name": "Junfeng Xu",
+ "title": "MSc Student, UBC",
+ "entries": [
+ {
+ "name": "ouroboros",
+ "link": "./entries/nxjfxu/fib.hs"
+ }
+ ]
}
]
--
cgit v1.2.3-70-g09d2
From db535e5c3035030bc1089528ad5fc12b9eef14ad Mon Sep 17 00:00:00 2001
From: braxtonhall
Date: Mon, 24 Oct 2022 12:34:39 -0700
Subject: Add Paulette
---
entries/pkoronkevich/tex/README.md | 1 +
entries/pkoronkevich/tex/fib.tex | 28 ++++++++++++++++++++++++++++
entries/pkoronkevich/tex/render.pdf | Bin 0 -> 21761 bytes
entries/pkoronkevich/tex/render.png | Bin 0 -> 297404 bytes
people.json | 11 +++++++++++
5 files changed, 40 insertions(+)
create mode 100644 entries/pkoronkevich/tex/README.md
create mode 100644 entries/pkoronkevich/tex/fib.tex
create mode 100644 entries/pkoronkevich/tex/render.pdf
create mode 100644 entries/pkoronkevich/tex/render.png
(limited to 'entries')
diff --git a/entries/pkoronkevich/tex/README.md b/entries/pkoronkevich/tex/README.md
new file mode 100644
index 0000000..225773b
--- /dev/null
+++ b/entries/pkoronkevich/tex/README.md
@@ -0,0 +1 @@
+
\ No newline at end of file
diff --git a/entries/pkoronkevich/tex/fib.tex b/entries/pkoronkevich/tex/fib.tex
new file mode 100644
index 0000000..22781d1
--- /dev/null
+++ b/entries/pkoronkevich/tex/fib.tex
@@ -0,0 +1,28 @@
+\documentclass[11pt]{article}
+\usepackage[fleqn]{amsmath}
+
+\newcommand{\one}{\lambda f . \lambda x . f \ x}
+\newcommand{\two}{\lambda f . \lambda x . f \ (f \ x)}
+\newcommand{\tru}{\lambda x . \lambda y . x}
+\newcommand{\flse}{\lambda x . \lambda y . y}
+\newcommand{\isz}{\lambda n . n \ (\lambda c . \flse) \ \tru}
+\newcommand{\ife}{\lambda p . \lambda a . \lambda b . p \ a \ b}
+\newcommand{\suc}{\lambda n . \lambda f . \lambda x . f \ (n \ f \ x)}
+\newcommand{\plus}{\lambda m . \lambda n . m \ (\suc) \ n}
+\newcommand{\pred}{\lambda n . \lambda f . \lambda x . n \ (\lambda g . \lambda h . h \ (g \ f)) \ (\lambda u . x) \ (\lambda u . u)}
+\newcommand{\sub}{\lambda m . \lambda n . n \ (\pred) \ m}
+\newcommand{\fix}{\lambda g . (\lambda x . g \ (x \ x)) \ (\lambda x . g \ (x \ x))}
+\newcommand{\appo}[2]{#1 \ #2}
+\newcommand{\appt}[3]{#1 \ #2 \ #3}
+
+\begin{document}
+\begin{gather*}
+ \fix \\ % recursive function application
+ \quad \lambda r . \lambda n . (\ife) \\ % of fib, which takes itself and n, if expression
+ \quad \ \appo{(\isz)}{n} \\ % is n zero
+ \quad \ (\one) \\ % if so, return 1
+ \quad \ (\plus) \\ % if not, add
+ \qquad \appo{r}{(\appo{(\pred)}{n})} \\ % the first recursive call, n - 1, to
+ \qquad \appo{r}{(\appt{(\sub)}{n}{\two})} % the second recursive call, n - 2
+\end{gather*}
+\end{document}
diff --git a/entries/pkoronkevich/tex/render.pdf b/entries/pkoronkevich/tex/render.pdf
new file mode 100644
index 0000000..b69f747
Binary files /dev/null and b/entries/pkoronkevich/tex/render.pdf differ
diff --git a/entries/pkoronkevich/tex/render.png b/entries/pkoronkevich/tex/render.png
new file mode 100644
index 0000000..2e172cc
Binary files /dev/null and b/entries/pkoronkevich/tex/render.png differ
diff --git a/people.json b/people.json
index b957009..ef2cbd2 100644
--- a/people.json
+++ b/people.json
@@ -232,5 +232,16 @@
"link": "./entries/zgrannan/Fib.hs"
}
]
+ },
+ {
+ "github": "pkoronkevich",
+ "name": "Paulette Koronkevich",
+ "title": "PhD Student, UBC",
+ "entries": [
+ {
+ "name": "tex",
+ "link": "./entries/pkoronkevich/tex"
+ }
+ ]
}
]
--
cgit v1.2.3-70-g09d2
From d6cab23a8b6879a58eadac239001acc40372cbb6 Mon Sep 17 00:00:00 2001
From: braxtonhall
Date: Mon, 24 Oct 2022 13:04:02 -0700
Subject: Update Paulette's fib
---
entries/pkoronkevich/tex/fib.tex | 3 ++-
entries/pkoronkevich/tex/render.pdf | Bin 21761 -> 21807 bytes
entries/pkoronkevich/tex/render.png | Bin 297404 -> 387387 bytes
3 files changed, 2 insertions(+), 1 deletion(-)
(limited to 'entries')
diff --git a/entries/pkoronkevich/tex/fib.tex b/entries/pkoronkevich/tex/fib.tex
index 22781d1..cef9138 100644
--- a/entries/pkoronkevich/tex/fib.tex
+++ b/entries/pkoronkevich/tex/fib.tex
@@ -11,6 +11,7 @@
\newcommand{\plus}{\lambda m . \lambda n . m \ (\suc) \ n}
\newcommand{\pred}{\lambda n . \lambda f . \lambda x . n \ (\lambda g . \lambda h . h \ (g \ f)) \ (\lambda u . x) \ (\lambda u . u)}
\newcommand{\sub}{\lambda m . \lambda n . n \ (\pred) \ m}
+\newcommand{\lleq}{\lambda m . \lambda n . \\ \qquad \isz \ ((\sub) \\ \qquad \ m \ n)}
\newcommand{\fix}{\lambda g . (\lambda x . g \ (x \ x)) \ (\lambda x . g \ (x \ x))}
\newcommand{\appo}[2]{#1 \ #2}
\newcommand{\appt}[3]{#1 \ #2 \ #3}
@@ -19,7 +20,7 @@
\begin{gather*}
\fix \\ % recursive function application
\quad \lambda r . \lambda n . (\ife) \\ % of fib, which takes itself and n, if expression
- \quad \ \appo{(\isz)}{n} \\ % is n zero
+ \quad \ \appt{(\lleq)}{n}{\one} \\ % if n less than or equal to one
\quad \ (\one) \\ % if so, return 1
\quad \ (\plus) \\ % if not, add
\qquad \appo{r}{(\appo{(\pred)}{n})} \\ % the first recursive call, n - 1, to
diff --git a/entries/pkoronkevich/tex/render.pdf b/entries/pkoronkevich/tex/render.pdf
index b69f747..8ee60c7 100644
Binary files a/entries/pkoronkevich/tex/render.pdf and b/entries/pkoronkevich/tex/render.pdf differ
diff --git a/entries/pkoronkevich/tex/render.png b/entries/pkoronkevich/tex/render.png
index 2e172cc..a1896a2 100644
Binary files a/entries/pkoronkevich/tex/render.png and b/entries/pkoronkevich/tex/render.png differ
--
cgit v1.2.3-70-g09d2
From 2db6cb57d86bfa3616e9f8ede8ac73b30dfe75e1 Mon Sep 17 00:00:00 2001
From: StuartLiv
Date: Mon, 24 Oct 2022 14:26:31 -0700
Subject: Added ThetaFibN
---
entries/StuartLiv/ThetaFibN.java | 13 +++++++++++++
people.json | 11 +++++++++++
2 files changed, 24 insertions(+)
create mode 100644 entries/StuartLiv/ThetaFibN.java
(limited to 'entries')
diff --git a/entries/StuartLiv/ThetaFibN.java b/entries/StuartLiv/ThetaFibN.java
new file mode 100644
index 0000000..1e4f431
--- /dev/null
+++ b/entries/StuartLiv/ThetaFibN.java
@@ -0,0 +1,13 @@
+public class ThetaFibN {
+
+ //Fibonacci(n) is asymptotically in ϴ(Fibonacci(n))
+ public int Fibonacci(int n) {
+ String reference = "0";
+ int fib = 1;
+ for(int i = 1; i <= n; i++) {
+ fib = reference.length();
+ reference = reference.replace("0", "").replace("1", "0") + "1".repeat(fib);
+ }
+ return fib;
+ }
+}
diff --git a/people.json b/people.json
index 248c644..bb44dde 100644
--- a/people.json
+++ b/people.json
@@ -166,6 +166,17 @@
}
]
},
+ {
+ "github": "StuartLiv",
+ "name": "Stuart Livingstone",
+ "title": "BSc Student, UBC",
+ "entries": [
+ {
+ "name": "ThetaFibN",
+ "link": "./entries/StuartLiv/ThetaFibN.java"
+ }
+ ]
+ },
{
"github": "Tarcisio-Teixeira",
"name": "Tarcísio Teixeira",
--
cgit v1.2.3-70-g09d2
From 8ffac10bf733f5f75bf85750562710c1cd60cf0a Mon Sep 17 00:00:00 2001
From: braxtonhall
Date: Mon, 24 Oct 2022 15:14:18 -0700
Subject: Add Ron
---
entries/rxg/fib.rkt | 132 ++++++++++++++++++++++++++++++++++++++++++++++++++++
people.json | 11 +++++
2 files changed, 143 insertions(+)
create mode 100644 entries/rxg/fib.rkt
(limited to 'entries')
diff --git a/entries/rxg/fib.rkt b/entries/rxg/fib.rkt
new file mode 100644
index 0000000..61373cd
--- /dev/null
+++ b/entries/rxg/fib.rkt
@@ -0,0 +1,132 @@
+#lang racket
+
+;; fib.rkt - A variety of iterative implementations of the Fibonacci Sequence
+;; All are based on accumulators
+
+;; Natural -> Natural
+;; produce the n'th Fibonacci number
+(define (fib-iter n)
+ (cond
+ [(= n 0) 1]
+ [(= n 1) 1]
+ [else
+ (let-values ([(n-2 n-1)
+ ;; i-2 = fib (i-2)
+ ;; i-1 = fib (i-1)
+ (for/fold ([i-2 1] [i-1 1])
+ ([i (in-range 2 n)])
+ (values i-1 (+ i-2 i-1)))])
+ (+ n-2 n-1))]))
+
+
+(define (fib-iter2 n)
+ (cond
+ [(= n 0) 1]
+ [(= n 1) 1]
+ [else
+ ;; i-2 = fib (i-2)
+ ;; i-1 = fib (i-1)
+ (let loop ([i-2 1] [i-1 1] [i 2])
+ (if (= i n)
+ (+ i-2 i-1)
+ (loop i-1 (+ i-2 i-1) (add1 i))))]))
+
+(define (fib-iter3 n)
+ (cond
+ [(= n 0) 1]
+ [(= n 1) 1]
+ [else
+ ;; i-2 = fib (i-2)
+ ;; i-1 = fib (i-1)
+ (do ([i-2 1 i-1]
+ [i-1 1 (+ i-2 i-1)]
+ [i 2 (add1 i)])
+ [(= i n)
+ (+ i-2 i-1)])]))
+
+;; New variant of for with accumulators and a final expression in terms of
+;; the accumulators
+(define-syntax (for/acc stx)
+ (syntax-case stx ()
+ [(_ ([id* init*] ...)
+ (clauses ...)
+ body
+ result)
+ (with-syntax ([original stx])
+ #'(let-values ([(id* ...)
+ (for/fold/derived original
+ ([id* init*] ...)
+ (clauses ...)
+ body)])
+ result))]))
+
+(define (fib-iter4 n)
+ (cond
+ [(= n 0) 1]
+ [(= n 1) 1]
+ [else
+ ;; i-2 = fib (i-2)
+ ;; i-1 = fib (i-1)
+ (for/acc ([i-2 1] [i-1 1])
+ ([i (in-range 2 n)])
+ (values i-1 (+ i-2 i-1))
+ (+ i-2 i-1))]))
+
+;; New variant of for with accumulators and a final expression in terms of
+;; the accumulators
+(define-syntax (for/do stx)
+ (syntax-case stx ()
+ [(_ ([id* init* step*] ...)
+ (clauses ...)
+ result)
+ (with-syntax ([original stx])
+ #'(let-values ([(id* ...)
+ (for/fold/derived original
+ ([id* init*] ...)
+ (clauses ...)
+ (values step* ...))])
+ result))]))
+
+(define (fib-iter5 n)
+ (cond
+ [(= n 0) 1]
+ [(= n 1) 1]
+ [else
+ ;; i-2 = fib (i-2)
+ ;; i-1 = fib (i-1)
+ (for/do ([i-2 1 i-1] [i-1 1 (+ i-2 i-1)])
+ ([i (in-range 2 n)])
+ (+ i-2 i-1))]))
+
+
+;; Fibonacci's problem, as described by Greg Rawlins in "Compared to What":
+;; Suppose you have a pair of rabbits and suppose every month each pair
+;; bears a new pair that from the second month on becomes productive.
+;; how many pairs of rabbits will you have in a year?
+
+;; Analysis:
+;; - At time 0 you have 1 unproductive pair: 1 pair, 0 productive pairs
+;; - Each month, each productive pair produces an unproductive pair
+;; - Each month, last months unproductive pairs transition to productive
+;; - how many pairs are there at time step 12?
+
+;; The following function solves the problem *directly* as a
+;; structural recursion over natural numbers with two
+;; accumulators (for lost context (fertile) and result-so-far (total))
+
+;; Natural -> Natural
+;; produce the solution to Fibonacci's problem after n months
+(define (fib-rabbit n0)
+ ;; Accumulator: total is Natural
+ ;; Invariant: total pairs of rabbits after (- n0 n) months
+ ;; Accumulator: fertile is Natural
+ ;; Invariant: productive pairs of rabbits after (- n0 n) months
+ (local [(define (fib-acc fertile total n)
+ (cond [(zero? n) total]
+ [else
+ (fib-acc total ;; next month, all will be productive
+ (+ ;; next months pairs include:
+ total ;; - this months pairs plus
+ fertile) ;; - offspring from productive pairs
+ (sub1 n))]))]
+ (fib-acc 0 1 n0)))
diff --git a/people.json b/people.json
index b84c8d8..1ff8fa0 100644
--- a/people.json
+++ b/people.json
@@ -163,6 +163,17 @@
}
]
},
+ {
+ "github": "rxg",
+ "name": "Ronald Garcia",
+ "title": "Associate Professor of Computer Science, UBC",
+ "entries": [
+ {
+ "name": "fib-iter*",
+ "link": "./entries/rxg/fib.rkt"
+ }
+ ]
+ },
{
"github": "shayanh",
"name": "Shayan Hosseini",
--
cgit v1.2.3-70-g09d2
From d8809640625ff7113b3e534a0ddc84d970674570 Mon Sep 17 00:00:00 2001
From: braxtonhall
Date: Mon, 24 Oct 2022 15:21:37 -0700
Subject: Add Marie
---
entries/MarieSal0/FibonacciWorkplace/.gitignore | 133 +++++++++++++++++++++
.../FibonacciWorkplace/FibonacciWorkplace.csproj | 10 ++
entries/MarieSal0/FibonacciWorkplace/Program.cs | 41 +++++++
people.json | 11 ++
4 files changed, 195 insertions(+)
create mode 100644 entries/MarieSal0/FibonacciWorkplace/.gitignore
create mode 100644 entries/MarieSal0/FibonacciWorkplace/FibonacciWorkplace.csproj
create mode 100644 entries/MarieSal0/FibonacciWorkplace/Program.cs
(limited to 'entries')
diff --git a/entries/MarieSal0/FibonacciWorkplace/.gitignore b/entries/MarieSal0/FibonacciWorkplace/.gitignore
new file mode 100644
index 0000000..9b956f9
--- /dev/null
+++ b/entries/MarieSal0/FibonacciWorkplace/.gitignore
@@ -0,0 +1,133 @@
+## Ignore Visual Studio temporary files, build results, and
+## files generated by popular Visual Studio add-ons.
+
+# User-specific files
+*.suo
+*.user
+*.sln.docstates
+
+# Build results
+
+[Dd]ebug/
+[Rr]elease/
+x64/
+[Bb]in/
+[Oo]bj/
+
+# MSTest test Results
+[Tt]est[Rr]esult*/
+[Bb]uild[Ll]og.*
+
+*_i.c
+*_p.c
+*_i.h
+*.ilk
+*.meta
+*.obj
+*.pch
+*.pdb
+*.pgc
+*.pgd
+*.rsp
+*.sbr
+*.tlb
+*.tli
+*.tlh
+*.tmp
+*.tmp_proj
+*.log
+*.vspscc
+*.vssscc
+.builds
+*.pidb
+*.log
+*.svclog
+*.scc
+
+# Visual C++ cache files
+ipch/
+*.aps
+*.ncb
+*.opensdf
+*.sdf
+*.cachefile
+
+# Visual Studio profiler
+*.psess
+*.vsp
+*.vspx
+
+# Guidance Automation Toolkit
+*.gpState
+
+# ReSharper is a .NET coding add-in
+_ReSharper*/
+*.[Rr]e[Ss]harper
+*.DotSettings.user
+
+# Click-Once directory
+publish/
+
+# Publish Web Output
+*.Publish.xml
+*.pubxml
+*.azurePubxml
+
+# NuGet Packages Directory
+## TODO: If you have NuGet Package Restore enabled, uncomment the next line
+packages/
+## TODO: If the tool you use requires repositories.config, also uncomment the next line
+!packages/repositories.config
+
+# Windows Azure Build Output
+csx/
+*.build.csdef
+
+# Windows Store app package directory
+AppPackages/
+
+# Others
+sql/
+*.Cache
+ClientBin/
+[Ss]tyle[Cc]op.*
+![Ss]tyle[Cc]op.targets
+~$*
+*~
+*.dbmdl
+*.[Pp]ublish.xml
+
+*.publishsettings
+
+# RIA/Silverlight projects
+Generated_Code/
+
+# Backup & report files from converting an old project file to a newer
+# Visual Studio version. Backup files are not needed, because we have git ;-)
+_UpgradeReport_Files/
+Backup*/
+UpgradeLog*.XML
+UpgradeLog*.htm
+
+# SQL Server files
+App_Data/*.mdf
+App_Data/*.ldf
+
+# =========================
+# Windows detritus
+# =========================
+
+# Windows image file caches
+Thumbs.db
+ehthumbs.db
+
+# Folder config file
+Desktop.ini
+
+# Recycle Bin used on file shares
+$RECYCLE.BIN/
+
+# Mac desktop service store files
+.DS_Store
+
+_NCrunch*
\ No newline at end of file
diff --git a/entries/MarieSal0/FibonacciWorkplace/FibonacciWorkplace.csproj b/entries/MarieSal0/FibonacciWorkplace/FibonacciWorkplace.csproj
new file mode 100644
index 0000000..40c60dd
--- /dev/null
+++ b/entries/MarieSal0/FibonacciWorkplace/FibonacciWorkplace.csproj
@@ -0,0 +1,10 @@
+
+
+
+ Exe
+ net6.0
+ enable
+ enable
+
+
+
diff --git a/entries/MarieSal0/FibonacciWorkplace/Program.cs b/entries/MarieSal0/FibonacciWorkplace/Program.cs
new file mode 100644
index 0000000..bac5688
--- /dev/null
+++ b/entries/MarieSal0/FibonacciWorkplace/Program.cs
@@ -0,0 +1,41 @@
+using System;
+namespace FibonacciWorkplace
+{
+ public class Program
+ {
+ static void Main(string[] args)
+ {
+ Console.Write("How long should the Fibonacci Series be?? ");
+ int lengthOfSeries = Convert.ToInt32(Console.ReadLine());
+ if (lengthOfSeries<=2)
+ {
+ LengthCheck(lengthOfSeries);
+ }
+ FibonacciSeries(0, 1, 1, lengthOfSeries);
+ Console.ReadKey();
+ }
+ public static void LengthCheck(int lengthOfSeries)
+ {
+ if (lengthOfSeries<=1)
+ {
+ Console.Write("The Fibonacci Series needs to be greater than 2");
+ lengthOfSeries = Convert.ToInt32(Console.ReadLine());
+ LengthCheck(lengthOfSeries);
+ }
+
+ }
+
+ public static void FibonacciSeries(int firstNumber, int secondNumber, int counter, int lengthOfSeries)
+ {
+ Console.Write(firstNumber + " ");
+ if (counter < lengthOfSeries)
+ {
+ int sum = firstNumber + secondNumber;
+ counter++;
+ FibonacciSeries(secondNumber, sum, counter, lengthOfSeries);
+ }
+ }
+
+
+ }
+}
\ No newline at end of file
diff --git a/people.json b/people.json
index b84c8d8..60654a5 100644
--- a/people.json
+++ b/people.json
@@ -100,6 +100,17 @@
}
]
},
+ {
+ "github": "MarieSal0",
+ "name": "Marie Salomon",
+ "title": "MSc Student, UBC",
+ "entries": [
+ {
+ "name": "c#",
+ "link": "./entries/MarieSal0/FibonacciWorkplace/Program.cs"
+ }
+ ]
+ },
{
"github": "meghasinghania22",
"name": "Megha Singhania",
--
cgit v1.2.3-70-g09d2
From dd5fef744a98521bc586b149272580456405ec8f Mon Sep 17 00:00:00 2001
From: David Ewert
Date: Mon, 24 Oct 2022 15:42:38 -0700
Subject: Added Fib
---
entries/dewert99/fib.rs | 22 ++++++++++++++++++++++
people.json | 11 +++++++++++
2 files changed, 33 insertions(+)
create mode 100644 entries/dewert99/fib.rs
(limited to 'entries')
diff --git a/entries/dewert99/fib.rs b/entries/dewert99/fib.rs
new file mode 100644
index 0000000..b1744d5
--- /dev/null
+++ b/entries/dewert99/fib.rs
@@ -0,0 +1,22 @@
+const MAX: usize = 94;
+
+const fn fibc() -> [u64; N] {
+ let mut res = [0; N];
+ res[1] = 1;
+ let mut i = 2;
+ while i < N {
+ res[i] = res[i - 1] + res[i - 2];
+ i += 1;
+ }
+ res
+}
+
+static FIB: [u64; MAX] = fibc();
+
+pub fn fib(n: usize) -> Option {
+ if n > MAX {
+ None // Fib of n wouldn't fit in 64-bits
+ } else {
+ Some(FIB[n])
+ }
+}
diff --git a/people.json b/people.json
index a8e6e56..16b2be7 100644
--- a/people.json
+++ b/people.json
@@ -288,4 +288,15 @@
}
]
}
+ {
+ "github": "dewert99",
+ "name": "David Ewert",
+ "title": "MSc Student, UBC",
+ "entries": [
+ {
+ "name": "tex",
+ "link": "./entries/dewert99/fib.rs"
+ }
+ ]
+ }
]
--
cgit v1.2.3-70-g09d2
From b707a7103789116363427bdd248007b61d527196 Mon Sep 17 00:00:00 2001
From: David Ewert
Date: Mon, 24 Oct 2022 16:01:26 -0700
Subject: >=
---
entries/dewert99/fib.rs | 2 +-
1 file changed, 1 insertion(+), 1 deletion(-)
(limited to 'entries')
diff --git a/entries/dewert99/fib.rs b/entries/dewert99/fib.rs
index b1744d5..ecf0a85 100644
--- a/entries/dewert99/fib.rs
+++ b/entries/dewert99/fib.rs
@@ -14,7 +14,7 @@ const fn fibc() -> [u64; N] {
static FIB: [u64; MAX] = fibc();
pub fn fib(n: usize) -> Option {
- if n > MAX {
+ if n >= MAX {
None // Fib of n wouldn't fit in 64-bits
} else {
Some(FIB[n])
--
cgit v1.2.3-70-g09d2
From 40fdd4d0694f2dc0dd394901dad9884d277459db Mon Sep 17 00:00:00 2001
From: David Ewert
Date: Mon, 24 Oct 2022 16:06:31 -0700
Subject: Added compiled version
---
entries/dewert99/fib_compiled | 13 +++++++++++++
1 file changed, 13 insertions(+)
create mode 100644 entries/dewert99/fib_compiled
(limited to 'entries')
diff --git a/entries/dewert99/fib_compiled b/entries/dewert99/fib_compiled
new file mode 100644
index 0000000..0a0d3a8
--- /dev/null
+++ b/entries/dewert99/fib_compiled
@@ -0,0 +1,13 @@
+example::fib:
+ cmp rdi, 94
+ jb .LBB0_3
+ xor eax, eax
+ ret
+.LBB0_3:
+ lea rax, [rip + example::FIB]
+ mov rdx, qword ptr [rax + 8*rdi]
+ mov eax, 1
+ ret
+
+example::FIB:
+ .ascii "\000\000\000\000\000\000\000\000\001\000\000\000\000\000\000\000\001\000\000\000\000\000\000\000\002\000\000\000\000\000\000\000\003\000\000\000\000\000\000\000\005\000\000\000\000\000\000\000\b\000\000\000\000\000\000\000\r\000\000\000\000\000\000\000\025\000\000\000\000\000\000\000\"\000\000\000\000\000\000\0007\000\000\000\000\000\000\000Y\000\000\000\000\000\000\000\220\000\000\000\000\000\000\000\351\000\000\000\000\000\000\000y\001\000\000\000\000\000\000b\002\000\000\000\000\000\000\333\003\000\000\000\000\000\000=\006\000\000\000\000\000\000\030\n\000\000\000\000\000\000U\020\000\000\000\000\000\000m\032\000\000\000\000\000\000\302*\000\000\000\000\000\000/E\000\000\000\000\000\000\361o\000\000\000\000\000\000 \265\000\000\000\000\000\000\021%\001\000\000\000\000\0001\332\001\000\000\000\000\000B\377\002\000\000\000\000\000s\331\004\000\000\000\000\000\265\330\007\000\000\000\000\000(\262\f\000\000\000\000\000\335\212\024\000\000\000\000\000\005=!\000\000\000\000\000\342\3075\000\000\000\000\000\347\004W\000\000\000\000\000\311\314\214\000\000\000\000\000\260\321\343\000\000\000\000\000y\236p\001\000\000\000\000)pT\002\000\000\000\000\242\016\305\003\000\000\000\000\313~\031\006\000\000\000\000m\215\336\t\000\000\000\0008\f\370\017\000\000\000\000\245\231\326\031\000\000\000\000\335\245\316)\000\000\000\000\202?\245C\000\000\000\000_\345sm\000\000\000\000\341$\031\261\000\000\000\000@\n\215\036\001\000\000\000!/\246\317\001\000\000\000a93\356\002\000\000\000\202h\331\275\004\000\000\000\343\241\f\254\007\000\000\000e\n\346i\f\000\000\000H\254\362\025\024\000\000\000\255\266\330\177 \000\000\000\365b\313\2254\000\000\000\242\031\244\025U\000\000\000\227|o\253\211\000\000\0009\226\023\301\336\000\000\000\320\022\203lh\001\000\000\t\251\226-G\002\000\000\331\273\031\232\257\003\000\000\342d\260\307\366\005\000\000\273 \312a\246\t\000\000\235\205z)\235\017\000\000X\246D\213C\031\000\000\365+\277\264\340(\000\000M\322\003@$B\000\000B\376\302\364\004k\000\000\217\320\3064)\255\000\000\321\316\211).\030\001\000`\237P^W\305\001\0001n\332\207\205\335\002\000\221\r+\346\334\242\004\000\302{\005nb\200\007\000S\2110T?#\f\000\025\0056\302\241\243\023\000h\216f\026\341\306\037\000}\223\234\330\202j3\000\345!\003\357c1S\000b\265\237\307\346\233\206\000G\327\242\266J\315\331\000\251\214B~1i`\001\360c\3454|6:\002\231\360'\263\255\237\232\003\211T\r\350)\326\324\005\"E5\233\327uo\t\253\231B\203\001LD\017\315\336w\036\331\301\263\030xx\272\241\332\r\370'EW2\300\263\317\253@\275\317\354a\216\335\243h\002'\037\"B\255O\251"
--
cgit v1.2.3-70-g09d2
From 4da08849446829da335c5c59d953a5c23345d45d Mon Sep 17 00:00:00 2001
From: Dave Pagurek
Date: Mon, 24 Oct 2022 19:31:35 -0400
Subject: Do some unholy things with CSS
---
entries/davepagurek/fib.html | 67 ++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 67 insertions(+)
create mode 100644 entries/davepagurek/fib.html
(limited to 'entries')
diff --git a/entries/davepagurek/fib.html b/entries/davepagurek/fib.html
new file mode 100644
index 0000000..9b2ea6a
--- /dev/null
+++ b/entries/davepagurek/fib.html
@@ -0,0 +1,67 @@
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
--
cgit v1.2.3-70-g09d2
From d04de9dca28dd4878be2bdbffe814ebe1586aa98 Mon Sep 17 00:00:00 2001
From: Dave Pagurek
Date: Mon, 24 Oct 2022 19:33:32 -0400
Subject: Rename fib.html to index.html
---
entries/davepagurek/fib.html | 67 ------------------------------------------
entries/davepagurek/index.html | 67 ++++++++++++++++++++++++++++++++++++++++++
2 files changed, 67 insertions(+), 67 deletions(-)
delete mode 100644 entries/davepagurek/fib.html
create mode 100644 entries/davepagurek/index.html
(limited to 'entries')
diff --git a/entries/davepagurek/fib.html b/entries/davepagurek/fib.html
deleted file mode 100644
index 9b2ea6a..0000000
--- a/entries/davepagurek/fib.html
+++ /dev/null
@@ -1,67 +0,0 @@
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
diff --git a/entries/davepagurek/index.html b/entries/davepagurek/index.html
new file mode 100644
index 0000000..9b2ea6a
--- /dev/null
+++ b/entries/davepagurek/index.html
@@ -0,0 +1,67 @@
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
--
cgit v1.2.3-70-g09d2
From 0921d8222bb883ea86d51c7200a865a5e4dbc469 Mon Sep 17 00:00:00 2001
From: James Yoo
Date: Mon, 24 Oct 2022 16:46:58 -0700
Subject: Adding HtDP version of fibonacci, pre @htdp tags
---
entries/jyoo980/vintage-htdp/fib.rkt | 17 +++++++++++++++++
1 file changed, 17 insertions(+)
create mode 100644 entries/jyoo980/vintage-htdp/fib.rkt
(limited to 'entries')
diff --git a/entries/jyoo980/vintage-htdp/fib.rkt b/entries/jyoo980/vintage-htdp/fib.rkt
new file mode 100644
index 0000000..697c17b
--- /dev/null
+++ b/entries/jyoo980/vintage-htdp/fib.rkt
@@ -0,0 +1,17 @@
+;; Natural -> Natural
+;; given n, produce the nth fibonacci number
+(check-expect (fib 0) 0)
+(check-expect (fib 1) 1)
+(check-expect (fib 2) 1)
+(check-expect (fib 7) 13)
+
+; (define (fib n) 0) ; stub
+
+;
+(define (fib n)
+ (cond
+ [(zero? n) 0]
+ [else
+ (if (= n 1)
+ 1
+ (+ (fib (sub1 n)) (fib (- n 2))))]))
--
cgit v1.2.3-70-g09d2
From b9f9263c9f1590c043e38987935fc656834192b6 Mon Sep 17 00:00:00 2001
From: Dave Pagurek
Date: Mon, 24 Oct 2022 19:50:55 -0400
Subject: More consistent naming
---
entries/davepagurek/index.html | 50 +++++++++++++++++++++---------------------
1 file changed, 25 insertions(+), 25 deletions(-)
(limited to 'entries')
diff --git a/entries/davepagurek/index.html b/entries/davepagurek/index.html
index 9b2ea6a..bfa8791 100644
--- a/entries/davepagurek/index.html
+++ b/entries/davepagurek/index.html
@@ -6,17 +6,17 @@
--next: 1;
}
-.copyPrev {
+.copyPrevToTmpVars {
--tmp-prev: var(--prev);
--tmp-next: var(--next);
}
-.sumPrevious {
+.setVarsToSumOfTmps {
--prev: var(--tmp-next);
--next: calc(var(--tmp-prev) + var(--tmp-next));
}
-.sumPrevious::before {
+.setVarsToSumOfTmps::before {
counter-set: fib var(--prev);
content: counter(fib);
}
@@ -31,37 +31,37 @@