Debian Codegraph @

reals/fast/CRroot.v

raw
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.