skip list implementation

[p2pool.git] / p2pool / util / math.py

diff --git a/p2pool/util/math.py b/p2pool/util/math.py
index 3137368..0442c36 100644 (file)
--- a/p2pool/util/math.py
+++ b/p2pool/util/math.py
@@ -1,4 +1,7 @@
-from __future__ import division
+from __future__ import absolute_import, division
+
+import math
+import random
 
 def median(x, use_float=True):
     # there exist better algorithms...
@@ -37,3 +40,10 @@ def nth(i, n=0):
     for _ in xrange(n):
         i.next()
     return i.next()
+
+def geometric(p):
+    if p <= 0 or p > 1:
+        raise ValueError("p must be in the interval (0.0, 1.0]")
+    if p == 1:
+        return 1
+    return int(math.log1p(-random.random()) / math.log1p(-p)) + 1