src/allmydata/util/mathutil.py

   1 # Copyright (c) 2005-2007 Bryce "Zooko" Wilcox-O'Hearn
   2 # mailto:zooko@zooko.com
   3 # http://zooko.com/repos/pyutil
   4 # Permission is hereby granted, free of charge, to any person obtaining a copy
   5 # of this work to deal in this work without restriction (including the rights
   6 # to use, modify, distribute, sublicense, and/or sell copies).
   7
   8 """
   9 A few commonly needed functions.
  10 """
  11
  12 import math
  13
  14 def div_ceil(n, d):
  15     """
  16     The smallest integer k such that k*d >= n.
  17     """
  18     return (n/d) + (n%d != 0)
  19
  20 def next_multiple(n, k):
  21     """
  22     The smallest multiple of k which is >= n.
  23     """
  24     return div_ceil(n, k) * k
  25
  26 def pad_size(n, k):
  27     """
  28     The smallest number that has to be added to n so that n is a multiple of k.
  29     """
  30     if n%k:
  31         return k - n%k
  32     else:
  33         return 0
  34
  35 def is_power_of_k(n, k):
  36     return k**int(math.log(n, k) + 0.5) == n
  37
  38 def next_power_of_k(n, k):
  39     if n == 0:
  40         x = 0
  41     else:
  42         x = int(math.log(n, k) + 0.5)
  43     r = k**x
  44     if k**x < n:
  45         return k**(x+1)
  46     else:
  47         return k**x
  48
  49 def ave(l):
  50     return sum(l) / len(l)
  51
  52 def log_ceil(n, b):
  53     """
  54     The smallest integer k such that b^k >= n.
  55
  56     log_ceil(n, 2) is the number of bits needed to store any of n values, e.g.
  57     the number of bits needed to store any of 128 possible values is 7.
  58     """
  59     p = 1
  60     k = 0
  61     while p < n:
  62         p *= b
  63         k += 1
  64     return k
  65
  66 def log_floor(n, b):
  67     """
  68     The largest integer k such that b^k <= n.
  69     """
  70     p = 1
  71     k = 0
  72     while p <= n:
  73         p *= b
  74         k += 1
  75     return k - 1
  76
  77 def round_sigfigs(f, n):
  78     fmt = "%." + str(n-1) + "e"
  79     return float(fmt % f)