| 1 |
Require Import CoRN.algebra.RSetoid. |
| 2 |
Require Import CoRN.metric2.Metric. |
| 3 |
Require Import CoRN.metric2.UniformContinuity. |
| 4 |
From Coq Require Import Ring. |
| 5 |
Require Import CoRN.stdlib_omissions.Z |
| 6 |
CoRN.model.totalorder.QposMinMax |
| 7 |
CoRN.metric2.Complete CoRN.model.metric2.Qmetric. |
| 8 |
From Coq Require Import ZArith. |
| 9 |
Require Import CoRN.util.Qdlog |
| 10 |
CoRN.reals.fast.CRroot |
| 11 |
CoRN.reals.faster.ARabs |
| 12 |
MathClasses.interfaces.abstract_algebra MathClasses.theory.shiftl MathClasses.theory.nat_pow MathClasses.theory.int_pow. |
| 13 |
Require Export |
| 14 |
CoRN.reals.faster.ARArith. |
| 15 |
|
| 16 |
Section ARsqrt. |
| 17 |
Context `{AppRationals AQ}. |
| 18 |
|
| 19 |
Add Ring AQ : (rings.stdlib_ring_theory AQ). |
| 20 |
Add Ring Q : (rings.stdlib_ring_theory Q). |
| 21 |
Add Ring Z : (rings.stdlib_ring_theory Z). |
| 22 |
Add Ring AR : (rings.stdlib_ring_theory AR). |
| 23 |
|
| 24 |
Section sqrt_mid. |
| 25 |
Context `(Pa : 1 ≤ a ≤ 4). |
| 26 |
|
| 27 |
Fixpoint AQsqrt_loop (n : nat) : AQ * AQ := |
| 28 |
match n with |
| 29 |
| O => (a, 0) |
| 30 |
| S n => |
| 31 |
let (r, s) := AQsqrt_loop n in |
| 32 |
if decide_rel (≤) (s + 1) r |
| 33 |
then ((r - (s + 1)) ≪ (2%mc:Z), (s + 2) ≪ (1%mc:Z)) |
| 34 |
else (r ≪ (2%mc:Z), s ≪ (1%mc:Z)) |
| 35 |
end. |
| 36 |
|
| 37 |
Instance: Proper (=) AQsqrt_loop. |
| 38 |
Proof. intros x y E. change (x ≡ y) in E. now rewrite E. Qed. |
| 39 |
|
| 40 |
Lemma AQsqrt_loop_invariant1 (n : nat) : |
| 41 |
snd (AQsqrt_loop n) ^ (2%mc:N) + 4 * fst (AQsqrt_loop n) = 4 * 4 ^ n * a. |
| 42 |
Proof. |
| 43 |
rewrite nat_pow_2. |
| 44 |
induction n; unfold pow; simpl. |
| 45 |
ring. |
| 46 |
revert IHn; case (AQsqrt_loop n); intros r s IHn. |
| 47 |
case (decide_rel (≤) (s + 1) r); intros; simpl in *; |
| 48 |
rewrite shiftl_1, shiftl_2, <-(associativity 4), <-IHn; ring. |
| 49 |
Qed. |
| 50 |
|
| 51 |
Lemma AQsqrt_loop_invariant2 (n : nat) : |
| 52 |
fst (AQsqrt_loop n) ≤ 2 * snd (AQsqrt_loop n) + 4. |
| 53 |
Proof. |
| 54 |
induction n; simpl. |
| 55 |
now setoid_replace (2 * 0 + 4) with 4 by ring. |
| 56 |
revert IHn; case (AQsqrt_loop n); intros r s IHn. |
| 57 |
case (decide_rel (≤) (s + 1) r); intros; simpl in *. |
| 58 |
rewrite shiftl_1, shiftl_2. |
| 59 |
setoid_replace (2 * (2 * (s + 2)) + 4) with (4 * ((2 * s + 4) - (s + 1))) by ring. |
| 60 |
apply (order_preserving (4 *.)). |
| 61 |
now apply (order_preserving (+ _)). |
| 62 |
rewrite shiftl_1, shiftl_2. |
| 63 |
setoid_replace (2 * (2 * s) + 4) with (4 * (s + 1)) by ring. |
| 64 |
apply (order_preserving (4 *.)). |
| 65 |
now apply orders.le_flip. |
| 66 |
Qed. |
| 67 |
|
| 68 |
Lemma AQsqrt_loop_snd_lower_bound (n z : nat) : |
| 69 |
snd (AQsqrt_loop n) * 2 ^ z ≤ snd (AQsqrt_loop (z + n)). |
| 70 |
Proof. |
| 71 |
induction z; unfold pow; simpl. |
| 72 |
apply orders.eq_le. ring. |
| 73 |
revert IHz. case (AQsqrt_loop (z + n)); intros r s IHz. |
| 74 |
case (decide_rel (≤) _); intros; simpl in *. |
| 75 |
rewrite shiftl_1. |
| 76 |
setoid_replace (snd (AQsqrt_loop n) * (2 * 2 ^ z)) with (2 * (snd (AQsqrt_loop n) * 2 ^ z)) by ring. |
| 77 |
apply (order_preserving (2 *.)). |
| 78 |
apply semirings.plus_le_compat_r; [solve_propholds | assumption]. |
| 79 |
rewrite shiftl_1. |
| 80 |
setoid_replace (snd (AQsqrt_loop n) * (2 * 2 ^ z)) with (2 * (snd (AQsqrt_loop n) * 2 ^ z)) by ring. |
| 81 |
now apply (order_preserving (2 *.)). |
| 82 |
Qed. |
| 83 |
|
| 84 |
Lemma AQsqrt_loop_snd_upper_bound (n z : nat) : |
| 85 |
snd (AQsqrt_loop (z + n)) ≤ (snd (AQsqrt_loop n) + 4) * 2 ^ z - 4. |
| 86 |
Proof. |
| 87 |
induction z; unfold pow; simpl. |
| 88 |
apply orders.eq_le. ring. |
| 89 |
revert IHz. case (AQsqrt_loop (z + n)); intros r s IHz. |
| 90 |
case (decide_rel (≤)); simpl; intros E. |
| 91 |
rewrite shiftl_1. |
| 92 |
setoid_replace ((snd (AQsqrt_loop n) + 4) * (2 * 2 ^ z) - 4) with (2 * ((snd (AQsqrt_loop n) + 4) * 2 ^ z - 4 + 2)) by ring. |
| 93 |
apply (order_preserving (2 *.)). |
| 94 |
now apply (order_preserving (+2)). |
| 95 |
rewrite shiftl_1. |
| 96 |
setoid_replace ((snd (AQsqrt_loop n) + 4) * (2 * 2 ^ z) - 4) with (2 * ((snd (AQsqrt_loop n) + 4) * 2 ^ z - 4 + 2)) by ring. |
| 97 |
apply (order_preserving (2 *.)). |
| 98 |
apply semirings.plus_le_compat_r; [solve_propholds | assumption]. |
| 99 |
Qed. |
| 100 |
|
| 101 |
Lemma AQsqrt_loop_snd_nonneg (n : nat) : 0 ≤ snd (AQsqrt_loop n). |
| 102 |
Proof. |
| 103 |
rewrite <-(rings.plus_0_r n) at 1. |
| 104 |
etransitivity. |
| 105 |
2: apply AQsqrt_loop_snd_lower_bound. |
| 106 |
simpl. apply orders.eq_le. ring. |
| 107 |
Qed. |
| 108 |
|
| 109 |
Lemma AQsqrt_loop_fst_nonneg (n : nat) : 0 ≤ fst (AQsqrt_loop n). |
| 110 |
Proof. |
| 111 |
induction n; simpl. |
| 112 |
transitivity 1; [solve_propholds | easy]. |
| 113 |
revert IHn; case (AQsqrt_loop n); intros r s IHn. |
| 114 |
case (decide_rel (≤) (s + 1) r); intros; simpl in *. |
| 115 |
rewrite shiftl_2. |
| 116 |
apply nonneg_mult_compat; [solve_propholds |]. |
| 117 |
now apply rings.flip_nonneg_minus. |
| 118 |
rewrite shiftl_2. |
| 119 |
now apply (nonneg_mult_compat _ _ _). |
| 120 |
Qed. |
| 121 |
|
| 122 |
Lemma AQsqrt_loop_fst_upper_bound (n : nat) : |
| 123 |
fst (AQsqrt_loop n) ≤ 2 ^ (3 + n). |
| 124 |
Proof with auto. |
| 125 |
transitivity (2 * snd (AQsqrt_loop n) + 4). |
| 126 |
apply AQsqrt_loop_invariant2. |
| 127 |
change (2 ^ (3 + n)) with (2 * (2 * (2 * 2 ^ n))). |
| 128 |
setoid_replace (2 * snd (AQsqrt_loop n) + 4) with (2 * (snd (AQsqrt_loop n) + 2)) by ring. |
| 129 |
apply (order_preserving (2 *.)). |
| 130 |
setoid_replace (2 * (2 * 2 ^ n)) with ((4 * 2 ^ n - 2) + 2) by ring. |
| 131 |
apply (order_preserving (+ 2)). |
| 132 |
transitivity (4 * 2 ^ n - 4). |
| 133 |
rewrite <-(rings.plus_0_r n) at 1. |
| 134 |
rewrite <-(rings.plus_0_l 4) at 1. |
| 135 |
now apply AQsqrt_loop_snd_upper_bound. |
| 136 |
apply semirings.plus_le_compat. |
| 137 |
now rewrite commutativity. |
| 138 |
now apply rings.flip_le_negate, semirings.le_2_4. |
| 139 |
Qed. |
| 140 |
|
| 141 |
Definition AQsqrt_mid_bounded_raw (n : N) := snd (AQsqrt_loop ('n)) ≪ -((1 + 'n)%mc : Z). |
| 142 |
|
| 143 |
Instance AQsqrt_mid_bounded_raw_proper: Proper ((=) ==> (=)) AQsqrt_mid_bounded_raw. |
| 144 |
Proof. intros x y E. change (x ≡ y) in E. now subst. Qed. |
| 145 |
|
| 146 |
Lemma AQsqrt_mid_bounded_raw_lower_bound (n : N) : |
| 147 |
0 ≤ AQsqrt_mid_bounded_raw n. |
| 148 |
Proof. unfold AQsqrt_mid_bounded_raw. apply shiftl_nonneg, AQsqrt_loop_snd_nonneg. Qed. |
| 149 |
|
| 150 |
Lemma AQsqrt_mid_bounded_raw_upper_bound (n : N) : |
| 151 |
AQsqrt_mid_bounded_raw n ≤ 4. |
| 152 |
Proof. |
| 153 |
unfold AQsqrt_mid_bounded_raw. |
| 154 |
apply (order_reflecting (≪ 1 + 'n)). |
| 155 |
rewrite shiftl_reverse by ring. |
| 156 |
etransitivity. |
| 157 |
rewrite <-(rings.plus_0_r ('n)). |
| 158 |
now apply AQsqrt_loop_snd_upper_bound. |
| 159 |
simpl. |
| 160 |
apply rings.nonneg_minus_compat; [solve_propholds|]. |
| 161 |
rewrite rings.plus_0_l, shiftl_S. |
| 162 |
apply semirings.ge_1_mult_le_compat_l. |
| 163 |
now apply semirings.le_1_2. |
| 164 |
solve_propholds. |
| 165 |
apply orders.eq_le. |
| 166 |
now rewrite shiftl_nat_pow_alt, preserves_nat_pow_exp. |
| 167 |
Qed. |
| 168 |
|
| 169 |
Lemma AQsqrt_mid_bounded_regular_aux1 (n m : N) : |
| 170 |
m ≤ n → AQsqrt_mid_bounded_raw n - AQsqrt_mid_bounded_raw m ≤ 1 ≪ (1 - 'm : Z). |
| 171 |
Proof. |
| 172 |
intros E. |
| 173 |
apply naturals.nat_le_plus in E. |
| 174 |
destruct E as [z E]. rewrite commutativity in E. |
| 175 |
change (n ≡ z + m) in E. subst. |
| 176 |
unfold AQsqrt_mid_bounded_raw. |
| 177 |
rewrite rings.preserves_plus. |
| 178 |
etransitivity. |
| 179 |
apply semirings.plus_le_compat; [| reflexivity]. |
| 180 |
apply (order_preserving (≪ _)). |
| 181 |
etransitivity. |
| 182 |
now apply AQsqrt_loop_snd_upper_bound. |
| 183 |
apply rings.nonneg_minus_compat; [solve_propholds | reflexivity]. |
| 184 |
apply orders.eq_le. |
| 185 |
rewrite <-(shiftl_nat_pow_alt (f:=cast nat Z)). |
| 186 |
rewrite (naturals.to_semiring_twice _ _ (cast N Z)). |
| 187 |
rewrite <-shiftl_exp_plus, rings.preserves_plus. |
| 188 |
mc_setoid_replace (('z - (1 + ('z + 'm)))%mc : Z) with ((-(1 + 'm))%mc : Z) by ring. |
| 189 |
rewrite shiftl_base_plus. ring_simplify. |
| 190 |
mc_setoid_replace ((1 - ' m)%mc : Z) with ((2 - (1 + 'm))%mc : Z) by ring. |
| 191 |
now rewrite shiftl_exp_plus, shiftl_2, rings.mult_1_r. |
| 192 |
Qed. |
| 193 |
|
| 194 |
Lemma AQsqrt_mid_bounded_regular_aux2 (n m : N) : |
| 195 |
n ≤ m → AQsqrt_mid_bounded_raw n ≤ AQsqrt_mid_bounded_raw m. |
| 196 |
Proof. |
| 197 |
intros E. |
| 198 |
apply naturals.nat_le_plus in E. |
| 199 |
destruct E as [z E]. rewrite commutativity in E. |
| 200 |
change (m ≡ z + n) in E. subst. |
| 201 |
unfold AQsqrt_mid_bounded_raw. |
| 202 |
rewrite 2!rings.preserves_plus. |
| 203 |
mc_setoid_replace ((-(1 + 'n))%mc : Z) with (('z - (1 + ('z + 'n)))%mc : Z) by ring. |
| 204 |
rewrite shiftl_exp_plus. |
| 205 |
apply (order_preserving (≪ _)). |
| 206 |
rewrite shiftl_nat_pow_alt, <-(preserves_nat_pow_exp (f:=cast N nat)). |
| 207 |
now apply AQsqrt_loop_snd_lower_bound. |
| 208 |
Qed. |
| 209 |
|
| 210 |
Lemma AQsqrt_mid_bounded_spec (n : N) : |
| 211 |
(AQsqrt_mid_bounded_raw n ^ (2%mc:N)) = a - fst (AQsqrt_loop ('n)) ≪ -(2 * 'n). |
| 212 |
Proof. |
| 213 |
unfold AQsqrt_mid_bounded_raw. |
| 214 |
rewrite shiftl_base_nat_pow, rings.preserves_2. |
| 215 |
apply (injective (≪ (2 + 2 * 'n))). |
| 216 |
rewrite shiftl_reverse by ring. |
| 217 |
rewrite shiftl_base_plus, shiftl_negate, <-shiftl_exp_plus. |
| 218 |
mc_setoid_replace ((-(2 * 'n) + (2 + 2 * 'n))%mc : Z) with (2%mc : Z) by ring. |
| 219 |
rewrite shiftl_exp_plus, ?shiftl_2, <-shiftl_mult_l. |
| 220 |
rewrite <-(rings.preserves_2 (f:=cast N Z)), <-rings.preserves_mult. |
| 221 |
rewrite shiftl_nat_pow_alt, nat_pow_exp_mult. |
| 222 |
rewrite (commutativity a), associativity. |
| 223 |
rewrite <-(preserves_nat_pow_exp (f:=cast N nat) _ n). |
| 224 |
setoid_replace (2 ^ 2) with 4 by (rewrite nat_pow_2; ring). |
| 225 |
apply (right_cancellation (+) (4 * fst (AQsqrt_loop (' n)))). |
| 226 |
rewrite AQsqrt_loop_invariant1. ring. |
| 227 |
Qed. |
| 228 |
|
| 229 |
Lemma AQsqrt_mid_bounded_raw_square_upper_bound (n : N) : |
| 230 |
AQsqrt_mid_bounded_raw n ^ (2:N) ≤ a. |
| 231 |
Proof. |
| 232 |
rewrite AQsqrt_mid_bounded_spec. |
| 233 |
apply rings.nonneg_minus_compat; [| reflexivity]. |
| 234 |
now apply shiftl_nonneg, AQsqrt_loop_fst_nonneg. |
| 235 |
Qed. |
| 236 |
|
| 237 |
Definition AQsqrt_mid_raw (ε : Qpos) |
| 238 |
:= AQsqrt_mid_bounded_raw (plus (N_of_Z (-Qdlog2 (proj1_sig ε))) 3). |
| 239 |
|
| 240 |
Instance: Proper (QposEq ==> (=)) AQsqrt_mid_raw. |
| 241 |
Proof. unfold AQsqrt_mid_raw. intros [x?] [y?] E. change (x = y) in E. simpl. now rewrite E. Qed. |
| 242 |
|
| 243 |
Lemma AQsqrt_mid_bounded_prf: is_RegularFunction_noInf _ (AQsqrt_mid_raw : Qpos → AQ_as_MetricSpace). |
| 244 |
Proof. |
| 245 |
assert (∀ n m, m ≤ n → ball (2 ^ (-cast N Z m - 2)) |
| 246 |
(AQsqrt_mid_bounded_raw (n + 3) : AQ_as_MetricSpace) (AQsqrt_mid_bounded_raw (m + 3))). |
| 247 |
intros n m E. |
| 248 |
simpl. apply Qball_Qabs. rewrite Qabs.Qabs_pos. |
| 249 |
change ('AQsqrt_mid_bounded_raw (n + 3) - 'AQsqrt_mid_bounded_raw (m + 3) ≤ ((2 ^ (-'m - 2))%mc : Q)). |
| 250 |
rewrite <-rings.preserves_minus, <-(rings.mult_1_l (2 ^ (-'m - 2))). |
| 251 |
rewrite <-shiftl_int_pow. |
| 252 |
rewrite <-(rings.preserves_1 (f:=cast AQ Q)), <-(preserves_shiftl (f:=cast AQ Q)). |
| 253 |
apply (order_preserving _). |
| 254 |
mc_setoid_replace ((-'m - 2)%mc : Z) with ((1 - '(m + 3))%mc : Z). |
| 255 |
apply AQsqrt_mid_bounded_regular_aux1. |
| 256 |
now refine (order_preserving (+ (3%mc:N)) _ _ _). |
| 257 |
rewrite rings.preserves_plus, rings.preserves_3. ring. |
| 258 |
change (0 ≤ (('AQsqrt_mid_bounded_raw (n + 3) - 'AQsqrt_mid_bounded_raw (m + 3))%mc : Q)). |
| 259 |
apply rings.flip_nonneg_minus. |
| 260 |
apply (order_preserving _). |
| 261 |
apply AQsqrt_mid_bounded_regular_aux2. |
| 262 |
now refine (order_preserving (+ (3:N)) _ _ _). |
| 263 |
assert (∀ ε1 ε2 : Qpos, N_of_Z (-Qdlog2 (proj1_sig ε2)) ≤ N_of_Z (-Qdlog2 (proj1_sig ε1)) → |
| 264 |
ball (proj1_sig ε1 + proj1_sig ε2) (AQsqrt_mid_raw ε1 : AQ_as_MetricSpace) (AQsqrt_mid_raw ε2)). |
| 265 |
{ intros ε1 ε2 E. |
| 266 |
unfold AQsqrt_mid_raw. |
| 267 |
eapply ball_weak_le; auto. |
| 268 |
change ((2%mc:Q) ^ (-'N_of_Z (-Qdlog2 (proj1_sig ε2)) - 2) |
| 269 |
≤ proj1_sig ε1 + proj1_sig ε2). |
| 270 |
apply semirings.plus_le_compat_l. |
| 271 |
now apply orders.lt_le, Qpos_ispos. |
| 272 |
destruct (total (≤) (proj1_sig ε2) 1). |
| 273 |
rewrite N_of_Z_nonneg. |
| 274 |
change (- (-Qdlog2 (proj1_sig ε2))%Z) with (- -Qdlog2 (proj1_sig ε2)). |
| 275 |
rewrite rings.negate_involutive. |
| 276 |
rewrite int_pow_exp_plus by solve_propholds. |
| 277 |
transitivity ((2 ^ Qdlog2 (proj1_sig ε2))%mc : Q). |
| 278 |
2: now apply Qdlog2_spec, Qpos_ispos. |
| 279 |
rewrite <-(rings.mult_1_r (2 ^ Qdlog2 (proj1_sig ε2) : Q)) at 2. |
| 280 |
now apply (order_preserving (_ *.)). |
| 281 |
change (0 ≤ -Qdlog2 (proj1_sig ε2)). |
| 282 |
now apply rings.flip_nonpos_negate, Qdlog2_nonpos. |
| 283 |
transitivity (1:Q); auto. |
| 284 |
rewrite N_of_Z_nonpos; [easy|]. |
| 285 |
change (-Qdlog2 (proj1_sig ε2) ≤ 0). |
| 286 |
now apply rings.flip_nonneg_negate, Qdlog2_nonneg. } |
| 287 |
intros ε1 ε2. |
| 288 |
destruct (total (≤) (N_of_Z (-Qdlog2 (proj1_sig ε1))) |
| 289 |
(N_of_Z (-Qdlog2 (proj1_sig ε2)))); auto. |
| 290 |
apply ball_sym. |
| 291 |
rewrite Qplus_comm. auto. |
| 292 |
Qed. |
| 293 |
|
| 294 |
Definition AQsqrt_mid : AR := mkRegularFunction (0 : AQ_as_MetricSpace) AQsqrt_mid_bounded_prf. |
| 295 |
|
| 296 |
Lemma AQsqrt_mid_upper_bound : AQsqrt_mid ≤ 4. |
| 297 |
Proof. |
| 298 |
intros ε. |
| 299 |
transitivity (0 : Q). |
| 300 |
apply rings.flip_nonneg_negate. |
| 301 |
now apply orders.lt_le, Qpos_ispos. |
| 302 |
change ((0:Q) ≤ '(4 - AQsqrt_mid_raw ((1#2) * ε))). |
| 303 |
apply semirings.preserves_nonneg, rings.flip_nonneg_minus. |
| 304 |
now apply AQsqrt_mid_bounded_raw_upper_bound. |
| 305 |
Qed. |
| 306 |
|
| 307 |
Lemma AQsqrt_mid_nonneg : 0 ≤ AQsqrt_mid. |
| 308 |
Proof. |
| 309 |
intros ε. |
| 310 |
transitivity (0 : Q). |
| 311 |
apply rings.flip_nonneg_negate. |
| 312 |
now apply orders.lt_le, Qpos_ispos. |
| 313 |
change ((0:Q) ≤ '(AQsqrt_mid_raw ((1#2) * ε) - 0)). |
| 314 |
apply semirings.preserves_nonneg, rings.flip_nonneg_minus. |
| 315 |
now apply AQsqrt_mid_bounded_raw_lower_bound. |
| 316 |
Qed. |
| 317 |
|
| 318 |
Lemma AQsqrt_mid_spec : AQsqrt_mid ^ (2:N)= 'a. |
| 319 |
Proof. |
| 320 |
assert (∀ ε, Qball (proj1_sig ε) ('(AQsqrt_mid_raw ε ^ (2:N))) ('a)) as P. |
| 321 |
{ intros ε. apply Qball_Qabs. rewrite Qabs.Qabs_neg. |
| 322 |
eapply Qle_trans. |
| 323 |
2: now apply Qpos_dlog2_spec. |
| 324 |
change (-( '(AQsqrt_mid_raw ε ^ 2) - 'a) ≤ ((2 ^ Qdlog2 (proj1_sig ε))%mc : Q)). |
| 325 |
rewrite <-rings.negate_swap_r. |
| 326 |
unfold AQsqrt_mid_raw. rewrite AQsqrt_mid_bounded_spec. |
| 327 |
rewrite rings.preserves_minus, preserves_shiftl. ring_simplify. |
| 328 |
apply shiftl_le_flip_l. |
| 329 |
etransitivity. |
| 330 |
apply (order_preserving _). |
| 331 |
now apply AQsqrt_loop_fst_upper_bound. |
| 332 |
rewrite preserves_nat_pow, rings.preserves_2. |
| 333 |
rewrite <-(int_pow_nat_pow (f:=cast nat Z)). |
| 334 |
rewrite shiftl_int_pow, <-int_pow_exp_plus by solve_propholds. |
| 335 |
apply int_pow_exp_le; [apply semirings.le_1_2|]. |
| 336 |
rewrite rings.preserves_plus, (naturals.to_semiring_twice _ _ (cast N Z)). |
| 337 |
rewrite (rings.preserves_plus _ 3), !rings.preserves_3. |
| 338 |
apply (order_reflecting (+ -(3 + 3))). ring_simplify. |
| 339 |
destruct (total (≤) (proj1_sig ε) 1). |
| 340 |
rewrite N_of_Z_nonneg. |
| 341 |
apply orders.eq_le. |
| 342 |
change (-Qdlog2 (proj1_sig ε) = 2 * -Qdlog2 (proj1_sig ε) + Qdlog2 (proj1_sig ε)). |
| 343 |
ring. |
| 344 |
change (0 ≤ -Qdlog2 (proj1_sig ε)). |
| 345 |
now apply rings.flip_nonpos_negate, Qdlog2_nonpos. |
| 346 |
rewrite N_of_Z_nonpos. |
| 347 |
now apply Qdlog2_nonneg. |
| 348 |
change (-Qdlog2 (proj1_sig ε) ≤ 0). |
| 349 |
now apply rings.flip_nonneg_negate, Qdlog2_nonneg. |
| 350 |
change ('(AQsqrt_mid_raw ε ^ 2) - 'a ≤ (0:Q)). |
| 351 |
apply rings.flip_nonpos_minus. |
| 352 |
apply (order_preserving _). |
| 353 |
now apply AQsqrt_mid_bounded_raw_square_upper_bound. } |
| 354 |
rewrite <-(ARpower_N_bounded_N_power _ _ 4). |
| 355 |
- intros ε1 ε2. rewrite Qplus_0_r. simpl. |
| 356 |
rewrite lattices.meet_r, lattices.join_r. |
| 357 |
+ apply ball_weak. apply Qpos_nonneg. |
| 358 |
apply ball_weak_le with (proj1_sig (ε1 * Qpos_inv (8 # 1))%Qpos). |
| 359 |
change ('ε1 / (8#1) ≤ 'ε1). |
| 360 |
rewrite <-(rings.mult_1_r ('ε1)) at 2. |
| 361 |
apply Qmult_le_l. apply Qpos_ispos. discriminate. |
| 362 |
assert (QposEq (ε1 * Qpos_inv ((2#1) * Qpos_power (' 4) 1)) |
| 363 |
(ε1 * Qpos_inv (8#1))). |
| 364 |
unfold QposEq. simpl. |
| 365 |
pose proof AQposAsQpos_preserves_4. |
| 366 |
unfold equiv, sig_equiv, equiv, stdlib_rationals.Q_eq in H5. |
| 367 |
simpl. rewrite H5. reflexivity. |
| 368 |
rewrite H5. apply P. |
| 369 |
+ transitivity (0:AQ). |
| 370 |
apply rings.flip_nonneg_negate. now apply semirings.le_0_4. |
| 371 |
now apply AQsqrt_mid_bounded_raw_lower_bound. |
| 372 |
+ now apply AQsqrt_mid_bounded_raw_upper_bound. |
| 373 |
- split. |
| 374 |
transitivity (0:AR). |
| 375 |
apply rings.flip_nonneg_negate. |
| 376 |
apply (semirings.preserves_nonneg (f:=cast AQ AR)). |
| 377 |
now apply semirings.le_0_4. |
| 378 |
now apply AQsqrt_mid_nonneg. |
| 379 |
now apply AQsqrt_mid_upper_bound. |
| 380 |
Qed. |
| 381 |
|
| 382 |
Lemma AQsqrt_mid_correct : 'AQsqrt_mid = rational_sqrt ('a). |
| 383 |
Proof. |
| 384 |
apply rational_sqrt_unique. |
| 385 |
apply semirings.preserves_nonneg. |
| 386 |
red. transitivity 1; [solve_propholds | intuition]. |
| 387 |
change ('AQsqrt_mid ^ (2 : N) = cast Q CR (cast AQ Q a)). |
| 388 |
rewrite <-preserves_nat_pow. |
| 389 |
rewrite AQsqrt_mid_spec. |
| 390 |
now apply ARtoCR_inject. |
| 391 |
change (0%CR) with (0%mc : CR). |
| 392 |
rewrite <-(rings.preserves_0 (f:=cast AR CR)). |
| 393 |
apply (order_preserving _). |
| 394 |
now apply AQsqrt_mid_nonneg. |
| 395 |
Qed. |
| 396 |
End sqrt_mid. |
| 397 |
|
| 398 |
Section sqrt_pos. |
| 399 |
Context `(Pa : 0 < a). |
| 400 |
|
| 401 |
Local Obligation Tactic := idtac. |
| 402 |
Program Definition AQsqrt_pos := |
| 403 |
let n := Qdlog4 ('a) in ARscale (1 ≪ n) (AQsqrt_mid (a:=a ≪ (2 * -n)) _). |
| 404 |
Next Obligation. |
| 405 |
simpl. split. |
| 406 |
apply (order_reflecting (cast AQ Q)). |
| 407 |
rewrite rings.preserves_1, aq_shift_correct. |
| 408 |
rewrite int_pow_exp_mult. |
| 409 |
change (2 ^ 2 : Q) with (4 : Q). |
| 410 |
apply (order_reflecting (.* 4 ^ Qdlog4 ('a))). |
| 411 |
rewrite <-associativity, <-int_pow_exp_plus by (compute; discriminate). |
| 412 |
rewrite rings.mult_1_l, rings.plus_negate_l, int_pow_0, rings.mult_1_r. |
| 413 |
apply Qdlog4_spec. |
| 414 |
now apply semirings.preserves_pos. |
| 415 |
apply (order_reflecting (cast AQ Q)). |
| 416 |
rewrite aq_shift_correct, rings.preserves_4. |
| 417 |
rewrite int_pow_exp_mult. |
| 418 |
change (2 ^ 2 : Q) with (4 : Q). |
| 419 |
apply (order_reflecting (.* 4 ^ Qdlog4 ('a))). |
| 420 |
rewrite <-associativity, <-int_pow_exp_plus by (compute; discriminate). |
| 421 |
rewrite rings.plus_negate_l, int_pow_0, rings.mult_1_r. |
| 422 |
rewrite <-int_pow_S by (compute; discriminate). |
| 423 |
apply orders.lt_le, Qdlog4_spec. |
| 424 |
now apply semirings.preserves_pos. |
| 425 |
Qed. |
| 426 |
|
| 427 |
Lemma AQsqrt_pos_correct : 'AQsqrt_pos = rational_sqrt ('a). |
| 428 |
Proof. |
| 429 |
unfold AQsqrt_pos. |
| 430 |
rewrite ARtoCR_preserves_scale, AQsqrt_mid_correct. |
| 431 |
transitivity (scale (2 ^ Qdlog4 (' a)) |
| 432 |
(rational_sqrt (' (a ≪ (2 * - Qdlog4 (' a)))))). |
| 433 |
apply Cmap_wd. |
| 434 |
rewrite aq_shift_correct, rings.preserves_1, rings.mult_1_l. |
| 435 |
reflexivity. reflexivity. |
| 436 |
rewrite aq_shift_correct. |
| 437 |
rewrite int_pow_exp_mult. |
| 438 |
apply rational_sqrt_scale. |
| 439 |
apply semirings.preserves_nonneg. |
| 440 |
now apply orders.lt_le. |
| 441 |
Qed. |
| 442 |
End sqrt_pos. |
| 443 |
|
| 444 |
Program Definition AQsqrt (a : AQ) : AR := |
| 445 |
if decide_rel (≤) a 0 then 0 else AQsqrt_pos (a:=a) _. |
| 446 |
Next Obligation. now apply orders.not_le_lt_flip. Qed. |
| 447 |
|
| 448 |
Lemma AQsqrt_correct (a : AQ) : 'AQsqrt a = rational_sqrt ('a). |
| 449 |
Proof. |
| 450 |
unfold AQsqrt. |
| 451 |
case (decide_rel _); intros E. |
| 452 |
rewrite rational_sqrt_nonpos. |
| 453 |
now apply rings.preserves_0. |
| 454 |
now apply semirings.preserves_nonpos. |
| 455 |
now apply AQsqrt_pos_correct. |
| 456 |
Qed. |
| 457 |
|
| 458 |
Local Obligation Tactic := idtac. |
| 459 |
Require Import CoRN.metric2.MetricMorphisms. |
| 460 |
|
| 461 |
Program Definition ARsqrt_uc := unary_complete_uc |
| 462 |
QPrelengthSpace (cast AQ Q_as_MetricSpace) AQsqrt sqrt_uc _. |
| 463 |
Next Obligation. intros a. apply AQsqrt_correct. Qed. |
| 464 |
|
| 465 |
Definition ARsqrt := Cbind AQPrelengthSpace ARsqrt_uc. |
| 466 |
|
| 467 |
Lemma ARtoCR_preserves_sqrt (x : AR) : 'ARsqrt x = CRsqrt ('x). |
| 468 |
Proof. apply preserves_unary_complete_fun. Qed. |
| 469 |
|
| 470 |
Lemma ARsqrt_correct : forall (x : AR), |
| 471 |
ARle 0 x -> ARsqrt x * ARsqrt x = x. |
| 472 |
Proof. |
| 473 |
intros x xpos. |
| 474 |
apply (injective (Eembed QPrelengthSpace (cast AQ Q_as_MetricSpace))). |
| 475 |
change (Eembed QPrelengthSpace (cast AQ Q_as_MetricSpace) x) |
| 476 |
with ('x). |
| 477 |
change (Eembed QPrelengthSpace (cast AQ Q_as_MetricSpace) (ARsqrt x * ARsqrt x)) |
| 478 |
with ('(ARsqrt x * ARsqrt x)). |
| 479 |
rewrite (ARtoCR_preserves_mult (ARsqrt x) (ARsqrt x)). |
| 480 |
rewrite ARtoCR_preserves_sqrt. |
| 481 |
apply CRsqrt_sqr. |
| 482 |
rewrite <- ARtoCR_preserves_0. |
| 483 |
apply (ARtoCR_preserves_le 0 x), xpos. |
| 484 |
Qed. |
| 485 |
|
| 486 |
Lemma ARsqrt_mult : forall (x y : AR), |
| 487 |
ARle 0 x -> ARle 0 y -> ARsqrt (x*y) = ARsqrt x * ARsqrt y. |
| 488 |
Proof. |
| 489 |
intros. |
| 490 |
apply (injective (Eembed QPrelengthSpace (cast AQ Q_as_MetricSpace))). |
| 491 |
change (Eembed QPrelengthSpace (cast AQ Q_as_MetricSpace) (ARsqrt (x*y))) |
| 492 |
with ('(ARsqrt (x*y))). |
| 493 |
change (Eembed QPrelengthSpace (cast AQ Q_as_MetricSpace) (ARsqrt x * ARsqrt y)) |
| 494 |
with ('(ARsqrt x * ARsqrt y)). |
| 495 |
rewrite (ARtoCR_preserves_mult (ARsqrt x) (ARsqrt y)). |
| 496 |
rewrite ARtoCR_preserves_sqrt. |
| 497 |
rewrite ARtoCR_preserves_sqrt. |
| 498 |
rewrite ARtoCR_preserves_sqrt. |
| 499 |
rewrite <- CRsqrt_mult. |
| 500 |
rewrite ARtoCR_preserves_mult. reflexivity. |
| 501 |
rewrite <- ARtoCR_preserves_0. |
| 502 |
apply (ARtoCR_preserves_le 0 x), H5. |
| 503 |
rewrite <- ARtoCR_preserves_0. |
| 504 |
apply (ARtoCR_preserves_le 0 y), H6. |
| 505 |
Qed. |
| 506 |
|
| 507 |
Lemma ARsqrt_srq_abs : |
| 508 |
forall x : AR, ARsqrt (x*x) = ARabs x. |
| 509 |
Proof. |
| 510 |
(* Goal is a negation, use excluded middle x is positive or not. |
| 511 |
When positive, ARsqrt(x*x) = ARsqrt x*ARsqrt x = x. *) |
| 512 |
assert (forall x : AR, ARle 0 x -> ARsqrt (x*x) = ARabs x) as posCase. |
| 513 |
{ intros. |
| 514 |
rewrite ARsqrt_mult, ARsqrt_correct. |
| 515 |
rewrite ARabs_pos. reflexivity. |
| 516 |
exact H5. exact H5. |
| 517 |
exact H5. exact H5. } |
| 518 |
intros. apply ball_stable. |
| 519 |
intro abs. assert (~(ARle 0 x)). |
| 520 |
- intro H5. contradict abs. |
| 521 |
apply posCase, H5. |
| 522 |
- contradict H5. |
| 523 |
apply ARle_not_lt. intro H5. |
| 524 |
contradict abs. |
| 525 |
change (ARsqrt (x*x) = ARabs x). |
| 526 |
rewrite <- ARabs_opp. |
| 527 |
setoid_replace (x * x) with (-x * -x) by ring. |
| 528 |
apply posCase. |
| 529 |
destruct (ARtoCR_preserves_ltT x 0) as [c _]. |
| 530 |
specialize (c H5). |
| 531 |
apply ARtoCR_preserves_le. |
| 532 |
rewrite ARtoCR_preserves_0. |
| 533 |
rewrite <- CRopp_0. |
| 534 |
rewrite ARtoCR_preserves_opp. |
| 535 |
apply CRopp_le_compat. |
| 536 |
rewrite <- ARtoCR_preserves_0. |
| 537 |
apply CRlt_le_weak, c. |
| 538 |
Qed. |
| 539 |
|
| 540 |
Lemma ARsqrt_inc : |
| 541 |
forall x y : AR, |
| 542 |
ARle 0 x -> ARle x y -> ARle (ARsqrt x) (ARsqrt y). |
| 543 |
Proof. |
| 544 |
intros. |
| 545 |
apply ARtoCR_preserves_le. |
| 546 |
rewrite ARtoCR_preserves_sqrt. |
| 547 |
rewrite ARtoCR_preserves_sqrt. |
| 548 |
apply CRsqrt_inc. |
| 549 |
rewrite <- ARtoCR_preserves_0. |
| 550 |
apply (ARtoCR_preserves_le 0 x), H5. |
| 551 |
apply (ARtoCR_preserves_le x y), H6. |
| 552 |
Qed. |
| 553 |
|
| 554 |
End ARsqrt. |