| 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 |
Require Import CoRN.reals.Q_in_CReals. |
| 26 |
Require Import CoRN.reals.fast.CRpower. |
| 27 |
Require Export CoRN.reals.fast.CRArith. |
| 28 |
Require Import CoRN.reals.fast.CRIR. |
| 29 |
Require Import CoRN.reals.NRootIR. |
| 30 |
Require Import CoRN.model.totalorder.QMinMax. |
| 31 |
Require Import CoRN.model.totalorder.QposMinMax. |
| 32 |
Require Import CoRN.model.metric2.Qmetric. |
| 33 |
From Coq Require Import Qpower. |
| 34 |
Require Import CoRN.model.ordfields.Qordfield. |
| 35 |
Require Import CoRN.reals.fast.Compress. |
| 36 |
Require Import CoRN.reals.fast.PowerBound. |
| 37 |
Require Import CoRN.transc.RealPowers. |
| 38 |
Require Import CoRN.reals.fast.ContinuousCorrect. |
| 39 |
Require Import CoRN.tactics.Qauto. |
| 40 |
Require Import CoRN.tactics.CornTac. |
| 41 |
Require Import MathClasses.interfaces.abstract_algebra. |
| 42 |
|
| 43 |
(* Backwards compatibility for Hint Rewrite locality attributes *) |
| 44 |
Set Warnings "-unsupported-attributes". |
| 45 |
|
| 46 |
Local Open Scope Q_scope. |
| 47 |
|
| 48 |
Opaque CR. |
| 49 |
Opaque Qmin Qmax. |
| 50 |
|
| 51 |
(** |
| 52 |
** Square Root |
| 53 |
Square root is implement using Newton's method. |
| 54 |
*) |
| 55 |
|
| 56 |
Section SquareRoot. |
| 57 |
|
| 58 |
Variable a : Q. |
| 59 |
|
| 60 |
Hypothesis Ha : 1 <= a <= 4. |
| 61 |
(** Square root is first defined on [[1,4]]. Iterating this formula will |
| 62 |
converge to the square root of [a]. *) |
| 63 |
Definition root_step (b:Q) : Q := b / (2#1) + a / ((2#1) * b). |
| 64 |
|
| 65 |
Definition root_has_error (e:Qpos) (b:Q) := a <= (b+proj1_sig e)^2 /\ (b-proj1_sig e)^2 <= a. |
| 66 |
(* begin hide *) |
| 67 |
Add Morphism root_has_error with signature QposEq ==> Qeq ==> iff as root_has_error_wd. |
| 68 |
Proof. |
| 69 |
intros x1 x2 Hx y1 y2 Hy. |
| 70 |
unfold root_has_error. |
| 71 |
rewrite -> Hy. |
| 72 |
unfold QposEq in Hx. |
| 73 |
rewrite -> Hx. |
| 74 |
reflexivity. |
| 75 |
Qed. |
| 76 |
(* end hide *) |
| 77 |
Lemma root_has_error_le : forall (e1 e2:Qpos) (b:Q), proj1_sig e2 <= b -> proj1_sig e1 <= proj1_sig e2 -> root_has_error e1 b -> root_has_error e2 b. |
| 78 |
Proof. |
| 79 |
intros e1 e2 b Hb He [H0 H1]. |
| 80 |
rewrite -> Qle_minus_iff in *. |
| 81 |
split; rewrite -> Qle_minus_iff. |
| 82 |
replace RHS with (((b + proj1_sig e1) ^ 2 + - a) + (proj1_sig e2 + - proj1_sig e1)*((2#1) * (b + - proj1_sig e2 + proj1_sig e2) + proj1_sig e2 + proj1_sig e1)) by ring. |
| 83 |
Qauto_nonneg. |
| 84 |
replace RHS with ((a + - (b-proj1_sig e1)^2) + (proj1_sig e2 + -proj1_sig e1)*((proj1_sig e2 + - proj1_sig e1) + (2#1) * (b + - proj1_sig e2))) by ring. |
| 85 |
Qauto_nonneg. |
| 86 |
Qed. |
| 87 |
|
| 88 |
Lemma root_error_bnd : forall (e:Qpos) b, proj1_sig e <= 1 -> 1 <= b -> (root_has_error e b) -> b <= (2#1) + proj1_sig e. |
| 89 |
Proof. |
| 90 |
intros e b He Hb [H0 H1]. |
| 91 |
destruct Ha as [Ha0 Ha1]. |
| 92 |
rewrite -> Qle_minus_iff in *. |
| 93 |
assert (X:0 < 2 + b - proj1_sig e). |
| 94 |
apply Qlt_le_trans with 2. |
| 95 |
constructor. |
| 96 |
rewrite -> Qle_minus_iff. |
| 97 |
replace RHS with ((b + -(1)) + (1 + - proj1_sig e)) by (simpl; ring). |
| 98 |
Qauto_nonneg. |
| 99 |
replace RHS with ((((4#1) + - a) + (a + - (b - proj1_sig e)^2))/((2#1) + b - proj1_sig e)) by simpl; field; auto with *. |
| 100 |
apply Qle_shift_div_l. |
| 101 |
assumption. |
| 102 |
replace LHS with 0 by simpl; ring. |
| 103 |
Qauto_nonneg. |
| 104 |
Qed. |
| 105 |
|
| 106 |
Lemma root_has_error_ball : forall (e1 e2:Qpos) (b1 b2:Q), |
| 107 |
(proj1_sig e1 + proj1_sig e2<=1) -> (1 <= b1) -> (1 <= b2) -> root_has_error e1 b1 |
| 108 |
-> Qball (proj1_sig e2) b1 b2 -> root_has_error (e1+e2) b2. |
| 109 |
Proof. |
| 110 |
intros e1 e2 b1 b2 He Hb1 Hb2 [H0 H1] [H2 H3]. |
| 111 |
simpl in H2, H3. |
| 112 |
clear Ha. |
| 113 |
rewrite -> Qle_minus_iff in *. |
| 114 |
unfold root_has_error. |
| 115 |
autorewrite with QposElim. |
| 116 |
split; rewrite -> Qle_minus_iff. |
| 117 |
replace RHS with (((b1 + proj1_sig e1)^2 + - a) + (b2 + - (1) + proj1_sig e1 + proj1_sig e2 + (b1 + -(1)) + (2#1) + proj1_sig e1)*(proj1_sig e2 - (b1 - b2))) by simpl; ring. |
| 118 |
Qauto_nonneg. |
| 119 |
replace RHS with ((a + - (b1 - proj1_sig e1)^2) + (b1 - b2 + - - proj1_sig e2)*((b1 + -(1)) + (1 + - (proj1_sig e1 + proj1_sig e2)) + proj1_sig e2 + (b2 + -(1)) + (1 + - (proj1_sig e1 + proj1_sig e2)))) by simpl; ring. |
| 120 |
Qauto_nonneg. |
| 121 |
Qed. |
| 122 |
|
| 123 |
Lemma ball_root_has_error : forall (e1 e2:Qpos) (b1 b2:Q), |
| 124 |
((proj1_sig e1 + proj1_sig e2)<=1) -> (1<=b1) -> (1<=b2) -> root_has_error e1 b1 |
| 125 |
-> root_has_error e2 b2 -> Qball (proj1_sig e1+proj1_sig e2) b1 b2. |
| 126 |
Proof. |
| 127 |
intros e1 e2 b1 b2 He Hb1 Hb2 [H0 H1] [H2 H3]. |
| 128 |
clear Ha. |
| 129 |
rewrite -> Qle_minus_iff in *. |
| 130 |
split; simpl; rewrite -> Qle_minus_iff. |
| 131 |
assert (A0:0 < (b1 + proj1_sig e1 + b2 - proj1_sig e2)). |
| 132 |
apply Qlt_le_trans with 1;[constructor|]. |
| 133 |
rewrite -> Qle_minus_iff. |
| 134 |
replace RHS with (b1 + - (1) + (b2 + - (1)) + (2#1) * proj1_sig e1 + (1 - (proj1_sig e1 + proj1_sig e2))) by simpl; ring. |
| 135 |
Qauto_nonneg. |
| 136 |
replace RHS with ((((b1 + proj1_sig e1)^2 + - a) + (a + - (b2 - proj1_sig e2)^2))/(b1 + proj1_sig e1 +b2 - proj1_sig e2)) by (simpl; field; auto with * ). |
| 137 |
Qauto_nonneg. |
| 138 |
assert (A0:0 < (b2 + proj1_sig e2 + b1 - proj1_sig e1)). |
| 139 |
apply Qlt_le_trans with 1;[constructor|]. |
| 140 |
rewrite -> Qle_minus_iff. |
| 141 |
replace RHS with (b2 + - (1) + (b1 + - (1)) + (2#1) * proj1_sig e2 + (1 - (proj1_sig e1 + proj1_sig e2))) by simpl; ring. |
| 142 |
Qauto_nonneg. |
| 143 |
replace RHS with (((a + -(b1 - proj1_sig e1)^2) + ((b2 + proj1_sig e2)^2 + - a))/(b2 + proj1_sig e2 + b1 - proj1_sig e1)) by (simpl; field;auto with * ). |
| 144 |
Qauto_nonneg. |
| 145 |
Qed. |
| 146 |
|
| 147 |
Lemma root_step_error : forall b (e:Qpos), |
| 148 |
(1 <= b) -> (proj1_sig e <= 1) -> root_has_error e b -> root_has_error ((1#2)*(e*e)) (root_step b). |
| 149 |
Proof. |
| 150 |
intros b e Hb He [H0 H1]. |
| 151 |
unfold root_step. |
| 152 |
assert (A0:0 < b). |
| 153 |
apply Qlt_le_trans with 1; try assumption. |
| 154 |
Qauto_pos. |
| 155 |
assert (A1:(0 <= b - proj1_sig e^2)). |
| 156 |
replace RHS with (b + - proj1_sig e^2) by simpl; ring. |
| 157 |
rewrite <- Qle_minus_iff. |
| 158 |
apply Qle_trans with ((1:Q)[^]2); try assumption. |
| 159 |
replace LHS with ((proj1_sig e)[^]2) by (simpl; ring). |
| 160 |
apply: (power_resp_leEq);simpl; try assumption. |
| 161 |
apply Qpos_nonneg. |
| 162 |
assert (A2:(0 <= a)). |
| 163 |
eapply Qle_trans;[|apply H1]. |
| 164 |
replace RHS with ((b-proj1_sig e)[^]2) by (simpl; ring). |
| 165 |
apply: sqr_nonneg. |
| 166 |
split. |
| 167 |
apply Qle_trans with ((b / (2#1) + a / ((2#1) * b))^2); [|Qauto_le]. |
| 168 |
field_simplify (b / (2#1) + a / ((2#1) * b)); auto with *. |
| 169 |
rewrite -> Qdiv_power. |
| 170 |
apply Qle_shift_div_l. |
| 171 |
Qauto_pos. |
| 172 |
rewrite -> Qle_minus_iff. |
| 173 |
replace RHS with ((b^2 - a)[^]2) by (simpl; ring). |
| 174 |
apply: sqr_nonneg. |
| 175 |
field_simplify (b / (2#1) + a / ((2#1) * b) - ((1#2)*proj1_sig (e * e)%Qpos)); auto with *. |
| 176 |
rewrite -> Qdiv_power. |
| 177 |
apply Qle_shift_div_r. |
| 178 |
Qauto_pos. |
| 179 |
replace LHS with ((a + b^2 - b*proj1_sig e^2)^2) by simpl; ring. |
| 180 |
apply Qle_trans with ((a + b^2 - proj1_sig e^2)^2). |
| 181 |
replace RHS with ((a + b ^ 2 - proj1_sig e ^ 2)[^]2) by (simpl; ring). |
| 182 |
replace LHS with ((a + b ^ 2 - b * proj1_sig e ^ 2)[^]2) by (simpl; ring). |
| 183 |
apply: (power_resp_leEq). |
| 184 |
replace RHS with (a + b*(b-proj1_sig e^2)) by simpl; ring. |
| 185 |
Qauto_nonneg. |
| 186 |
rewrite -> Qle_minus_iff;ring_simplify. |
| 187 |
replace RHS with ((b-1)*((proj1_sig e)[^]2)) by (simpl; ring). |
| 188 |
rewrite -> Qle_minus_iff in Hb. |
| 189 |
Qauto_nonneg. |
| 190 |
rewrite -> Qle_minus_iff. |
| 191 |
replace RHS with ((a-(b-proj1_sig e)^2)*((b+proj1_sig e)^2-a)) by simpl; ring. |
| 192 |
rewrite -> Qle_minus_iff in *|-. |
| 193 |
apply: mult_resp_nonneg; assumption. |
| 194 |
Qed. |
| 195 |
|
| 196 |
(** Our initial estimate is (a+1)/2 with an error of 1/2 *) |
| 197 |
Definition initial_root :Q := ((1#2)*(a+1)). |
| 198 |
|
| 199 |
Lemma initial_root_error : root_has_error (1#2) initial_root. |
| 200 |
Proof. |
| 201 |
destruct Ha as [Ha0 Ha1]. |
| 202 |
unfold initial_root, root_has_error. |
| 203 |
simpl. |
| 204 |
split. |
| 205 |
Qauto_le. |
| 206 |
rewrite -> Qle_minus_iff. |
| 207 |
assert (A0:(0<=1 + -((1#4)*a))). |
| 208 |
rewrite <- Qle_minus_iff. |
| 209 |
replace LHS with (a/(4#1)) by (simpl; field; discriminate). |
| 210 |
apply Qle_shift_div_r; try assumption. |
| 211 |
Qauto_pos. |
| 212 |
rewrite -> Qle_minus_iff in Ha0. |
| 213 |
replace RHS with ((a + -(1) + 1)*(1 +- ((1#4)*a))) by simpl; ring. |
| 214 |
Qauto_nonneg. |
| 215 |
Qed. |
| 216 |
|
| 217 |
Lemma root_step_one_le : forall b, (1 <= b)-> (1 <= root_step b). |
| 218 |
Proof. |
| 219 |
intros b Hb. |
| 220 |
assert (A0:0<b). |
| 221 |
apply Qlt_le_trans with 1; auto with *. |
| 222 |
destruct Ha as [Ha0 Ha1]. |
| 223 |
unfold root_step. |
| 224 |
rewrite -> Qle_minus_iff in *. |
| 225 |
field_simplify (b / (2#1) + a / ((2#1) * b) + -(1));auto with *. |
| 226 |
apply Qle_shift_div_l. |
| 227 |
Qauto_pos. |
| 228 |
ring_simplify. |
| 229 |
replace RHS with (((b -1) ^ 2 + (a + -(1)))) by simpl; ring. |
| 230 |
Qauto_nonneg. |
| 231 |
Qed. |
| 232 |
|
| 233 |
Lemma initial_root_one_le : (1 <= initial_root). |
| 234 |
Proof. |
| 235 |
destruct Ha as [Ha0 Ha1]. |
| 236 |
unfold initial_root. |
| 237 |
rewrite -> Qle_minus_iff in *. |
| 238 |
replace RHS with ((1#2)*(a + - (1))) by simpl; ring. |
| 239 |
Qauto_nonneg. |
| 240 |
Qed. |
| 241 |
|
| 242 |
(** Each step squares the error *) |
| 243 |
Fixpoint root_loop (e:Qpos) (n:nat) (b:Q) (err:positive) {struct n} : Q := |
| 244 |
match n with |
| 245 |
| O => b |
| 246 |
| S n' => match Qlt_le_dec_fast (proj1_sig e) (1#err) with |
| 247 |
| left _ => let err':= (err*err)%positive in root_loop e n' (approximateQ (root_step b) (2*err')) err' |
| 248 |
| right _ => b |
| 249 |
end |
| 250 |
end. |
| 251 |
|
| 252 |
Opaque root_step. |
| 253 |
|
| 254 |
Lemma root_loop_one_le : forall e n b err, (1 <= b)-> (1 <= root_loop e n b err). |
| 255 |
Proof. |
| 256 |
intros e n. |
| 257 |
induction n; auto with *. |
| 258 |
simpl. |
| 259 |
intros b err Hb. |
| 260 |
destruct (Qlt_le_dec_fast (proj1_sig e) (1 # err)) as [A|A]; try assumption. |
| 261 |
apply IHn. |
| 262 |
apply approximateQ_big. |
| 263 |
apply root_step_one_le. |
| 264 |
assumption. |
| 265 |
Qed. |
| 266 |
|
| 267 |
Lemma root_loop_error : forall (e:Qpos) n b err, (1 <= b) -> root_has_error (1#err) b -> (1#(iter_nat n _ (fun x => (x * x)%positive) err))<=proj1_sig e -> |
| 268 |
root_has_error (Qpos_min (1 # err) e) (root_loop e n b err). |
| 269 |
Proof. |
| 270 |
induction n. |
| 271 |
intros b err Hb0 Hb1 He. |
| 272 |
simpl in *. |
| 273 |
setoid_replace (Qpos_min (1 # err) e) with (1#err)%Qpos; try assumption. |
| 274 |
unfold QposEq. |
| 275 |
rewrite <- Qpos_le_min_l. |
| 276 |
assumption. |
| 277 |
intros b err Hb0 Hb1 He. |
| 278 |
simpl in *. |
| 279 |
destruct (Qlt_le_dec_fast (proj1_sig e) (1 # err)) as [A|A]. |
| 280 |
apply root_has_error_le with (Qpos_min (1#(err*err)) e). |
| 281 |
apply Qle_trans with 1. |
| 282 |
apply Qle_trans with (1#err); auto with *. |
| 283 |
apply Qpos_min_lb_l. |
| 284 |
apply root_loop_one_le. |
| 285 |
apply approximateQ_big. |
| 286 |
apply root_step_one_le; assumption. |
| 287 |
apply Qpos_min_glb. |
| 288 |
apply Qle_trans with (1#err*err). |
| 289 |
apply Qpos_min_lb_l. |
| 290 |
change (1*err <= err*err)%Z; auto with *. |
| 291 |
apply Qpos_min_lb_r. |
| 292 |
apply IHn; try assumption. |
| 293 |
apply approximateQ_big. |
| 294 |
apply root_step_one_le; assumption. |
| 295 |
assert (QposEq (1#err*err) ((1#(2*(err * err)))+(1#(2*(err * err))))). |
| 296 |
{ unfold QposEq. |
| 297 |
simpl. |
| 298 |
ring_simplify. |
| 299 |
constructor. } |
| 300 |
rewrite H. clear H. |
| 301 |
apply root_has_error_ball with (root_step b). |
| 302 |
simpl. |
| 303 |
ring_simplify. |
| 304 |
unfold Qmult, Qle; simpl. |
| 305 |
auto with *. |
| 306 |
apply root_step_one_le; assumption. |
| 307 |
apply approximateQ_big. |
| 308 |
apply root_step_one_le; assumption. |
| 309 |
apply (root_step_error b (1#err)); try assumption. |
| 310 |
unfold Qle; simpl; auto with *. |
| 311 |
apply approximateQ_correct. |
| 312 |
replace (iter_nat n positive (fun x : positive => (x * x)%positive) (err * err)%positive) |
| 313 |
with (iter_nat n positive (fun x : positive => (x * x)%positive) err * |
| 314 |
iter_nat n positive (fun x : positive => (x * x)%positive) err)%positive. |
| 315 |
assumption. |
| 316 |
clear - n. |
| 317 |
induction n; try constructor. |
| 318 |
simpl in *. |
| 319 |
rewrite IHn. |
| 320 |
reflexivity. |
| 321 |
setoid_replace (Qpos_min (1 # err) e) with (1#err)%Qpos; try assumption. |
| 322 |
unfold QposEq. |
| 323 |
rewrite <- Qpos_le_min_l. |
| 324 |
assumption. |
| 325 |
Qed. |
| 326 |
|
| 327 |
(** Find a bound on the number of iterations we need to take. *) |
| 328 |
Lemma root_max_steps : forall (n d:positive), (1#(iter_nat (S (Psize d)) _ (fun x => (x * x)%positive) 2%positive))<= proj1_sig (n#d)%Qpos. |
| 329 |
Proof. |
| 330 |
intros n d. |
| 331 |
apply Qle_trans with (1#d). |
| 332 |
clear - d. |
| 333 |
unfold Qle; simpl. |
| 334 |
cut ((d <= iter_nat (S (Psize d)) positive (fun x : positive => (x * x)%positive) |
| 335 |
2%positive)%Z/\(4 <= iter_nat (S (Psize d)) positive (fun x : positive => (x * x)%positive) |
| 336 |
2%positive)%Z). |
| 337 |
tauto. |
| 338 |
induction d; split; try discriminate; destruct IHd as [A B]; |
| 339 |
set (t:=iter_nat (S (Psize d)) positive (fun x : positive => (x * x)%positive) 2%positive) in *. |
| 340 |
rewrite Zpos_xI. |
| 341 |
apply Z.le_trans with (4*d)%Z; auto with *. |
| 342 |
apply (Zmult_le_compat 4 d t t); auto with *. |
| 343 |
change (4%Z) with (2*2)%Z. |
| 344 |
apply (Zmult_le_compat 2 2 t t); auto with *. |
| 345 |
rewrite Zpos_xO. |
| 346 |
apply Z.le_trans with (4*d)%Z; auto with *. |
| 347 |
apply (Zmult_le_compat 4 d t t); auto with *. |
| 348 |
change (4%Z) with (2*2)%Z. |
| 349 |
apply (Zmult_le_compat 2 2 t t); auto with *. |
| 350 |
unfold Qle; simpl. |
| 351 |
change (1*d <= n*d)%Z. |
| 352 |
auto with *. |
| 353 |
Qed. |
| 354 |
|
| 355 |
(** Square root on [[1,4]]. *) |
| 356 |
Definition sqrt_raw (e:QposInf) : Q := |
| 357 |
match e with |
| 358 |
| QposInfinity => 1 |
| 359 |
| Qpos2QposInf e' => root_loop e' (S (Psize (Qden (proj1_sig e')))) initial_root 2 |
| 360 |
end. |
| 361 |
|
| 362 |
Lemma sqrt_regular : is_RegularFunction Qball sqrt_raw. |
| 363 |
Proof. |
| 364 |
intros e1 e2. |
| 365 |
apply ball_weak_le with (proj1_sig (Qpos_min (1#2) e1 + Qpos_min (1#2) e2)%Qpos). |
| 366 |
- simpl. do 2 rewrite Q_Qpos_min. |
| 367 |
apply: plus_resp_leEq_both; simpl; auto with *. |
| 368 |
- apply ball_root_has_error. |
| 369 |
apply (Qle_trans _ (proj1_sig ((1#2) + (1#2))%Qpos)). |
| 370 |
2: simpl; ring_simplify; apply Qle_refl. |
| 371 |
apply: plus_resp_leEq_both; apply Qpos_min_lb_l. |
| 372 |
apply root_loop_one_le. |
| 373 |
apply initial_root_one_le. |
| 374 |
apply root_loop_one_le. |
| 375 |
apply initial_root_one_le. |
| 376 |
apply root_loop_error. |
| 377 |
apply initial_root_one_le. |
| 378 |
apply initial_root_error. |
| 379 |
revert e1. |
| 380 |
intros [[n d] epos]. |
| 381 |
destruct n as [|n|n]. inversion epos. 2: inversion epos. |
| 382 |
apply root_max_steps. |
| 383 |
apply root_loop_error. |
| 384 |
apply initial_root_one_le. |
| 385 |
apply initial_root_error. |
| 386 |
revert e2. |
| 387 |
intros [[n d] epos]. |
| 388 |
destruct n as [|n|n]. inversion epos. 2: inversion epos. |
| 389 |
apply root_max_steps. |
| 390 |
Qed. |
| 391 |
|
| 392 |
Definition rational_sqrt_mid : CR := Build_RegularFunction sqrt_regular. |
| 393 |
|
| 394 |
Lemma rational_sqrt_mid_err : forall (e:Qpos), (proj1_sig e <= 1) -> root_has_error e (approximate rational_sqrt_mid e). |
| 395 |
Proof. |
| 396 |
intros e He. |
| 397 |
change (root_has_error e (sqrt_raw e)). |
| 398 |
unfold sqrt_raw. |
| 399 |
eapply root_has_error_le;[| |apply root_loop_error]. |
| 400 |
eapply Qle_trans;[apply He|]. |
| 401 |
apply root_loop_one_le; apply initial_root_one_le. |
| 402 |
apply Qpos_min_lb_r. |
| 403 |
apply initial_root_one_le. |
| 404 |
apply initial_root_error. |
| 405 |
clear. |
| 406 |
revert e. |
| 407 |
intros [[n d] epos]. |
| 408 |
destruct n as [|n|n]. inversion epos. 2: inversion epos. |
| 409 |
apply root_max_steps. |
| 410 |
Qed. |
| 411 |
|
| 412 |
Lemma rational_sqrt_mid_one_le : forall (e:QposInf), 1 <= (approximate rational_sqrt_mid e). |
| 413 |
Proof. |
| 414 |
intros [e|];[|apply Qle_refl]. |
| 415 |
apply: root_loop_one_le. |
| 416 |
apply initial_root_one_le. |
| 417 |
Qed. |
| 418 |
|
| 419 |
Lemma rational_sqrt_mid_le_3 : forall (e:QposInf), (approximate rational_sqrt_mid e) <= 3. |
| 420 |
Proof. |
| 421 |
intros [e|];[|discriminate]. |
| 422 |
change (sqrt_raw e <= (3#1)). |
| 423 |
unfold sqrt_raw. |
| 424 |
set (n:= (S (Psize (Qden (proj1_sig e))))). |
| 425 |
assert (root_has_error (Qpos_min (1 # 2) e) (root_loop e n initial_root 2)). |
| 426 |
apply root_loop_error. |
| 427 |
apply initial_root_one_le. |
| 428 |
apply initial_root_error. |
| 429 |
subst n. |
| 430 |
clear. revert e. |
| 431 |
intros [[n d] epos]. |
| 432 |
destruct n as [|n|n]. inversion epos. 2: inversion epos. |
| 433 |
apply root_max_steps. |
| 434 |
eapply Qle_trans. |
| 435 |
apply root_error_bnd;[| |apply H]. |
| 436 |
eapply Qle_trans. |
| 437 |
apply Qpos_min_lb_l. |
| 438 |
discriminate. |
| 439 |
apply root_loop_one_le. |
| 440 |
apply initial_root_one_le. |
| 441 |
rewrite Q_Qpos_min. simpl. |
| 442 |
apply (Qle_trans _ (2 + (1#2))). |
| 443 |
apply Qplus_le_r, Qmin_lb_l. discriminate. |
| 444 |
Qed. |
| 445 |
|
| 446 |
Opaque root_loop. |
| 447 |
|
| 448 |
Lemma rational_sqrt_mid_correct0 : (CRpower_N rational_sqrt_mid 2 == ' a)%CR. |
| 449 |
Proof. |
| 450 |
assert (H:AbsSmall (R:=CRasCOrdField) (' (3 # 1))%CR rational_sqrt_mid). |
| 451 |
split; simpl. |
| 452 |
intros e. |
| 453 |
change (-proj1_sig e <= sqrt_raw (Qpos2QposInf ((1#2)*e)) + - - (3#1)). |
| 454 |
apply Qle_trans with 0. |
| 455 |
rewrite -> Qle_minus_iff. |
| 456 |
ring_simplify. |
| 457 |
auto with *. |
| 458 |
rewrite <- Qle_minus_iff. |
| 459 |
apply Qle_trans with 1. |
| 460 |
discriminate. |
| 461 |
apply rational_sqrt_mid_one_le. |
| 462 |
intros e. |
| 463 |
change (-proj1_sig e <= 3 + - sqrt_raw (Qpos2QposInf ((1#2)*e))). |
| 464 |
apply Qle_trans with 0. |
| 465 |
rewrite -> Qle_minus_iff. |
| 466 |
ring_simplify. |
| 467 |
auto with *. |
| 468 |
rewrite <- Qle_minus_iff. |
| 469 |
apply rational_sqrt_mid_le_3. |
| 470 |
rewrite <- (CRpower_N_bounded_N_power 2 (3#1));[|assumption]. |
| 471 |
apply regFunEq_equiv, (regFunEq_e_small (X:=Q_as_MetricSpace) (CRpower_N_bounded 2 (3 # 1) rational_sqrt_mid) (' a)%CR (1#1)). |
| 472 |
intros e. |
| 473 |
destruct e as [[en ed] epos]. |
| 474 |
destruct en as [|en|en]. inversion epos. 2: inversion epos. |
| 475 |
set (e := exist (Qlt 0) (en # ed) epos). |
| 476 |
intro He. |
| 477 |
set (d:= (e * Qpos_inv (6#1))%Qpos). |
| 478 |
simpl (approximate (' a)%CR (Qpos2QposInf ((en # ed) ↾ epos))). |
| 479 |
change (Qball (proj1_sig e + proj1_sig e) |
| 480 |
(approximate ((CRpower_N_bounded 2 (3 # 1)) rational_sqrt_mid) |
| 481 |
(Qpos2QposInf e)) a). |
| 482 |
assert ( |
| 483 |
(approximate ((CRpower_N_bounded 2 (3 # 1)) rational_sqrt_mid) (Qpos2QposInf e)) = |
| 484 |
((Qmax (- (3#1)) (Qmin (3#1) (approximate rational_sqrt_mid d)))^2) |
| 485 |
) as H0. |
| 486 |
{ simpl. |
| 487 |
replace d with (Qpos_mult e (Qpos_inv ((2 # 1) * (Qpos_power (3 # 1) (2 - 1)%positive)))). |
| 488 |
reflexivity. |
| 489 |
subst e d. |
| 490 |
apply Qpos_hprop. reflexivity. } |
| 491 |
rewrite H0. |
| 492 |
clear H0. |
| 493 |
setoid_replace (Qmin (3#1) (approximate rational_sqrt_mid d)) |
| 494 |
with ((approximate rational_sqrt_mid d)) by |
| 495 |
(rewrite <- Qle_min_r;destruct H;apply rational_sqrt_mid_le_3). |
| 496 |
setoid_replace (Qmax (-3#1) (approximate rational_sqrt_mid d)) |
| 497 |
with ((approximate rational_sqrt_mid d)) |
| 498 |
by (rewrite <- Qle_max_r;destruct H;eapply Qle_trans;[|apply rational_sqrt_mid_one_le];discriminate). |
| 499 |
assert (Z:root_has_error d (approximate rational_sqrt_mid d)). |
| 500 |
apply rational_sqrt_mid_err. |
| 501 |
unfold d. |
| 502 |
autorewrite with QposElim. |
| 503 |
change ((proj1_sig e/(6#1)) <= 1). |
| 504 |
apply Qle_shift_div_r. |
| 505 |
constructor. |
| 506 |
eapply Qle_trans. |
| 507 |
apply He. |
| 508 |
discriminate. |
| 509 |
set (z:=approximate rational_sqrt_mid d) in *. |
| 510 |
assert (X:z <= 3). |
| 511 |
apply rational_sqrt_mid_le_3. |
| 512 |
assert (X0:proj1_sig d^2 <= proj1_sig e). |
| 513 |
unfold d. |
| 514 |
autorewrite with QposElim in *. |
| 515 |
change ((proj1_sig e*(1#6))^2 <= proj1_sig e). |
| 516 |
rewrite -> Qle_minus_iff in *. |
| 517 |
replace RHS with (proj1_sig e*(1 + -proj1_sig e + (35#36)* proj1_sig e)) by simpl; ring. |
| 518 |
Qauto_nonneg. |
| 519 |
destruct Z; split; simpl; rewrite -> Qle_minus_iff in *; autorewrite with QposElim in *. |
| 520 |
replace RHS with (((z+proj1_sig d)^2 + - a) + (2#1) * ((3#1) + -z) * proj1_sig d + (proj1_sig e + - proj1_sig d^2)) |
| 521 |
by (simpl; unfold d;field;discriminate). |
| 522 |
Qauto_nonneg. |
| 523 |
replace RHS with (a + - (z-proj1_sig d)^2 + (2#1) * ((3#1) + - z)*proj1_sig d + proj1_sig d^2 + proj1_sig e) |
| 524 |
by (simpl; unfold d; autorewrite with QposElim;field;discriminate). |
| 525 |
Qauto_nonneg. |
| 526 |
Qed. (* todo: clean up *) |
| 527 |
|
| 528 |
Lemma rational_sqrt_mid_correct1 : (0 <= rational_sqrt_mid)%CR. |
| 529 |
Proof. |
| 530 |
intros e. |
| 531 |
apply Qle_trans with 1. |
| 532 |
Qauto_le. |
| 533 |
change (1 <= sqrt_raw (Qpos2QposInf ((1#2)%Qpos*e)) - 0). |
| 534 |
ring_simplify. |
| 535 |
apply rational_sqrt_mid_one_le. |
| 536 |
Qed. |
| 537 |
End SquareRoot. |
| 538 |
|
| 539 |
Lemma rational_sqrt_mid_correct_aux (x : Q) (y : CR) Px : |
| 540 |
CRpower_N y 2 = 'x → 0%CR ≤ y → y = IRasCR (sqrt (inj_Q IR x) Px). |
| 541 |
Proof. |
| 542 |
intros f_sqrt f_nonneg. |
| 543 |
rewrite <- (CRasIRasCR_id y). |
| 544 |
apply IRasCR_wd. |
| 545 |
assert (X:[0][<=](CRasIR y)[^]2). |
| 546 |
{ apply sqr_nonneg. } |
| 547 |
stepl (sqrt _ X). |
| 548 |
- apply sqrt_wd. |
| 549 |
rewrite -> IR_eq_as_CR. |
| 550 |
rewrite -> IR_inj_Q_as_CR. |
| 551 |
simpl. |
| 552 |
rewrite <- f_sqrt. |
| 553 |
rewrite <- (CRpower_N_correct 2). |
| 554 |
simpl. |
| 555 |
rewrite IR_mult_as_CR, IR_mult_as_CR. |
| 556 |
rewrite CRasIRasCR_id. rewrite IR_One_as_CR. |
| 557 |
ring. |
| 558 |
- apply sqrt_to_nonneg. |
| 559 |
rewrite -> IR_leEq_as_CR. |
| 560 |
rewrite -> IR_Zero_as_CR. |
| 561 |
now rewrite -> CRasIRasCR_id. |
| 562 |
Qed. |
| 563 |
|
| 564 |
Lemma rational_sqrt_mid_correct a Pa H : |
| 565 |
(rational_sqrt_mid a Pa == IRasCR (sqrt (inj_Q IR a) H))%CR. |
| 566 |
Proof. |
| 567 |
apply rational_sqrt_mid_correct_aux. |
| 568 |
now apply rational_sqrt_mid_correct0. |
| 569 |
now apply rational_sqrt_mid_correct1. |
| 570 |
Qed. |
| 571 |
|
| 572 |
(** By scaling the input the range of square root can be extened upto 4^n. |
| 573 |
*) |
| 574 |
Fixpoint rational_sqrt_big_bounded (n:nat) a (Ha:1 <= a <= (4 ^ n)%Z) { struct n } : CR. |
| 575 |
revert a Ha. |
| 576 |
destruct n as [|n]. |
| 577 |
intros _ _. |
| 578 |
exact 1%CR. |
| 579 |
intros a H. |
| 580 |
destruct (Qle_total a (4#1)). |
| 581 |
clear rational_sqrt_big_bounded. |
| 582 |
refine (@rational_sqrt_mid a _). |
| 583 |
abstract (destruct H; tauto). |
| 584 |
refine (scale (2#1) _). |
| 585 |
refine (@rational_sqrt_big_bounded n (a / (4#1)) _). |
| 586 |
clear rational_sqrt_big_bounded. |
| 587 |
abstract ( destruct H; split;[apply Qle_shift_div_l;[constructor|assumption]|]; |
| 588 |
apply Qle_shift_div_r;[constructor|]; rewrite -> Zpower_Qpower in * by auto with zarith; |
| 589 |
change (a <= ((4#1) ^ n) * (4#1)^1); rewrite <- Qpower_plus; try discriminate; change (n+1)%Z with (Z.succ n); |
| 590 |
rewrite <- inj_S; assumption). |
| 591 |
Defined. |
| 592 |
|
| 593 |
Lemma rational_sqrt_big_bounded_correct_aux a Xa4 Xa : |
| 594 |
((scale (2#1)) (IRasCR (sqrt (inj_Q IR (a / (4#1))) Xa4)) == IRasCR (sqrt (inj_Q IR a) Xa))%CR. |
| 595 |
Proof. |
| 596 |
rewrite <- CRmult_scale. |
| 597 |
rewrite <- IR_inj_Q_as_CR. |
| 598 |
rewrite <- IR_mult_as_CR. |
| 599 |
apply IRasCR_wd. |
| 600 |
assert (X1:[0][<=](inj_Q IR (4#1))). |
| 601 |
stepl (inj_Q IR 0); [| now (apply (inj_Q_nring IR 0))]. |
| 602 |
apply inj_Q_leEq. |
| 603 |
discriminate. |
| 604 |
csetoid_replace (inj_Q IR (2#1)) (sqrt _ X1). |
| 605 |
assert (X2:[0][<=](inj_Q IR (4#1)[*]inj_Q IR (a/4%positive))). |
| 606 |
apply mult_resp_nonneg;assumption. |
| 607 |
astepl (sqrt _ X2). |
| 608 |
apply sqrt_wd. |
| 609 |
csetoid_rewrite_rev (inj_Q_mult IR (4#1) (a/4%positive)). |
| 610 |
apply inj_Q_wd. |
| 611 |
simpl. |
| 612 |
field; discriminate. |
| 613 |
change (inj_Q IR (4#1)) with (inj_Q IR ((2#1)[*](2#1))). |
| 614 |
assert (X2:[0][<=](inj_Q IR (2#1))[^]2). |
| 615 |
apply sqr_nonneg. |
| 616 |
stepr (sqrt _ X2). |
| 617 |
apply eq_symmetric; apply sqrt_to_nonneg. |
| 618 |
stepl (inj_Q IR 0); [| now (apply (inj_Q_nring IR 0))]. |
| 619 |
apply inj_Q_leEq. |
| 620 |
discriminate. |
| 621 |
apply sqrt_wd. |
| 622 |
rstepl ((inj_Q IR (2#1))[*](inj_Q IR (2#1))). |
| 623 |
apply eq_symmetric. |
| 624 |
apply (inj_Q_mult IR (2#1) (2#1)). |
| 625 |
Qed. |
| 626 |
|
| 627 |
Lemma rational_sqrt_big_bounded_correct : forall n a Ha H, |
| 628 |
(@rational_sqrt_big_bounded n a Ha == IRasCR (sqrt (inj_Q IR a) H))%CR. |
| 629 |
Proof. |
| 630 |
induction n. |
| 631 |
intros a Ha H. |
| 632 |
simpl. |
| 633 |
rewrite <- IR_inj_Q_as_CR. |
| 634 |
apply IRasCR_wd. |
| 635 |
assert (X:[0][<=](inj_Q IR 1:IR)[^]2) by apply sqr_nonneg. |
| 636 |
stepl (sqrt _ X). |
| 637 |
apply sqrt_wd. |
| 638 |
rstepl (inj_Q IR 1[*]inj_Q IR 1). |
| 639 |
stepl (inj_Q IR (1*1)); [| now apply (inj_Q_mult IR)]. |
| 640 |
apply inj_Q_wd. |
| 641 |
simpl. |
| 642 |
rewrite -> Qeq_le_def. |
| 643 |
assumption. |
| 644 |
apply sqrt_to_nonneg. |
| 645 |
stepr (nring 1:IR); [| now (apply eq_symmetric; apply (inj_Q_nring IR 1))]. |
| 646 |
rstepr ([1]:IR). |
| 647 |
apply less_leEq; apply pos_one. |
| 648 |
intros a Ha H. |
| 649 |
simpl. |
| 650 |
destruct (Qle_total a). |
| 651 |
apply rational_sqrt_mid_correct. |
| 652 |
change (scale 2 (rational_sqrt_big_bounded n (a / 4%positive)(rational_sqrt_big_bounded_subproof0 n a Ha q)) == |
| 653 |
IRasCR (sqrt (inj_Q IR a) H))%CR. |
| 654 |
assert (X:[0][<=]inj_Q IR (a/4%positive)). |
| 655 |
change (a/4%positive) with (a*(1#4)). |
| 656 |
stepr (inj_Q IR a[*]inj_Q IR (1#4)); [| now apply eq_symmetric; apply (inj_Q_mult IR)]. |
| 657 |
apply mult_resp_nonneg. |
| 658 |
assumption. |
| 659 |
stepl (inj_Q IR 0); [| now (apply (inj_Q_nring IR 0))]. |
| 660 |
apply inj_Q_leEq. |
| 661 |
discriminate. |
| 662 |
set (X0:= (rational_sqrt_big_bounded_subproof0 n a Ha q)). |
| 663 |
rewrite -> (IHn (a/4%positive) X0 X). |
| 664 |
apply rational_sqrt_big_bounded_correct_aux. |
| 665 |
Qed. |
| 666 |
|
| 667 |
(** By scaling the other direction we can extend the range down to 4^(-n). |
| 668 |
*) |
| 669 |
Fixpoint rational_sqrt_small_bounded (n:nat) a (Ha: / (4^n)%Z <= a <= (4#1)) : CR. |
| 670 |
revert a Ha. |
| 671 |
destruct n as [|n]. |
| 672 |
clear rational_sqrt_small_bounded. |
| 673 |
refine (@rational_sqrt_mid). |
| 674 |
intros a H. |
| 675 |
destruct (Qle_total a 1). |
| 676 |
refine (scale (1#2) _). |
| 677 |
refine (@rational_sqrt_small_bounded n ((4#1) * a) _). |
| 678 |
clear rational_sqrt_small_bounded. |
| 679 |
abstract ( destruct H; split;[ rewrite -> Zpower_Qpower in *; auto with *; |
| 680 |
replace (Z_of_nat n) with ((S n) + (-1))%Z by (rewrite inj_S; ring); |
| 681 |
rewrite -> Qpower_plus; try discriminate; change (4%positive^(-1)) with (/(4#1)); |
| 682 |
rewrite -> Qinv_mult_distr; change ( / / (4#1)) with (4#1); rewrite -> Qmult_comm |
| 683 |
|replace RHS with ((4#1)*1) by constructor]; |
| 684 |
(apply: mult_resp_leEq_lft;simpl;[assumption|discriminate])). |
| 685 |
clear rational_sqrt_small_bounded. |
| 686 |
refine (@rational_sqrt_mid a _). |
| 687 |
abstract (destruct H; tauto). |
| 688 |
Defined. |
| 689 |
|
| 690 |
Lemma rational_sqrt_small_bounded_correct_aux (a:Q) X4a Xa : |
| 691 |
((scale (1 # 2)) (IRasCR (sqrt (inj_Q IR ((4#1) * a)%Q) X4a)) == IRasCR (sqrt (inj_Q IR a) Xa))%CR. |
| 692 |
Proof. |
| 693 |
rewrite <- CRmult_scale. |
| 694 |
rewrite <- IR_inj_Q_as_CR. |
| 695 |
rewrite <- IR_mult_as_CR. |
| 696 |
apply IRasCR_wd. |
| 697 |
assert (X1:[0][<=](inj_Q IR (1#4))). |
| 698 |
stepl (inj_Q IR 0); [| now (apply (inj_Q_nring IR 0))]. |
| 699 |
apply inj_Q_leEq. |
| 700 |
discriminate. |
| 701 |
csetoid_replace (inj_Q IR (1#2)) (sqrt _ X1). |
| 702 |
assert (X2:[0][<=](inj_Q IR (1#4)[*]inj_Q IR (4%positive*a))). |
| 703 |
apply mult_resp_nonneg;assumption. |
| 704 |
astepl (sqrt _ X2). |
| 705 |
apply sqrt_wd. |
| 706 |
csetoid_rewrite_rev (inj_Q_mult IR (1#4) (4%positive*a)). |
| 707 |
apply inj_Q_wd. |
| 708 |
simpl. |
| 709 |
field; discriminate. |
| 710 |
change (inj_Q IR (1#4)) with (inj_Q IR ((1#2)[*](1#2))). |
| 711 |
assert (X2:[0][<=](inj_Q IR (1#2))[^]2). |
| 712 |
apply sqr_nonneg. |
| 713 |
stepr (sqrt _ X2). |
| 714 |
apply eq_symmetric; apply sqrt_to_nonneg. |
| 715 |
stepl (inj_Q IR 0); [| now (apply (inj_Q_nring IR 0))]. |
| 716 |
apply inj_Q_leEq. |
| 717 |
discriminate. |
| 718 |
apply sqrt_wd. |
| 719 |
rstepl ((inj_Q IR (1#2))[*](inj_Q IR (1#2))). |
| 720 |
apply eq_symmetric. |
| 721 |
apply (inj_Q_mult IR). |
| 722 |
Qed. |
| 723 |
|
| 724 |
Lemma rational_sqrt_small_bounded_correct : forall n a Ha H, |
| 725 |
(@rational_sqrt_small_bounded n a Ha == IRasCR (sqrt (inj_Q IR a) H))%CR. |
| 726 |
Proof. |
| 727 |
induction n; try apply rational_sqrt_mid_correct. |
| 728 |
intros a Ha H. |
| 729 |
simpl. |
| 730 |
destruct (Qle_total a 1); [| apply rational_sqrt_mid_correct]. |
| 731 |
change (scale (1#2) (rational_sqrt_small_bounded n (4%positive*a) (rational_sqrt_small_bounded_subproof n a Ha q)) == |
| 732 |
IRasCR (sqrt (inj_Q IR a) H))%CR. |
| 733 |
assert (X:[0][<=]inj_Q IR (4%positive*a)). |
| 734 |
stepr (inj_Q IR (4%positive:Q)[*]inj_Q IR a); [| now apply eq_symmetric; apply (inj_Q_mult IR)]. |
| 735 |
apply mult_resp_nonneg. |
| 736 |
stepl (inj_Q IR 0); [| now (apply (inj_Q_nring IR 0))]. |
| 737 |
apply inj_Q_leEq. |
| 738 |
discriminate. |
| 739 |
assumption. |
| 740 |
set (X0:= (rational_sqrt_small_bounded_subproof n a Ha q)). |
| 741 |
rewrite -> (IHn (4%positive*a) X0 X). |
| 742 |
apply rational_sqrt_small_bounded_correct_aux. |
| 743 |
Qed. |
| 744 |
|
| 745 |
(** And hence it is defined for all postive numbers. *) |
| 746 |
Definition rational_sqrt_pos a (Ha:0<a) : CR. |
| 747 |
Proof. |
| 748 |
destruct (Qle_total 1 a). |
| 749 |
eapply (rational_sqrt_big_bounded _ a). |
| 750 |
split. |
| 751 |
assumption. |
| 752 |
apply (power4bound a). |
| 753 |
eapply (rational_sqrt_small_bounded _ a). |
| 754 |
split. |
| 755 |
apply (power4bound' a). |
| 756 |
assumption. |
| 757 |
abstract (apply Qle_trans with 1;[assumption|discriminate]). |
| 758 |
Defined. |
| 759 |
|
| 760 |
Lemma rational_sqrt_pos_correct : forall a Ha H, |
| 761 |
(@rational_sqrt_pos a Ha == IRasCR (sqrt (inj_Q IR a) H))%CR. |
| 762 |
Proof. |
| 763 |
intros a Ha H. |
| 764 |
unfold rational_sqrt_pos. |
| 765 |
destruct (Qle_total 1 a). |
| 766 |
apply rational_sqrt_big_bounded_correct. |
| 767 |
apply rational_sqrt_small_bounded_correct. |
| 768 |
Qed. |
| 769 |
|
| 770 |
(** We define the square root for all nonpositive numbers. *) |
| 771 |
Definition rational_sqrt a : CR := |
| 772 |
match (Qlt_le_dec_fast 0 a) with |
| 773 |
|left H => rational_sqrt_pos a H |
| 774 |
|right _ => 0%CR |
| 775 |
end. |
| 776 |
|
| 777 |
Lemma rational_sqrt_correct : forall a H, |
| 778 |
(@rational_sqrt a == IRasCR (sqrt (inj_Q IR a) H))%CR. |
| 779 |
Proof. |
| 780 |
intros a H. |
| 781 |
unfold rational_sqrt. |
| 782 |
destruct (Qlt_le_dec_fast 0 a). |
| 783 |
apply rational_sqrt_pos_correct. |
| 784 |
rewrite <- (IR_nring_as_CR 0). |
| 785 |
apply IRasCR_wd. |
| 786 |
simpl. |
| 787 |
assert (X:[0] [<=] ([0][^]2:IR)). |
| 788 |
rstepr ([0]:IR). |
| 789 |
apply leEq_reflexive. |
| 790 |
stepl (sqrt _ X). |
| 791 |
apply sqrt_wd. |
| 792 |
rstepl ([0]:IR). |
| 793 |
apply leEq_imp_eq. |
| 794 |
assumption. |
| 795 |
stepr (inj_Q IR 0); [| now apply (inj_Q_nring IR 0)]. |
| 796 |
apply inj_Q_leEq. |
| 797 |
assumption. |
| 798 |
apply sqrt_to_nonneg. |
| 799 |
apply leEq_reflexive. |
| 800 |
Qed. |
| 801 |
|
| 802 |
(** Square root is uniformly continuous everywhere. *) |
| 803 |
Definition sqrt_modulus (e:Qpos) : QposInf := Qpos2QposInf (e*e). |
| 804 |
|
| 805 |
Lemma sqrt_uc_prf : @is_UniformlyContinuousFunction |
| 806 |
Q_as_MetricSpace CR rational_sqrt sqrt_modulus. |
| 807 |
Proof. |
| 808 |
intros e a. |
| 809 |
cut (forall a b, (0 <= a) -> (0 <= b) -> ball_ex (X:=Q_as_MetricSpace) (sqrt_modulus e) a b |
| 810 |
-> ball (m:=CR) (proj1_sig e) (rational_sqrt a) (rational_sqrt b)). |
| 811 |
intros X b Hab. |
| 812 |
destruct (Qle_total 0 a) as [Ha|Ha]. |
| 813 |
destruct (Qle_total 0 b) as [Hb|Hb]. |
| 814 |
apply X; assumption. |
| 815 |
unfold rational_sqrt at 2. |
| 816 |
destruct (Qlt_le_dec_fast 0 b) as [Z|_]. |
| 817 |
elim (Qle_not_lt _ _ Hb Z). |
| 818 |
change 0%CR with (rational_sqrt 0). |
| 819 |
apply X; try assumption. |
| 820 |
apply Qle_refl. |
| 821 |
destruct Hab. |
| 822 |
split; simpl in *. |
| 823 |
rewrite -> Qle_minus_iff in *. |
| 824 |
replace RHS with ((a + - 0) + proj1_sig (e*e)%Qpos) by simpl; ring. |
| 825 |
Qauto_nonneg. |
| 826 |
rewrite -> Qle_minus_iff in *. |
| 827 |
replace RHS with (proj1_sig (e*e)%Qpos + - (a - b) + (0 + - b)) by simpl; ring. |
| 828 |
Qauto_nonneg. |
| 829 |
unfold rational_sqrt at 1. |
| 830 |
destruct (Qlt_le_dec_fast 0 a) as [Z0|_]. |
| 831 |
elim (Qle_not_lt _ _ Ha Z0). |
| 832 |
change 0%CR with (rational_sqrt 0). |
| 833 |
destruct (Qle_total 0 b) as [Hb|Hb]. |
| 834 |
apply X; try assumption. |
| 835 |
apply Qle_refl. |
| 836 |
destruct Hab. |
| 837 |
split; simpl in *. |
| 838 |
rewrite -> Qle_minus_iff in *. |
| 839 |
replace RHS with ((a - b) + - - proj1_sig (e*e)%Qpos + (0 + - a)) by simpl; ring. |
| 840 |
Qauto_nonneg. |
| 841 |
rewrite -> Qle_minus_iff in *. |
| 842 |
replace RHS with (proj1_sig (e*e)%Qpos + (b + - 0)) by simpl; ring. |
| 843 |
Qauto_nonneg. |
| 844 |
unfold rational_sqrt at 2. |
| 845 |
destruct (Qlt_le_dec_fast 0 b) as [Z0|_]. |
| 846 |
elim (Qle_not_lt _ _ Hb Z0). |
| 847 |
change 0%CR with (rational_sqrt 0). |
| 848 |
apply ball_refl. apply Qpos_nonneg. |
| 849 |
clear a. |
| 850 |
intros a b Ha Hb Hab. |
| 851 |
assert (Z:[0][<=]inj_Q IR a). |
| 852 |
stepl (inj_Q IR 0); [| now apply (inj_Q_nring IR 0)]. |
| 853 |
apply inj_Q_leEq. |
| 854 |
assumption. |
| 855 |
rewrite -> (rational_sqrt_correct _ Z). |
| 856 |
assert (Z0:[0][<=]inj_Q IR b). |
| 857 |
stepl (inj_Q IR 0); [| now apply (inj_Q_nring IR 0)]. |
| 858 |
apply inj_Q_leEq. |
| 859 |
assumption. |
| 860 |
rewrite -> (rational_sqrt_correct _ Z0). |
| 861 |
rewrite <- CRAbsSmall_ball. |
| 862 |
cut (AbsSmall (R:=CRasCOrdField) (IRasCR (inj_Q IR (proj1_sig e)))%CR |
| 863 |
(IRasCR (sqrt (inj_Q IR a) Z[-](sqrt (inj_Q IR b) Z0)))). |
| 864 |
intros [A B]. |
| 865 |
unfold cg_minus. |
| 866 |
split; (simpl; rewrite <- (IR_inj_Q_as_CR (proj1_sig e)); rewrite <- (IR_opp_as_CR (sqrt _ Z0)); |
| 867 |
rewrite <- (IR_plus_as_CR); assumption). |
| 868 |
rewrite <- IR_AbsSmall_as_CR. |
| 869 |
assert (Z1:AbsSmall (inj_Q IR (proj1_sig e*proj1_sig e)) ((inj_Q IR a)[-](inj_Q IR b))). |
| 870 |
destruct Hab. |
| 871 |
split. |
| 872 |
stepl (inj_Q IR (-(proj1_sig e*proj1_sig e))); [| now apply (inj_Q_inv IR)]. |
| 873 |
stepr (inj_Q IR (a - b)); [| now apply (inj_Q_minus IR)]. |
| 874 |
apply inj_Q_leEq. |
| 875 |
assumption. |
| 876 |
stepl (inj_Q IR (a - b)); [| now apply (inj_Q_minus IR)]. |
| 877 |
apply inj_Q_leEq. |
| 878 |
assumption. |
| 879 |
clear Hab. |
| 880 |
set (e':=(inj_Q IR (proj1_sig e))). |
| 881 |
set (a':=(sqrt (inj_Q IR a) Z)). |
| 882 |
set (b':=(sqrt (inj_Q IR b) Z0)). |
| 883 |
assert (He:[0][<]e'). |
| 884 |
stepl (inj_Q IR 0); [| now apply (inj_Q_nring IR 0)]. |
| 885 |
apply inj_Q_less. |
| 886 |
simpl; auto with *. |
| 887 |
split. |
| 888 |
refine (mult_cancel_leEq _ _ _ (e'[+]a'[+]b') _ _). |
| 889 |
rstepl ([0][+][0][+][0]:IR). |
| 890 |
do 2 (apply plus_resp_less_leEq; try apply sqrt_nonneg). |
| 891 |
assumption. |
| 892 |
rstepl (([--](e'[*]e'))[+](e')[*]([--]a'[-]b')). |
| 893 |
rstepr ((a'[^]2[-]b'[^]2)[+](e')[*](a'[-]b')). |
| 894 |
apply plus_resp_leEq_both. |
| 895 |
stepr (inj_Q IR a[-]inj_Q IR b). |
| 896 |
stepl ([--](inj_Q IR (proj1_sig e*proj1_sig e))). |
| 897 |
destruct Z1; assumption. |
| 898 |
unfold e'. |
| 899 |
csetoid_rewrite_rev (inj_Q_mult IR (proj1_sig e) (proj1_sig e)). |
| 900 |
apply eq_reflexive. |
| 901 |
unfold a', b'. |
| 902 |
unfold cg_minus. |
| 903 |
csetoid_rewrite (sqrt_sqr (inj_Q IR a) Z). |
| 904 |
csetoid_rewrite (sqrt_sqr (inj_Q IR b) Z0). |
| 905 |
apply eq_reflexive. |
| 906 |
apply mult_resp_leEq_lft;[|apply less_leEq;assumption]. |
| 907 |
apply minus_resp_leEq. |
| 908 |
apply shift_leEq_rht. |
| 909 |
rstepr (Two[*]a'). |
| 910 |
apply mult_resp_nonneg. |
| 911 |
apply less_leEq; apply pos_two. |
| 912 |
apply sqrt_nonneg. |
| 913 |
refine (mult_cancel_leEq _ _ _ (e'[+]a'[+]b') _ _). |
| 914 |
rstepl ([0][+][0][+][0]:IR). |
| 915 |
do 2 (apply plus_resp_less_leEq; try apply sqrt_nonneg). |
| 916 |
assumption. |
| 917 |
rstepr (((e'[*]e'))[+](e')[*](a'[+]b')). |
| 918 |
rstepl ((a'[^]2[-]b'[^]2)[+](e')[*](a'[-]b')). |
| 919 |
apply plus_resp_leEq_both. |
| 920 |
stepl (inj_Q IR a[-]inj_Q IR b). |
| 921 |
stepr (inj_Q IR (proj1_sig e*proj1_sig e)). |
| 922 |
destruct Z1; assumption. |
| 923 |
unfold e'. |
| 924 |
csetoid_rewrite_rev (inj_Q_mult IR (proj1_sig e) (proj1_sig e)). |
| 925 |
apply eq_reflexive. |
| 926 |
unfold a', b'. |
| 927 |
unfold cg_minus. |
| 928 |
csetoid_rewrite (sqrt_sqr (inj_Q IR a) Z). |
| 929 |
csetoid_rewrite (sqrt_sqr (inj_Q IR b) Z0). |
| 930 |
apply eq_reflexive. |
| 931 |
apply mult_resp_leEq_lft;[|apply less_leEq;assumption]. |
| 932 |
unfold cg_minus. |
| 933 |
apply plus_resp_leEq_lft. |
| 934 |
apply shift_leEq_rht. |
| 935 |
rstepr (Two[*]b'). |
| 936 |
apply mult_resp_nonneg. |
| 937 |
apply less_leEq; apply pos_two. |
| 938 |
apply sqrt_nonneg. |
| 939 |
Qed. |
| 940 |
|
| 941 |
Local Open Scope uc_scope. |
| 942 |
|
| 943 |
Definition sqrt_uc : Q_as_MetricSpace --> CR := |
| 944 |
Build_UniformlyContinuousFunction sqrt_uc_prf. |
| 945 |
|
| 946 |
Definition CRsqrt : CR --> CR := Cbind QPrelengthSpace sqrt_uc. |
| 947 |
|
| 948 |
Lemma CRsqrt_correct : forall x H, |
| 949 |
(IRasCR (sqrt x H) == CRsqrt (IRasCR x))%CR. |
| 950 |
Proof. |
| 951 |
intros x H. |
| 952 |
assert (X:Dom (FNRoot FId 2 (Nat.lt_0_succ 1)) x). |
| 953 |
simpl; split; auto. |
| 954 |
transitivity (IRasCR (FNRoot FId 2 (Nat.lt_0_succ 1) x X)). |
| 955 |
apply IRasCR_wd. |
| 956 |
apply: NRoot_wd. |
| 957 |
apply eq_reflexive. |
| 958 |
apply (ContinuousCorrect (I:proper (closel [0]))); try assumption. |
| 959 |
apply Continuous_NRoot. |
| 960 |
Contin. |
| 961 |
intros; assumption. |
| 962 |
intros q Hq Y. |
| 963 |
transitivity (rational_sqrt q);[|apply: rational_sqrt_correct]. |
| 964 |
unfold CRsqrt. |
| 965 |
pose proof (Cbind_correct QPrelengthSpace sqrt_uc). |
| 966 |
apply ucEq_equiv in H0. |
| 967 |
rewrite (H0 ('q)%CR). |
| 968 |
apply BindLaw1. |
| 969 |
Qed. |
| 970 |
(* begin hide *) |
| 971 |
#[global] |
| 972 |
Hint Rewrite CRsqrt_correct : IRtoCR. |
| 973 |
(* end hide *) |
| 974 |
|
| 975 |
Lemma CRsqrt_sqr : forall (x : CR), |
| 976 |
(0 <= x -> CRsqrt x * CRsqrt x = x)%CR. |
| 977 |
Proof. |
| 978 |
intros x xpos. |
| 979 |
rewrite <- (CRasIRasCR_id x). |
| 980 |
assert ([0] [<=] CRasIR x). |
| 981 |
{ apply IR_leEq_as_CR. |
| 982 |
rewrite CRasIRasCR_id, IR_Zero_as_CR. |
| 983 |
exact xpos. } |
| 984 |
rewrite <- (CRsqrt_correct (CRasIR x) H). |
| 985 |
rewrite <- IR_mult_as_CR. |
| 986 |
apply IRasCR_wd. |
| 987 |
setoid_replace (sqrt (CRasIR x) H [*] sqrt (CRasIR x) H) |
| 988 |
with (sqrt (CRasIR x) H [^] 2). |
| 989 |
exact (sqrt_sqr (CRasIR x) H). |
| 990 |
simpl. |
| 991 |
destruct (cr_proof IR), ax_mult_mon. |
| 992 |
rewrite lunit. reflexivity. |
| 993 |
Qed. |
| 994 |
|
| 995 |
Lemma CRsquare_nonneg_cancel : forall x y : CR, |
| 996 |
(0 <= x)%CR -> (0 <= y)%CR -> msp_eq (x*x)%CR (y*y)%CR -> msp_eq x y. |
| 997 |
Proof. |
| 998 |
intros. |
| 999 |
assert (msp_eq ((x-y)*(x+y))%CR 0%CR). |
| 1000 |
{ rewrite (CRplus_eq_l (y*y)%CR). |
| 1001 |
ring_simplify. exact H1. } |
| 1002 |
apply ball_stable. |
| 1003 |
intro abs. |
| 1004 |
apply CRmult_eq_0_reg_l in H2. |
| 1005 |
contradict abs. |
| 1006 |
rewrite (CRplus_eq_l (-y)%CR x y). |
| 1007 |
rewrite CRplus_opp. |
| 1008 |
exact H2. |
| 1009 |
intro H3. |
| 1010 |
assert (msp_eq x 0%CR). |
| 1011 |
{ apply CRle_antisym. split. |
| 1012 |
2: exact H. |
| 1013 |
rewrite <- CRplus_0_r. |
| 1014 |
apply (@CRle_trans _ (x+y)%CR). |
| 1015 |
apply CRplus_le_l. exact H0. |
| 1016 |
rewrite H3. apply CRle_refl. } |
| 1017 |
rewrite H4, CRplus_0_l in H3. |
| 1018 |
contradict abs. |
| 1019 |
rewrite H3, H4. reflexivity. |
| 1020 |
Qed. |
| 1021 |
|
| 1022 |
Lemma root_loop_nonneg : forall (n:nat) q (e:Qpos) (b:Q) (err:positive), |
| 1023 |
0 <= b -> 0 <= q -> 0 <= root_loop q e n b err. |
| 1024 |
Proof. |
| 1025 |
induction n. |
| 1026 |
- intros. exact H. |
| 1027 |
- intros. simpl. |
| 1028 |
destruct (Qlt_le_dec_fast (`e) (1#err)). |
| 1029 |
2: exact H. |
| 1030 |
apply IHn. 2: exact H0. |
| 1031 |
destruct b as [b a]. |
| 1032 |
unfold Qle in H; simpl in H. rewrite Z.mul_1_r in H. |
| 1033 |
destruct q as [q c]. |
| 1034 |
unfold Qle in H0; simpl in H0. rewrite Z.mul_1_r in H0. |
| 1035 |
unfold Qle, Qnum, Qden. |
| 1036 |
rewrite Z.mul_0_l, Z.mul_1_r. |
| 1037 |
rewrite Z.mul_1_r. |
| 1038 |
apply Z_div_pos. reflexivity. |
| 1039 |
apply Z.mul_nonneg_nonneg. |
| 1040 |
2: discriminate. |
| 1041 |
apply Z.add_nonneg_nonneg. |
| 1042 |
apply Z.mul_nonneg_nonneg. apply H. |
| 1043 |
discriminate. |
| 1044 |
apply Z.mul_nonneg_nonneg. |
| 1045 |
apply Z.mul_nonneg_nonneg. exact H0. |
| 1046 |
2: discriminate. |
| 1047 |
unfold Qinv, Qmult. simpl. |
| 1048 |
destruct b. discriminate. |
| 1049 |
discriminate. exfalso. |
| 1050 |
apply (Zle_not_lt _ _ H). reflexivity. |
| 1051 |
Qed. |
| 1052 |
|
| 1053 |
Lemma sqrt_raw_nonneg : |
| 1054 |
forall a e, 0 <= a -> 0 <= sqrt_raw a e. |
| 1055 |
Proof. |
| 1056 |
intros. destruct e. 2: discriminate. |
| 1057 |
simpl. destruct (Qlt_le_dec_fast (`q) (1#2)). |
| 1058 |
apply root_loop_nonneg. |
| 1059 |
rewrite Z.mul_1_r, Z.mul_1_r. |
| 1060 |
destruct a as [a b]; simpl. |
| 1061 |
destruct a. |
| 1062 |
- simpl. unfold Qle; simpl. |
| 1063 |
rewrite Z.mul_1_r. |
| 1064 |
apply Z.div_pos. discriminate. |
| 1065 |
reflexivity. |
| 1066 |
- simpl. |
| 1067 |
unfold Qle, Qnum, Qden. |
| 1068 |
rewrite Z.mul_0_l, Z.mul_1_r. |
| 1069 |
apply Z.div_pos. 2: reflexivity. |
| 1070 |
discriminate. |
| 1071 |
- exfalso. |
| 1072 |
unfold Qle in H; simpl in H. |
| 1073 |
apply (Zle_not_lt _ _ H). reflexivity. |
| 1074 |
- exact H. |
| 1075 |
- unfold initial_root. |
| 1076 |
apply Qmult_le_0_compat. discriminate. |
| 1077 |
apply (Qle_trans _ (0+1)). |
| 1078 |
discriminate. apply Qplus_le_l, H. |
| 1079 |
Qed. |
| 1080 |
|
| 1081 |
Lemma rational_sqrt_big_bounded_nonneg : forall n (a:Q) Ha e, |
| 1082 |
0 <= approximate (rational_sqrt_big_bounded n a Ha) e. |
| 1083 |
Proof. |
| 1084 |
induction n. |
| 1085 |
- intros. discriminate. |
| 1086 |
- intros. simpl. |
| 1087 |
destruct (Qle_total a (4#1)). |
| 1088 |
+ simpl. apply (sqrt_raw_nonneg a e). |
| 1089 |
destruct Ha. apply (Qle_trans _ 1). |
| 1090 |
discriminate. exact H. |
| 1091 |
+ unfold Cmap_fun; simpl. |
| 1092 |
rewrite <- (Qmult_0_r (2#1)). |
| 1093 |
apply Qmult_le_l. reflexivity. |
| 1094 |
apply IHn. |
| 1095 |
Qed. |
| 1096 |
|
| 1097 |
Lemma rational_sqrt_small_bounded_nonneg |
| 1098 |
: forall (n:nat) a (Ha: / (4^n)%Z <= a <= (4#1)) e, |
| 1099 |
0 <= approximate (rational_sqrt_small_bounded n a Ha) e. |
| 1100 |
Proof. |
| 1101 |
induction n. |
| 1102 |
- intros. simpl. |
| 1103 |
apply sqrt_raw_nonneg. destruct Ha. |
| 1104 |
unfold Qinv in H. simpl in H. |
| 1105 |
apply (Qle_trans _ 1). |
| 1106 |
discriminate. exact H. |
| 1107 |
- intros. simpl. |
| 1108 |
destruct (Qle_total a 1). simpl. |
| 1109 |
apply Qmult_le_0_compat. discriminate. |
| 1110 |
apply IHn. simpl. apply sqrt_raw_nonneg. |
| 1111 |
apply (Qle_trans _ 1). |
| 1112 |
discriminate. exact q. |
| 1113 |
Qed. |
| 1114 |
|
| 1115 |
Lemma rational_sqrt_nonneg : forall (q : Q) (e : Qpos), |
| 1116 |
0 <= approximate (rational_sqrt q) e. |
| 1117 |
Proof. |
| 1118 |
intros. |
| 1119 |
unfold rational_sqrt. |
| 1120 |
destruct (Qlt_le_dec_fast 0 q). |
| 1121 |
2: apply Qle_refl. |
| 1122 |
unfold rational_sqrt_pos. |
| 1123 |
destruct (Qle_total 1 q). |
| 1124 |
apply rational_sqrt_big_bounded_nonneg. |
| 1125 |
apply rational_sqrt_small_bounded_nonneg. |
| 1126 |
Qed. |
| 1127 |
|
| 1128 |
Lemma CRsqrt_pos : forall x : CR, (0 <= x -> 0 <= CRsqrt x)%CR. |
| 1129 |
Proof. |
| 1130 |
(* This cannot be proved algebraically, because there is also |
| 1131 |
a negative solution y to the equation y^2 = x. *) |
| 1132 |
intros x H e1. simpl. |
| 1133 |
unfold Cap_raw; simpl. |
| 1134 |
unfold Cjoin_raw; simpl. |
| 1135 |
rewrite Qplus_0_r. |
| 1136 |
apply (Qle_trans _ 0). |
| 1137 |
apply (Qopp_le_compat 0 (`e1)). |
| 1138 |
apply Qpos_nonneg. |
| 1139 |
apply rational_sqrt_nonneg. |
| 1140 |
Qed. |
| 1141 |
|
| 1142 |
Lemma CRsqrt_mult : forall x y, |
| 1143 |
(0 <= x -> 0 <= y -> CRsqrt (x*y) = CRsqrt x * CRsqrt y)%CR. |
| 1144 |
Proof. |
| 1145 |
intros x y xpos ypos. |
| 1146 |
apply (CRsquare_nonneg_cancel |
| 1147 |
(CRsqrt (x*y)%CR) (CRsqrt x * CRsqrt y)%CR |
| 1148 |
(CRsqrt_pos _ (CRmult_le_0_compat _ _ xpos ypos))). |
| 1149 |
apply CRmult_le_0_compat; apply CRsqrt_pos; assumption. |
| 1150 |
rewrite CRsqrt_sqr. |
| 1151 |
2: exact (CRmult_le_0_compat _ _ xpos ypos). |
| 1152 |
transitivity (CRsqrt x * CRsqrt x * (CRsqrt y * CRsqrt y))%CR. |
| 1153 |
2: ring. |
| 1154 |
rewrite CRsqrt_sqr, CRsqrt_sqr. |
| 1155 |
reflexivity. exact ypos. exact xpos. |
| 1156 |
Qed. |
| 1157 |
|
| 1158 |
Lemma CRsqrt_inc : |
| 1159 |
forall x y : CR, (0 <= x -> x <= y -> CRsqrt x <= CRsqrt y)%CR. |
| 1160 |
Proof. |
| 1161 |
(* Prove that 0 <= ARsqrt y - ARsqrt x, |
| 1162 |
ie that 0 <= (ARsqrt y - ARsqrt x) * (ARsqrt y + ARsqrt x) *) |
| 1163 |
intros. |
| 1164 |
apply (CRplus_le_r _ _ (-CRsqrt x)%CR). |
| 1165 |
rewrite CRplus_opp. |
| 1166 |
apply CRle_not_lt. |
| 1167 |
intro abs. |
| 1168 |
assert ((0 < y)%CR -> False). |
| 1169 |
{ intro ypos. |
| 1170 |
revert abs. |
| 1171 |
apply CRle_not_lt. |
| 1172 |
apply (CRmult_le_0_reg_l (CRsqrt x + CRsqrt y)%CR). |
| 1173 |
- intro abs. |
| 1174 |
apply CRle_not_lt in abs. |
| 1175 |
assert (msp_eq 0%CR (CRsqrt y)). |
| 1176 |
apply CRle_antisym. split. |
| 1177 |
apply CRsqrt_pos. |
| 1178 |
apply CRlt_le_weak, ypos. |
| 1179 |
rewrite <- CRplus_0_l. |
| 1180 |
refine (CRle_trans _ abs). |
| 1181 |
apply CRplus_le_r, CRsqrt_pos, H. |
| 1182 |
pose proof (CRmult_wd H1 H1) as H3. |
| 1183 |
rewrite CRmult_0_r, CRsqrt_sqr in H3. |
| 1184 |
apply CRle_antisym in H3. |
| 1185 |
revert ypos. apply CRle_not_lt, H3. |
| 1186 |
apply CRlt_le_weak, ypos. |
| 1187 |
- setoid_replace ((CRsqrt x + CRsqrt y) * (CRsqrt y + (- CRsqrt x)))%CR |
| 1188 |
with (CRsqrt y*CRsqrt y - (CRsqrt x*CRsqrt x))%CR by ring. |
| 1189 |
rewrite (CRsqrt_sqr y). |
| 1190 |
rewrite (CRsqrt_sqr x). |
| 1191 |
rewrite <- (CRplus_opp x). |
| 1192 |
apply CRplus_le_r, H0. |
| 1193 |
exact H. exact (CRle_trans H H0). } |
| 1194 |
apply CRle_not_lt in H1. |
| 1195 |
revert abs. apply CRle_not_lt. |
| 1196 |
setoid_replace x with 0%CR. |
| 1197 |
setoid_replace y with 0%CR. |
| 1198 |
rewrite CRplus_opp. apply CRle_refl. |
| 1199 |
apply CRle_antisym. split. |
| 1200 |
exact H1. exact (CRle_trans H H0). |
| 1201 |
apply CRle_antisym. split. |
| 1202 |
exact (CRle_trans H0 H1). exact H. |
| 1203 |
Qed. |
| 1204 |
|
| 1205 |
Lemma CRsqrt_Qsqrt : forall x : Q, (CRsqrt ('x) == rational_sqrt x)%CR. |
| 1206 |
Proof. |
| 1207 |
intros x. |
| 1208 |
unfold CRsqrt. |
| 1209 |
pose proof (Cbind_correct QPrelengthSpace sqrt_uc). |
| 1210 |
apply ucEq_equiv in H. |
| 1211 |
rewrite (H ('x)%CR). |
| 1212 |
apply BindLaw1. |
| 1213 |
Qed. |
| 1214 |
|
| 1215 |
#[global] |
| 1216 |
Instance: Proper ((=) ==> (=)) rational_sqrt. |
| 1217 |
Proof. |
| 1218 |
intros x1 x2 E. |
| 1219 |
rewrite <-2!CRsqrt_Qsqrt. |
| 1220 |
now rewrite E. |
| 1221 |
Qed. |
| 1222 |
|
| 1223 |
Lemma rational_sqrt_nonpos (a : Q) : |
| 1224 |
a ≤ 0 → rational_sqrt a = 0%CR. |
| 1225 |
Proof. |
| 1226 |
intros. unfold rational_sqrt. |
| 1227 |
case Qlt_le_dec_fast; intros; [|reflexivity]. |
| 1228 |
edestruct Qle_not_lt; eassumption. |
| 1229 |
Qed. |
| 1230 |
|
| 1231 |
Lemma rational_sqrt_unique (a : Q) (y : CR) : |
| 1232 |
0 ≤ a → CRpower_N y 2 = 'a → 0%CR ≤ y → y = rational_sqrt a. |
| 1233 |
Proof. |
| 1234 |
intros. |
| 1235 |
assert (Pa : [0][<=](inj_Q IR a)). |
| 1236 |
stepl (inj_Q IR 0); [| now (apply (inj_Q_nring IR 0))]. |
| 1237 |
now apply inj_Q_leEq. |
| 1238 |
rewrite (rational_sqrt_correct _ Pa). |
| 1239 |
now apply rational_sqrt_mid_correct_aux. |
| 1240 |
Qed. |
| 1241 |
|
| 1242 |
Lemma rational_sqrt_scale (n : Z) a : |
| 1243 |
0 ≤ a → scale ((2#1) ^ n) (rational_sqrt (a * (4#1) ^ (-n))) = rational_sqrt a. |
| 1244 |
Proof. |
| 1245 |
intros E. |
| 1246 |
rewrite <-CRmult_scale. |
| 1247 |
revert n. apply biinduction. |
| 1248 |
solve_proper. |
| 1249 |
simpl. rewrite Qmult_1_r. |
| 1250 |
now ring_simplify. |
| 1251 |
intros n. |
| 1252 |
setoid_replace ('((2#1) ^ (1 + n)) * rational_sqrt (a * (4#1) ^ -(1 + n)))%CR |
| 1253 |
with ('((2#1) ^ n) * scale (2#1) (rational_sqrt ((a * (4#1) ^ -n) / (4#1))))%CR. |
| 1254 |
assert (Pa1 : [0][<=](inj_Q IR (a * (4#1) ^ (- n)))). |
| 1255 |
stepl (inj_Q IR 0); [| now (apply (inj_Q_nring IR 0))]. |
| 1256 |
apply inj_Q_leEq. |
| 1257 |
apply Qmult_le_0_compat; [assumption|]. |
| 1258 |
now apply Qpower_pos. |
| 1259 |
assert (Pa2 : [0][<=](inj_Q IR (a * (4#1) ^ (- n) / (4 # 1)))). |
| 1260 |
stepl (inj_Q IR 0); [| now (apply (inj_Q_nring IR 0))]. |
| 1261 |
apply inj_Q_leEq. |
| 1262 |
apply Qmult_le_0_compat; [|easy]. |
| 1263 |
apply Qmult_le_0_compat; [assumption|]. |
| 1264 |
now apply Qpower_pos. |
| 1265 |
rewrite (rational_sqrt_correct _ Pa1), (rational_sqrt_correct _ Pa2). |
| 1266 |
split; intros E2; rewrite <-E2; now rewrite rational_sqrt_big_bounded_correct_aux. |
| 1267 |
rewrite Zopp_plus_distr. |
| 1268 |
rewrite <-CRmult_scale. |
| 1269 |
rewrite 2!Qpower_plus by discriminate. |
| 1270 |
simpl. |
| 1271 |
rewrite (Qmult_comm (2#1) ((2#1) ^ n)), <-CRmult_Qmult. |
| 1272 |
rewrite (Qmult_comm (/(4#1))), Qmult_assoc. |
| 1273 |
symmetry. apply associativity. |
| 1274 |
Qed. |