chore: commit FareyApproximation.js

raklaptudirm · web-flow · commit a62b62dfa7ce · 2021-07-19T13:04:44.000+05:30
diff --git a/Maths/FareyApproximation.js b/Maths/FareyApproximation.js
@@ -0,0 +1,45 @@
+/*
+* Reference: https://en.wikipedia.org/wiki/Farey_sequence
+* Inspiration: https://www.youtube.com/watch?v=7LKy3lrkTRA
+*
+* Farey Approximation algorithm is an algorithm to
+* approximate a reduced fraction value for a certain
+* decimal number x where 0 < x < 1.
+*
+* The algorithm works by keeping two fractional upper and
+* lower bounds which start at 0 / 1 and 1 / 1. These values
+* are then used to find the "mediate" which is a value between
+* the two fractions.
+*
+* For any two fractions a / b and c / d,
+* mediate = a + c / b + d
+*
+* Then it is checked if the decimal is greater than or less
+* than the mediate and then the lower or the upper value is
+* set to be the mediate respectively.
+*
+* This is repeated for n times and then the mediate is
+* returned.
+*
+* This is explained in a greater detail in the "Inspiration"
+* link.
+*/
+
+function fareyApproximation (decimal, repeat = 20) {
+  let a = 0; let b = 1; let c = 1; let d = 1; let numerator; let denominator
+
+  for (let i = 0; i < repeat; i++) {
+    numerator = a + c
+    denominator = b + d
+
+    if (decimal > numerator / denominator) {
+      [a, b] = [numerator, denominator]
+    } else {
+      [c, d] = [numerator, denominator]
+    }
+  }
+
+  return { numerator, denominator }
+}
+
+export { fareyApproximation }
