From a9fbfb4fb03281513fccb9e1af599d63c47cef12 Mon Sep 17 00:00:00 2001 From: Simon Tatham Date: Fri, 14 Mar 2014 22:59:03 +0000 Subject: [PATCH] Implement some trivial bounds as well as the interesting ones. --- bounds.py | 21 ++++++++++++++++++--- 1 file changed, 18 insertions(+), 3 deletions(-) diff --git a/bounds.py b/bounds.py index a26bb5e..742a78c 100644 --- 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[0](n, m) if b is not None: - if b < m: + if b < best[0]: best = b, boundtype[1] - elif b == m: + elif b == best[0]: best = b, best[1] + ", " + boundtype[1] return best -- 2.30.2