diff options
| author |  letouzey <letouzey@85f007b7-540e-0410-9357-904b9bb8a0f7> | 2010-11-02 15:10:43 +0000 |
|---|---|---|
| committer | letouzey <letouzey@85f007b7-540e-0410-9357-904b9bb8a0f7> | 2010-11-02 15:10:43 +0000 |
| commit | d6ebd62341fd6bbe2b7d4e5309d8e13f786a9462 (patch) | |
| tree | 575ec66b8028a599f94d293ae32260b09e7874ef /theories/Numbers/Integer/SpecViaZ/ZSigZAxioms.v | |
| parent | 1dccdb6b2c792969c5e09faebc2f761e46192ec4 (diff) | |
Numbers : log2. Abstraction, properties and implementations.
Btw, we finally declare the original Zpower as the power on Z.
We should switch to a more efficient one someday, but in the
meantime BigN is proved with respect to the old one.
TODO: reform Zlogarithm with respect to Zlog_def
git-svn-id: svn+ssh://scm.gforge.inria.fr/svn/coq/trunk@13606 85f007b7-540e-0410-9357-904b9bb8a0f7
Diffstat (limited to 'theories/Numbers/Integer/SpecViaZ/ZSigZAxioms.v')
| -rw-r--r-- | theories/Numbers/Integer/SpecViaZ/ZSigZAxioms.v | 17 |
1 files changed, 16 insertions, 1 deletions
diff --git a/theories/Numbers/Integer/SpecViaZ/ZSigZAxioms.v b/theories/Numbers/Integer/SpecViaZ/ZSigZAxioms.v index c2965016a..96f243fa6 100644 --- a/theories/Numbers/Integer/SpecViaZ/ZSigZAxioms.v +++ b/theories/Numbers/Integer/SpecViaZ/ZSigZAxioms.v @@ -20,7 +20,7 @@ Hint Rewrite spec_0 spec_1 spec_2 spec_add spec_sub spec_pred spec_succ spec_mul spec_opp spec_of_Z spec_div spec_modulo spec_sqrt spec_compare spec_eq_bool spec_max spec_min spec_abs spec_sgn - spec_pow spec_even spec_odd + spec_pow spec_log2 spec_even spec_odd : zsimpl. Ltac zsimpl := autorewrite with zsimpl. @@ -293,6 +293,21 @@ Proof. intros n. zify. apply Zsqrt_neg. Qed. +(** Log2 *) + +Program Instance log2_wd : Proper (eq==>eq) log2. + +Lemma log2_spec : forall n, 0<n -> + 2^(log2 n) <= n /\ n < 2^(succ (log2 n)). +Proof. + intros n. zify. apply Zlog2_spec. +Qed. + +Lemma log2_nonpos : forall n, n<=0 -> log2 n == 0. +Proof. + intros n. zify. apply Zlog2_nonpos. +Qed. + (** Even / Odd *) Definition Even n := exists m, n == 2*m. |