diff options
author | letouzey <letouzey@85f007b7-540e-0410-9357-904b9bb8a0f7> | 2010-10-14 11:37:33 +0000 |
---|---|---|
committer | letouzey <letouzey@85f007b7-540e-0410-9357-904b9bb8a0f7> | 2010-10-14 11:37:33 +0000 |
commit | 888c41d2bf95bb84fee28a8737515c9ff66aa94e (patch) | |
tree | 80c67a7a2aa22cabc94335bc14dcd33bed981417 /theories/Numbers/Integer/BigZ/ZMake.v | |
parent | d7a3d9b4fbfdd0df8ab4d0475fc7afa1ed5f5bcb (diff) |
Numbers: new functions pow, even, odd + many reorganisations
- Simplification of functor names, e.g. ZFooProp instead of ZFooPropFunct
- The axiomatisations of the different fonctions are now in {N,Z}Axioms.v
apart for Z division (three separate flavours in there own files).
Content of {N,Z}AxiomsSig is extended, old version is {N,Z}AxiomsMiniSig.
- In NAxioms, the recursion field isn't that useful, since we axiomatize
other functions and not define them (apart in the toy NDefOps.v).
We leave recursion there, but in a separate NAxiomsFullSig.
- On Z, the pow function is specified to behave as Zpower : a^(-1)=0
- In BigN/BigZ, (power:t->N->t) is now pow_N, while pow is t->t->t
These pow could be more clever (we convert 2nd arg to N and use pow_N).
Default "^" is now (pow:t->t->t). BigN/BigZ ring is adapted accordingly
- In BigN, is_even is now even, its spec is changed to use Zeven_bool.
We add an odd. In BigZ, we add even and odd.
- In ZBinary (implem of ZAxioms by ZArith), we create an efficient Zpow
to implement pow. This Zpow should replace the current linear Zpower
someday.
- In NPeano (implem of NAxioms by Arith), we create pow, even, odd functions,
and we modify the div and mod functions for them to be linear, structural,
tail-recursive.
git-svn-id: svn+ssh://scm.gforge.inria.fr/svn/coq/trunk@13546 85f007b7-540e-0410-9357-904b9bb8a0f7
Diffstat (limited to 'theories/Numbers/Integer/BigZ/ZMake.v')
-rw-r--r-- | theories/Numbers/Integer/BigZ/ZMake.v | 62 |
1 files changed, 50 insertions, 12 deletions
diff --git a/theories/Numbers/Integer/BigZ/ZMake.v b/theories/Numbers/Integer/BigZ/ZMake.v index 6d14337ab..fb760bdf5 100644 --- a/theories/Numbers/Integer/BigZ/ZMake.v +++ b/theories/Numbers/Integer/BigZ/ZMake.v @@ -271,23 +271,23 @@ Module Make (N:NType) <: ZType. unfold square, to_Z; intros [x | x]; rewrite N.spec_square; ring. Qed. - Definition power_pos x p := + Definition pow_pos x p := match x with - | Pos nx => Pos (N.power_pos nx p) + | Pos nx => Pos (N.pow_pos nx p) | Neg nx => match p with | xH => x - | xO _ => Pos (N.power_pos nx p) - | xI _ => Neg (N.power_pos nx p) + | xO _ => Pos (N.pow_pos nx p) + | xI _ => Neg (N.pow_pos nx p) end end. - Theorem spec_power_pos: forall x n, to_Z (power_pos x n) = to_Z x ^ Zpos n. + Theorem spec_pow_pos: forall x n, to_Z (pow_pos x n) = to_Z x ^ Zpos n. Proof. assert (F0: forall x, (-x)^2 = x^2). intros x; rewrite Zpower_2; ring. - unfold power_pos, to_Z; intros [x | x] [p | p |]; - try rewrite N.spec_power_pos; try ring. + unfold pow_pos, to_Z; intros [x | x] [p | p |]; + try rewrite N.spec_pow_pos; try ring. assert (F: 0 <= 2 * Zpos p). assert (0 <= Zpos p); auto with zarith. rewrite Zpos_xI; repeat rewrite Zpower_exp; auto with zarith. @@ -300,18 +300,32 @@ Module Make (N:NType) <: ZType. rewrite F0; ring. Qed. - Definition power x n := + Definition pow_N x n := match n with | N0 => one - | Npos p => power_pos x p + | Npos p => pow_pos x p end. - Theorem spec_power: forall x n, to_Z (power x n) = to_Z x ^ Z_of_N n. + Theorem spec_pow_N: forall x n, to_Z (pow_N x n) = to_Z x ^ Z_of_N n. Proof. - destruct n; simpl. rewrite N.spec_1; reflexivity. - apply spec_power_pos. + destruct n; simpl. apply N.spec_1. + apply spec_pow_pos. Qed. + Definition pow x y := + match to_Z y with + | Z0 => one + | Zpos p => pow_pos x p + | Zneg p => zero + end. + + Theorem spec_pow: forall x y, to_Z (pow x y) = to_Z x ^ to_Z y. + Proof. + intros. unfold pow. destruct (to_Z y); simpl. + apply N.spec_1. + apply spec_pow_pos. + apply N.spec_0. + Qed. Definition sqrt x := match x with @@ -451,4 +465,28 @@ Module Make (N:NType) <: ZType. rewrite spec_0, spec_m1. symmetry. rewrite Zsgn_neg; auto with zarith. Qed. + Definition even z := + match z with + | Pos n => N.even n + | Neg n => N.even n + end. + + Definition odd z := + match z with + | Pos n => N.odd n + | Neg n => N.odd n + end. + + Lemma spec_even : forall z, even z = Zeven_bool (to_Z z). + Proof. + intros [n|n]; simpl; rewrite N.spec_even; trivial. + destruct (N.to_Z n) as [|p|p]; now try destruct p. + Qed. + + Lemma spec_odd : forall z, odd z = Zodd_bool (to_Z z). + Proof. + intros [n|n]; simpl; rewrite N.spec_odd; trivial. + destruct (N.to_Z n) as [|p|p]; now try destruct p. + Qed. + End Make. |