chiark / gitweb /
 author Simon Tatham Fri, 14 Mar 2014 22:59:03 +0000 (22:59 +0000) committer Simon Tatham Fri, 14 Mar 2014 22:59:39 +0000 (22:59 +0000)
 bounds.py patch | blob | history

index a26bb5e..742a78c 100644 (file)
--- a/bounds.py
+++ b/bounds.py
@@ -115,20 +115,35 @@ than our presumed minimum fragment. Contradiction."""
return m/3
return None

+def most_trivial(n, m):
+    """The most trivial possible bound."""
+    return m
+
+def trivial(n, m):
+    """Trivial upper bound of m/2.
+
+If m does not divide n, then at least one m-stick must be cut into
+more than one piece, reducing the best option to at most m/2."""
+    if n % m == 0:
+        return None
+    return Fraction(m, 2)
+
bounds = [
(writinghawk, "writinghawk's piece-counting bound"),
(fivemack, "fivemack's conditional m/3 bound"),
+    (trivial, "trivial bound of m/2"),
+    (most_trivial, "trivial bound of m"),
]

def upper_bound(n, m):
assert n > m
-    best = m, "trivial bound of m"
+    best = m+1, None
for boundtype in bounds:
b = boundtype(n, m)
if b is not None:
-            if b < m:
+            if b < best:
best = b, boundtype
-            elif b == m:
+            elif b == best:
best = b, best + ", " + boundtype
return best