Theory Wrap_Speedup_Arithmetic

theory Wrap_Speedup_Arithmetic
  imports Wrap_Speedup
begin

section ‹Absorbing the linear speedup's constants›

text ‹Form 1 of the linear speedup theorem, run on the raw input
  (@{thm [source] linear_speedup_form_1_raw_nae}), costs
  ‹n + 3⌈n/m⌉ + 8⌈T(n)/m⌉ + 9› steps at compression alphabet size ‹m›.
  Against a bound with ‹t(n) ≥ n + n/q›, write ‹t(n) = n + s›: then
  ‹8 c s / m›, ‹20›, ‹(3 + 8c) n / m› and ‹8 e / m› each take a fixed
  fraction of ‹s› once ‹m› is large relative to ‹c› and ‹q› and ‹n› is
  large relative to ‹q› and ‹e›.  The lemma below multiplies through by
  ‹16 m› so that the argument stays in typ‹nat›.

  Each ceiling is bounded by the floor plus one: the upper half of
  @{thm [source] nat_ceil_div_eq}, the entry's ceiling-division identity.›

lemma speedup_round_up_le:
  fixes x m :: nat
  assumes m: "0 < m"
  shows "(x + m - 1) div m ≤ x div m + 1"
  using nat_ceil_div_eq [OF m, of x, symmetric] by simp

lemma speedup_band_arith:
  fixes c e q m n tn :: nat
  assumes q: "0 < q"
      and m: "16 * (3 + 8 * c) * (q + 1) + 16 * c + 1 ≤ m"
      and n: "q * (81 + 128 * e) ≤ n"
      and tn: "n + n div q ≤ tn"
  shows "n + (n + m - 1) div m + 5 + 2 * ((n + m - 1) div m)
           + 8 * ((c * tn + e + m - 1) div m) + 4 ≤ tn"
proof -
  have m0: "0 < m" using m by simp
  define a where "a = n div m"
  define b where "b = (c * tn + e) div m"
  have ca: "(n + m - 1) div m ≤ a + 1" unfolding a_def by (rule speedup_round_up_le [OF m0])
  have cb: "(c * tn + e + m - 1) div m ≤ b + 1" unfolding b_def by (rule speedup_round_up_le [OF m0])
  have ma: "m * a ≤ n" unfolding a_def by (rule times_div_less_eq_dividend)
  have mb: "m * b ≤ c * tn + e" unfolding b_def by (rule times_div_less_eq_dividend)
  define s where "s = tn - n"
  have t_eq: "tn = n + s" using tn unfolding s_def by simp
  define d where "d = n div q"
  have ds: "d ≤ s" using tn unfolding s_def d_def by simp
  have dbig: "81 + 128 * e ≤ d"
  proof -
    have "(q * (81 + 128 * e)) div q ≤ n div q" by (rule div_le_mono [OF n])
    then show ?thesis unfolding d_def using q by simp
  qed
  have nd: "n ≤ q * (s + 1)"
  proof -
    have "n = q * d + n mod q" unfolding d_def by (rule mult_div_mod_eq [symmetric])
    moreover have "n mod q < q" using q by simp
    moreover have "q * d ≤ q * s" using ds by (rule mult_le_mono2)
    ultimately have "n ≤ q * s + q" by linarith
    then show ?thesis by (simp add: algebra_simps)
  qed
  have s1: "81 + 128 * e ≤ s" using dbig ds by simp
  have h1: "128 * (c * s) ≤ 8 * (m * s)"
  proof -
    have "16 * c ≤ m" using m by simp
    then have "16 * c * s ≤ m * s" by (rule mult_le_mono1)
    then show ?thesis by simp
  qed
  have h2: "320 * m ≤ 4 * (m * s)"
  proof -
    have "m * 80 ≤ m * s" using s1 by simp
    then show ?thesis by simp
  qed
  have h3: "16 * ((3 + 8 * c) * n) ≤ 2 * (m * s)"
  proof -
    have K: "16 * (3 + 8 * c) * q ≤ m"
    proof -
      have "16 * (3 + 8 * c) * q ≤ 16 * (3 + 8 * c) * (q + 1)" by simp
      then show ?thesis using m by linarith
    qed
    have "16 * ((3 + 8 * c) * n) ≤ 16 * ((3 + 8 * c) * (q * (s + 1)))"
      using nd by simp
    also have "… = 16 * (3 + 8 * c) * q * (s + 1)" by (simp only: mult.assoc)
    also have "… ≤ m * (s + 1)" using K by (rule mult_le_mono1)
    also have "… ≤ 2 * (m * s)"
    proof -
      have "m ≤ m * s" using s1 by simp
      then show ?thesis by (simp add: algebra_simps)
    qed
    finally show ?thesis .
  qed
  have h4: "128 * e ≤ m * s"
  proof -
    have "s ≤ m * s" using m0 by simp
    then show ?thesis using s1 by linarith
  qed
  define P where "P = m * n"
  define A where "A = m * a"
  define B where "B = m * b"
  define C where "C = c * tn"
  define W where "W = c * n"
  define X where "X = (3 + 8 * c) * n"
  define Y where "Y = c * s"
  define Z where "Z = m * s"
  have ma': "A ≤ n" using ma unfolding A_def .
  have mb': "B ≤ C + e" using mb unfolding B_def C_def .
  have e2: "C = W + Y" unfolding C_def W_def Y_def t_eq by (simp add: algebra_simps)
  have e3: "X = 3 * n + 8 * W" unfolding X_def W_def by (simp add: algebra_simps)
  have h1': "128 * Y ≤ 8 * Z" using h1 unfolding Y_def Z_def .
  have h2': "320 * m ≤ 4 * Z" using h2 unfolding Z_def .
  have h3': "16 * X ≤ 2 * Z" using h3 unfolding X_def Z_def .
  have h4': "128 * e ≤ Z" using h4 unfolding Z_def .
  have core: "P + 3 * A + 8 * B + 20 * m ≤ P + Z"
    using ma' mb' e2 e3 h1' h2' h3' h4' by linarith
  have e1: "m * (n + 3 * a + 8 * b + 20) = P + 3 * A + 8 * B + 20 * m"
    unfolding P_def A_def B_def by (simp add: algebra_simps)
  have e4: "m * tn = P + Z" unfolding P_def Z_def t_eq by (simp add: algebra_simps)
  have main: "m * (n + 3 * a + 8 * b + 20) ≤ m * tn"
    unfolding e1 e4 by (rule core)
  then have R: "n + 3 * a + 8 * b + 20 ≤ tn" using m0 by simp
  show ?thesis using ca cb R by linarith
qed

end