diff options
-rw-r--r-- | src/Util/ZUtil.v | 20 |
1 files changed, 19 insertions, 1 deletions
diff --git a/src/Util/ZUtil.v b/src/Util/ZUtil.v index 06d703bb7..5005cc32f 100644 --- a/src/Util/ZUtil.v +++ b/src/Util/ZUtil.v @@ -17,7 +17,7 @@ Hint Extern 1 => lia : lia. Hint Extern 1 => lra : lra. Hint Extern 1 => nia : nia. Hint Extern 1 => omega : omega. -Hint Resolve Z.log2_nonneg Z.div_small Z.mod_small Z.pow_neg_r Z.pow_0_l Z.pow_pos_nonneg Z.lt_le_incl Z.pow_nonzero Z.div_le_upper_bound Z_div_exact_full_2 Z.div_same Z.div_lt_upper_bound Z.div_le_lower_bound : zarith. +Hint Resolve Z.log2_nonneg Z.div_small Z.mod_small Z.pow_neg_r Z.pow_0_l Z.pow_pos_nonneg Z.lt_le_incl Z.pow_nonzero Z.div_le_upper_bound Z_div_exact_full_2 Z.div_same Z.div_lt_upper_bound Z.div_le_lower_bound Zplus_minus : zarith. Hint Resolve (fun a b H => proj1 (Z.mod_pos_bound a b H)) (fun a b H => proj2 (Z.mod_pos_bound a b H)) : zarith. (** Only hints that are always safe to apply (i.e., reversible), and @@ -1051,6 +1051,24 @@ Module Z. Hint Rewrite Z.div_mul_skip Z.div_mul_skip' using lia : zsimplify. + Lemma div_mul_skip_pow base e0 e1 x y : 0 < x -> 0 < y -> 0 < base -> 0 <= e1 <= e0 -> x * base^e0 / y / base^e1 = x * base^(e0 - e1) / y. + Proof. + intros. + assert (0 < base^e1) by auto with zarith. + replace (base^e0) with (base^(e0 - e1) * base^e1) by (autorewrite with pull_Zpow zsimplify; reflexivity). + rewrite !Z.mul_assoc. + autorewrite with zsimplify; lia. + Qed. + Hint Rewrite div_mul_skip_pow using lia : zsimplify. + + Lemma div_mul_skip_pow' base e0 e1 x y : 0 < x -> 0 < y -> 0 < base -> 0 <= e1 <= e0 -> base^e0 * x / y / base^e1 = base^(e0 - e1) * x / y. + Proof. + intros. + rewrite (Z.mul_comm (base^e0) x), div_mul_skip_pow by lia. + auto using f_equal2 with lia. + Qed. + Hint Rewrite div_mul_skip_pow' using lia : zsimplify. + Lemma mod_eq_le_to_eq a b : 0 < a <= b -> a mod b = 0 -> a = b. Proof. intros H H'. |