diff options
author | letouzey <letouzey@85f007b7-540e-0410-9357-904b9bb8a0f7> | 2010-11-18 14:40:08 +0000 |
---|---|---|
committer | letouzey <letouzey@85f007b7-540e-0410-9357-904b9bb8a0f7> | 2010-11-18 14:40:08 +0000 |
commit | 503d92f75b520e88864649306f5a70058ff73990 (patch) | |
tree | 8cf391e333965511a76fbf3fb123d165ae38fab1 /theories/ZArith | |
parent | 8d3a8edab6377823e620f7a22ccfcdcd869bb5a7 (diff) |
NZLog: we define log2_up, a base-2 logarithm that rounds up instead of down as log2
Some more results about log2. Similar results for log2_up.
git-svn-id: svn+ssh://scm.gforge.inria.fr/svn/coq/trunk@13648 85f007b7-540e-0410-9357-904b9bb8a0f7
Diffstat (limited to 'theories/ZArith')
-rw-r--r-- | theories/ZArith/Zlogarithm.v | 11 |
1 files changed, 11 insertions, 0 deletions
diff --git a/theories/ZArith/Zlogarithm.v b/theories/ZArith/Zlogarithm.v index 7bb23db62..ddb1eed9f 100644 --- a/theories/ZArith/Zlogarithm.v +++ b/theories/ZArith/Zlogarithm.v @@ -41,6 +41,17 @@ Section Log_pos. (* Log of positive integers *) Lemma Zlog2_log_inf : forall p, Zlog2 (Zpos p) = log_inf p. Proof. reflexivity. Qed. + Lemma Zlog2_up_log_sup : forall p, Z.log2_up (Zpos p) = log_sup p. + Proof. + induction p; simpl. + change (Zpos p~1) with (2*(Zpos p)+1). + rewrite Z.log2_up_succ_double, Zlog2_log_inf; try easy. + unfold Zsucc. now rewrite !(Zplus_comm _ 1), Zplus_assoc. + change (Zpos p~0) with (2*Zpos p). + now rewrite Z.log2_up_double, IHp. + reflexivity. + Qed. + (** Then we give the specifications of [log_inf] and [log_sup] and prove their validity *) |