| 1 |
(* |
| 2 |
Copyright © 2006-2008 Russell O’Connor |
| 3 |
|
| 4 |
Permission is hereby granted, free of charge, to any person obtaining a copy of |
| 5 |
this proof and associated documentation files (the "Proof"), to deal in |
| 6 |
the Proof without restriction, including without limitation the rights to |
| 7 |
use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of |
| 8 |
the Proof, and to permit persons to whom the Proof is furnished to do so, |
| 9 |
subject to the following conditions: |
| 10 |
|
| 11 |
The above copyright notice and this permission notice shall be included in all |
| 12 |
copies or substantial portions of the Proof. |
| 13 |
|
| 14 |
THE PROOF IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR |
| 15 |
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS |
| 16 |
FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR |
| 17 |
COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER |
| 18 |
IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN |
| 19 |
CONNECTION WITH THE PROOF OR THE USE OR OTHER DEALINGS IN THE PROOF. |
| 20 |
*) |
| 21 |
|
| 22 |
Require Import CoRN.algebra.RSetoid. |
| 23 |
Require Import CoRN.metric2.Metric. |
| 24 |
Require Import CoRN.metric2.UniformContinuity. |
| 25 |
From Coq Require Import ZArith. |
| 26 |
From Coq Require Import Basics. |
| 27 |
From Coq Require Import Qpower. |
| 28 |
Require Import CoRN.stdlib_omissions.Z. |
| 29 |
|
| 30 |
Lemma Psize_Zlog2 (p: positive) : |
| 31 |
Zpos (Pos.size p) = Z.succ (Z.log2 (Zpos p)). |
| 32 |
Proof. |
| 33 |
destruct p; simpl; rewrite ?Pos.add_1_r; reflexivity. |
| 34 |
Qed. |
| 35 |
|
| 36 |
Local Open Scope Q_scope. |
| 37 |
|
| 38 |
(** These functions effiecently find bounds on rational numbers of the |
| 39 |
form 3^z or 4^z. *) |
| 40 |
|
| 41 |
Lemma power3bound : forall (q:Q), (q <= (3^(Z_of_nat (let (n,_):= q in match n with Zpos p => Psize p | _ => O end)))%Z #1). |
| 42 |
Proof. |
| 43 |
intros [[|n|n] d]; try discriminate. |
| 44 |
unfold Qle. |
| 45 |
simpl. |
| 46 |
Open Scope Z_scope. |
| 47 |
rewrite Zpos_mult_morphism. |
| 48 |
apply Zmult_le_compat. |
| 49 |
2: apply Pos.le_1_l. 2: discriminate. 2: discriminate. |
| 50 |
clear - n. |
| 51 |
apply Z.le_trans with (two_p (Z.succ (Z.log2 (Zpos n)))-1)%Z. |
| 52 |
- rewrite <- Zle_plus_swap. |
| 53 |
apply Zlt_succ_le. |
| 54 |
change (Zpos n+1) with (Z.succ (Zpos n)). |
| 55 |
apply Zsucc_lt_compat. |
| 56 |
destruct (Z.log2_spec (Zpos n)); auto with zarith. |
| 57 |
rewrite two_p_correct. |
| 58 |
assumption. |
| 59 |
- replace (Z.succ (Z.log2 (Zpos n))) with (Z_of_nat (Psize n)). |
| 60 |
+ apply Z.le_trans with (two_p (Z_of_nat (Psize n))). |
| 61 |
auto with *. |
| 62 |
induction (Psize n); auto with *. |
| 63 |
rewrite inj_S. |
| 64 |
simpl. |
| 65 |
unfold Z.succ. |
| 66 |
rewrite two_p_is_exp; auto with *. |
| 67 |
change (two_p 1) with 2. |
| 68 |
rewrite Zpower_exp. |
| 69 |
2: apply Z.le_ge, Zle_0_nat. 2: discriminate. |
| 70 |
apply Zmult_le_compat. exact IHn0. |
| 71 |
discriminate. |
| 72 |
induction (Z_of_nat n0). |
| 73 |
discriminate. discriminate. |
| 74 |
discriminate. discriminate. |
| 75 |
+ rewrite <- Psize_Zlog2. |
| 76 |
induction n as [ p ih | p ih | ]. |
| 77 |
simpl; rewrite Pos2Z.inj_succ, <- ih; apply Z.P_of_succ_nat_Zplus. |
| 78 |
simpl; rewrite Pos2Z.inj_succ, <- ih; apply Z.P_of_succ_nat_Zplus. |
| 79 |
reflexivity. |
| 80 |
Close Scope Z_scope. |
| 81 |
Qed. |
| 82 |
|
| 83 |
Lemma power4bound : forall (q:Q), (q <= inject_Z (4^(Z_of_nat (let (n,_):= q in match n with Zpos p => Psize p | _ => O end)))%Z). |
| 84 |
Proof. |
| 85 |
intros q. |
| 86 |
eapply Qle_trans. |
| 87 |
apply power3bound. |
| 88 |
generalize (let (n, _) := q in match n with | 0 => 0%nat | Zpos p => Psize p | Zneg _ => 0%nat end)%Z. |
| 89 |
intros n. |
| 90 |
unfold Qle. |
| 91 |
simpl. |
| 92 |
ring_simplify. |
| 93 |
induction n. |
| 94 |
apply Z.le_refl. |
| 95 |
rewrite inj_S. |
| 96 |
unfold Z.succ. |
| 97 |
do 2 rewrite Zpower_exp by auto with zarith. |
| 98 |
ring_simplify. |
| 99 |
apply Zmult_le_compat. 1, 3: discriminate. |
| 100 |
assumption. |
| 101 |
clear -n. |
| 102 |
induction n. |
| 103 |
discriminate. |
| 104 |
rewrite inj_S. |
| 105 |
unfold Z.succ. |
| 106 |
rewrite Zpower_exp; auto with *. |
| 107 |
Qed. |
| 108 |
|
| 109 |
Lemma power4bound' : forall (q:Q), |
| 110 |
(0 < q) -> ((/inject_Z((4^(Z_of_nat (let (_,d):= q in Psize d)))%Z)) <= q). |
| 111 |
Proof. |
| 112 |
intros [[|n|n] d] H. |
| 113 |
elim (Qlt_not_eq _ _ H); constructor. |
| 114 |
2: elim (Qlt_not_le _ _ H); discriminate. |
| 115 |
assert (X:=power4bound (Zpos d#n)). |
| 116 |
simpl in X. |
| 117 |
rewrite -> Zpower_Qpower by auto with zarith. |
| 118 |
apply Qle_shift_inv_r. |
| 119 |
clear - d. |
| 120 |
induction (Psize d). |
| 121 |
constructor. |
| 122 |
rewrite inj_S. |
| 123 |
unfold Z.succ. |
| 124 |
rewrite -> Qpower_plus;[|discriminate]. |
| 125 |
rewrite <- (Qmult_0_r ((4%Z#1) ^ Z.of_nat n)). |
| 126 |
apply Qmult_lt_l. exact IHn. constructor. |
| 127 |
rewrite <- Zpower_Qpower by auto with zarith. |
| 128 |
destruct (inject_Z (Zpos 4%positive ^ Z.of_nat (Psize d))%Z). |
| 129 |
change ((1 * Zpos (d * Qden)%positive <= Zpos n * Qnum * 1)%Z). |
| 130 |
ring_simplify. |
| 131 |
unfold Qle in *. |
| 132 |
simpl in X. |
| 133 |
rewrite Zmult_comm. |
| 134 |
assumption. |
| 135 |
Qed. |