Some more revision of {P,N,Z}Arith + bitwise ops in Ndigits

Initial plan was only to add shiftl/shiftr/land/... to N and
other number type, this is only partly done, but this work has
diverged into a big reorganisation and improvement session
of PArith,NArith,ZArith.

Bool/Bool: add lemmas orb_diag (a||a = a) and andb_diag (a&&a = a)

PArith/BinPos:
 - added a power function Ppow
 - iterator iter_pos moved from Zmisc to here + some lemmas
 - added Psize_pos, which is 1+log2, used to define Nlog2/Zlog2
 - more lemmas on Pcompare and succ/+/* and order, allow
   to simplify a lot some old proofs elsewhere.
 - new/revised results on Pminus (including some direct proof of
   stuff from Pnat)

PArith/Pnat:
 - more direct proofs (limit the need of stuff about Pmult_nat).
 - provide nicer names for some lemmas (eg. Pplus_plus instead of
   nat_of_P_plus_morphism), compatibility notations provided.
 - kill some too-specific lemmas unused in stdlib + contribs

NArith/BinNat:
 - N_of_nat, nat_of_N moved from Nnat to here.
 - a lemma relating Npred and Nminus
 - revised definitions and specification proofs of Npow and Nlog2

NArith/Nnat:
 - shorter proofs.
 - stuff about Z_of_N is moved to Znat. This way, NArith is
   entirely independent from ZArith.

NArith/Ndigits:
 - added bitwise operations Nand Nor Ndiff Nshiftl Nshiftr
 - revised proofs about Nxor, still using functional bit stream
 - use the same approach to prove properties of Nand Nor Ndiff

ZArith/BinInt: huge simplification of Zplus_assoc + cosmetic stuff

ZArith/Zcompare: nicer proofs of ugly things like Zcompare_Zplus_compat

ZArith/Znat: some nicer proofs and names, received stuff about Z_of_N

ZArith/Zmisc: almost empty new, only contain stuff about badly-named
 iter. Should be reformed more someday.

ZArith/Zlog_def: Zlog2 is now based on Psize_pos, this factorizes
 proofs and avoid slowdown due to adding 1 in Z instead of in positive

Zarith/Zpow_def: Zpower_opt is renamed more modestly Zpower_alt
 as long as I dont't know why it's slower on powers of two.

Elsewhere: propagate new names + some nicer proofs

NB: Impact on compatibility is probably non-zero, but should be
really moderate. We'll see on contribs, but a few Require here
and there might be necessary.

git-svn-id: svn+ssh://scm.gforge.inria.fr/svn/coq/trunk@13651 85f007b7-540e-0410-9357-904b9bb8a0f7

1 files changed, 32 insertions, 12 deletions

diff --git a/theories/ZArith/Zpow_def.v b/theories/ZArith/Zpow_def.v
index 96d05760b..7121393bc 100644
--- a/theories/ZArith/Zpow_def.v
+++ b/theories/ZArith/Zpow_def.v
@@ -6,7 +6,7 @@
 (*         *       GNU Lesser General Public License Version 2.1        *)
 (************************************************************************)
 
-Require Import BinInt Zmisc Ring_theory.
+Require Import BinInt BinNat Ring_theory.
 
 Local Open Scope Z_scope.
 
@@ -49,23 +49,38 @@ Proof.
  induction p; simpl; intros; rewrite ?IHp, ?Zmult_assoc; trivial.
 Qed.
 
-(** An alternative Zpower *)
+Lemma Zpower_Ppow : forall p q, (Zpos p)^(Zpos q) = Zpos (p^q).
+Proof.
+ intros. unfold Ppow, Zpower, Zpower_pos.
+ symmetry. now apply iter_pos_swap_gen.
+Qed.
+
+Lemma Zpower_Npow : forall n m,
+ (Z_of_N n)^(Z_of_N m) = Z_of_N (n^m).
+Proof.
+ intros [|n] [|m]; simpl; trivial.
+ unfold Zpower_pos. generalize 1. induction m; simpl; trivial.
+ apply Zpower_Ppow.
+Qed.
 
-(** This Zpower_opt is extensionnaly equal to Zpower in ZArith,
-    but not convertible with it, and quicker : the number of
-    multiplications is logarithmic instead of linear.
+(** An alternative Zpower *)
 
-    TODO: We should try someday to replace Zpower with this Zpower_opt.
+(** This Zpower_alt is extensionnaly equal to Zpower in ZArith,
+    but not convertible with it. The number of
+    multiplications is logarithmic instead of linear, but
+    these multiplications are bigger. Experimentally, it seems
+    that Zpower_alt is slightly quicker than Zpower on average,
+    but can be quite slower on powers of 2.
 *)
 
-Definition Zpower_opt n m :=
+Definition Zpower_alt n m :=
   match m with
     | Z0 => 1
     | Zpos p => Piter_op Zmult p n
     | Zneg p => 0
   end.
 
-Infix "^^" := Zpower_opt (at level 30, right associativity) : Z_scope.
+Infix "^^" := Zpower_alt (at level 30, right associativity) : Z_scope.
 
 Lemma iter_pos_mult_acc : forall f,
  (forall x y:Z, (f x)*y = f (x*y)) ->
@@ -92,7 +107,7 @@ Qed.
 Lemma Zpower_equiv : forall a b, a^^b = a^b.
 Proof.
  intros a [|p|p]; trivial.
- unfold Zpower_opt, Zpower, Zpower_pos.
+ unfold Zpower_alt, Zpower, Zpower_pos.
  revert a.
  induction p; simpl; intros.
  f_equal.
@@ -105,17 +120,22 @@ Proof.
  now rewrite Zmult_1_r.
 Qed.
 
-Lemma Zpower_opt_0_r : forall n, n^^0 = 1.
+Lemma Zpower_alt_0_r : forall n, n^^0 = 1.
 Proof. reflexivity. Qed.
 
-Lemma Zpower_opt_succ_r : forall a b, 0<=b -> a^^(Zsucc b) = a * a^^b.
+Lemma Zpower_alt_succ_r : forall a b, 0<=b -> a^^(Zsucc b) = a * a^^b.
 Proof.
  intros a [|b|b] Hb; [ | |now elim Hb]; simpl.
  now rewrite Zmult_1_r.
  rewrite <- Pplus_one_succ_r. apply Piter_op_succ. apply Zmult_assoc.
 Qed.
 
-Lemma Zpower_opt_neg_r : forall a b, b<0 -> a^^b = 0.
+Lemma Zpower_alt_neg_r : forall a b, b<0 -> a^^b = 0.
 Proof.
  now destruct b.
 Qed.
+
+Lemma Zpower_alt_Ppow : forall p q, (Zpos p)^^(Zpos q) = Zpos (p^q).
+Proof.
+ intros. now rewrite Zpower_equiv, Zpower_Ppow.
+Qed.