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