diff options
| author | letouzey | 2010-11-02 15:10:43 +0000 |
|---|---|---|
| committer | letouzey | 2010-11-02 15:10:43 +0000 |
| commit | d6ebd62341fd6bbe2b7d4e5309d8e13f786a9462 (patch) | |
| tree | 575ec66b8028a599f94d293ae32260b09e7874ef /theories/Numbers/Integer/BigZ | |
| 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/BigZ')
| -rw-r--r-- | theories/Numbers/Integer/BigZ/BigZ.v | 3 | ||||
| -rw-r--r-- | theories/Numbers/Integer/BigZ/ZMake.v | 15 |
2 files changed, 18 insertions, 0 deletions
diff --git a/theories/Numbers/Integer/BigZ/BigZ.v b/theories/Numbers/Integer/BigZ/BigZ.v index 92be49bdaf..b2bf8703ea 100644 --- a/theories/Numbers/Integer/BigZ/BigZ.v +++ b/theories/Numbers/Integer/BigZ/BigZ.v @@ -63,10 +63,13 @@ Arguments Scope BigZ.eq_bool [bigZ_scope bigZ_scope]. Arguments Scope BigZ.pow_pos [bigZ_scope positive_scope]. Arguments Scope BigZ.pow_N [bigZ_scope N_scope]. Arguments Scope BigZ.pow [bigZ_scope bigZ_scope]. +Arguments Scope BigZ.log2 [bigZ_scope]. Arguments Scope BigZ.sqrt [bigZ_scope]. Arguments Scope BigZ.div_eucl [bigZ_scope bigZ_scope]. Arguments Scope BigZ.modulo [bigZ_scope bigZ_scope]. Arguments Scope BigZ.gcd [bigZ_scope bigZ_scope]. +Arguments Scope BigZ.even [bigZ_scope]. +Arguments Scope BigZ.odd [bigZ_scope]. Local Notation "0" := BigZ.zero : bigZ_scope. Local Notation "1" := BigZ.one : bigZ_scope. diff --git a/theories/Numbers/Integer/BigZ/ZMake.v b/theories/Numbers/Integer/BigZ/ZMake.v index 099554cd0b..b341b32095 100644 --- a/theories/Numbers/Integer/BigZ/ZMake.v +++ b/theories/Numbers/Integer/BigZ/ZMake.v @@ -332,6 +332,21 @@ Module Make (N:NType) <: ZType. apply N.spec_0. Qed. + Definition log2 x := + match x with + | Pos nx => Pos (N.log2 nx) + | Neg nx => zero + end. + + Theorem spec_log2: forall x, to_Z (log2 x) = Zlog2 (to_Z x). + Proof. + intros. destruct x as [p|p]; simpl. apply N.spec_log2. + rewrite N.spec_0. + destruct (Z_le_lt_eq_dec _ _ (N.spec_pos p)) as [LT|EQ]. + rewrite Zlog2_nonpos; auto with zarith. + now rewrite <- EQ. + Qed. + Definition sqrt x := match x with | Pos nx => Pos (N.sqrt nx) |