math_utils.py

   1 #!/usr/bin/env python3
   2
   3 """Mathematical helpers."""
   4
   5 import functools
   6 import math
   7 from heapq import heappop, heappush
   8 from typing import List
   9
  10
  11 class RunningMedian(object):
  12     """A running median computer.
  13
  14     >>> median = RunningMedian()
  15     >>> median.add_number(1)
  16     >>> median.add_number(10)
  17     >>> median.add_number(3)
  18     >>> median.get_median()
  19     3
  20     >>> median.add_number(7)
  21     >>> median.add_number(5)
  22     >>> median.get_median()
  23     5
  24     """
  25
  26     def __init__(self):
  27         self.lowers, self.highers = [], []
  28
  29     def add_number(self, number):
  30         if not self.highers or number > self.highers[0]:
  31             heappush(self.highers, number)
  32         else:
  33             heappush(self.lowers, -number)  # for lowers we need a max heap
  34         self.rebalance()
  35
  36     def rebalance(self):
  37         if len(self.lowers) - len(self.highers) > 1:
  38             heappush(self.highers, -heappop(self.lowers))
  39         elif len(self.highers) - len(self.lowers) > 1:
  40             heappush(self.lowers, -heappop(self.highers))
  41
  42     def get_median(self):
  43         if len(self.lowers) == len(self.highers):
  44             return (-self.lowers[0] + self.highers[0]) / 2
  45         elif len(self.lowers) > len(self.highers):
  46             return -self.lowers[0]
  47         else:
  48             return self.highers[0]
  49
  50
  51 def gcd_floats(a: float, b: float) -> float:
  52     if a < b:
  53         return gcd_floats(b, a)
  54
  55     # base case
  56     if abs(b) < 0.001:
  57         return a
  58     return gcd_floats(b, a - math.floor(a / b) * b)
  59
  60
  61 def gcd_float_sequence(lst: List[float]) -> float:
  62     if len(lst) <= 0:
  63         raise ValueError("Need at least one number")
  64     elif len(lst) == 1:
  65         return lst[0]
  66     assert len(lst) >= 2
  67     gcd = gcd_floats(lst[0], lst[1])
  68     for i in range(2, len(lst)):
  69         gcd = gcd_floats(gcd, lst[i])
  70     return gcd
  71
  72
  73 def truncate_float(n: float, decimals: int = 2):
  74     """
  75     Truncate a float to a particular number of decimals.
  76
  77     >>> truncate_float(3.1415927, 3)
  78     3.141
  79
  80     """
  81     assert 0 < decimals < 10
  82     multiplier = 10**decimals
  83     return int(n * multiplier) / multiplier
  84
  85
  86 def percentage_to_multiplier(percent: float) -> float:
  87     """Given a percentage (e.g. 155%), return a factor needed to scale a
  88     number by that percentage.
  89
  90     >>> percentage_to_multiplier(155)
  91     2.55
  92     >>> percentage_to_multiplier(45)
  93     1.45
  94     >>> percentage_to_multiplier(-25)
  95     0.75
  96
  97     """
  98     multiplier = percent / 100
  99     multiplier += 1.0
 100     return multiplier
 101
 102
 103 def multiplier_to_percent(multiplier: float) -> float:
 104     """Convert a multiplicative factor into a percent change.
 105
 106     >>> multiplier_to_percent(0.75)
 107     -25.0
 108     >>> multiplier_to_percent(1.0)
 109     0.0
 110     >>> multiplier_to_percent(1.99)
 111     99.0
 112
 113     """
 114     percent = multiplier
 115     if percent > 0.0:
 116         percent -= 1.0
 117     else:
 118         percent = 1.0 - percent
 119     percent *= 100.0
 120     return percent
 121
 122
 123 @functools.lru_cache(maxsize=1024, typed=True)
 124 def is_prime(n: int) -> bool:
 125     """
 126     Returns True if n is prime and False otherwise.  Obviously(?) very slow for
 127     very large input numbers.
 128
 129     >>> is_prime(13)
 130     True
 131     >>> is_prime(22)
 132     False
 133     >>> is_prime(51602981)
 134     True
 135
 136     """
 137     if not isinstance(n, int):
 138         raise TypeError("argument passed to is_prime is not of 'int' type")
 139
 140     # Corner cases
 141     if n <= 1:
 142         return False
 143     if n <= 3:
 144         return True
 145
 146     # This is checked so that we can skip middle five numbers in below
 147     # loop
 148     if n % 2 == 0 or n % 3 == 0:
 149         return False
 150
 151     i = 5
 152     while i * i <= n:
 153         if n % i == 0 or n % (i + 2) == 0:
 154             return False
 155         i = i + 6
 156     return True
 157
 158
 159 if __name__ == '__main__':
 160     import doctest
 161
 162     doctest.testmod()