Initial revision

1 files changed, 84 insertions, 0 deletions

diff --git a/math_utils.py b/math_utils.py
new file mode 100644
index 0000000..2cacc2f
--- /dev/null
+++ b/math_utils.py
@@ -0,0 +1,84 @@
+#!/usr/bin/env python3
+
+import math
+from typing import List
+from heapq import heappush, heappop
+
+
+class RunningMedian:
+    def __init__(self):
+        self.lowers, self.highers = [], []
+
+    def add_number(self, number):
+        if not self.highers or number > self.highers[0]:
+            heappush(self.highers, number)
+        else:
+            heappush(self.lowers, -number)  # for lowers we need a max heap
+        self.rebalance()
+
+    def rebalance(self):
+        if len(self.lowers) - len(self.highers) > 1:
+            heappush(self.highers, -heappop(self.lowers))
+        elif len(self.highers) - len(self.lowers) > 1:
+            heappush(self.lowers, -heappop(self.highers))
+
+    def get_median(self):
+        if len(self.lowers) == len(self.highers):
+            return (-self.lowers[0] + self.highers[0])/2
+        elif len(self.lowers) > len(self.highers):
+            return -self.lowers[0]
+        else:
+            return self.highers[0]
+
+
+def gcd_floats(a: float, b: float) -> float:
+    if a < b:
+        return gcd_floats(b, a)
+
+    # base case
+    if abs(b) < 0.001:
+        return a
+    return gcd_floats(b, a - math.floor(a / b) * b)
+
+
+def gcd_float_sequence(lst: List[float]) -> float:
+    if len(lst) <= 0:
+        raise Exception("Need at least one number")
+    elif len(lst) == 1:
+        return lst[0]
+    assert len(lst) >= 2
+    gcd = gcd_floats(lst[0], lst[1])
+    for i in range(2, len(lst)):
+        gcd = gcd_floats(gcd, lst[i])
+    return gcd
+
+
+def truncate_float(n: float, decimals: int = 2):
+    """Truncate a float to a particular number of decimals."""
+    assert decimals > 0 and decimals < 10
+    multiplier = 10 ** decimals
+    return int(n * multiplier) / multiplier
+
+
+def is_prime(n: int) -> bool:
+    """Returns True if n is prime and False otherwise"""
+    if not isinstance(n, int):
+        raise TypeError("argument passed to is_prime is not of 'int' type")
+
+    # Corner cases
+    if n <= 1:
+        return False
+    if n <= 3:
+        return True
+
+    # This is checked so that we can skip middle five numbers in below
+    # loop
+    if (n % 2 == 0 or n % 3 == 0):
+        return False
+
+    i = 5
+    while i * i <= n:
+        if (n % i == 0 or n % (i + 2) == 0):
+            return False
+        i = i + 6
+    return True