| 1 |
Require Import |
| 2 |
MathClasses.interfaces.abstract_algebra |
| 3 |
MathClasses.theory.nat_pow |
| 4 |
MathClasses.theory.int_pow |
| 5 |
CoRN.algebra.RSetoid |
| 6 |
CoRN.stdlib_omissions.Q |
| 7 |
CoRN.metric2.Metric |
| 8 |
CoRN.metric2.UniformContinuity |
| 9 |
CoRN.reals.fast.CRarctan_small |
| 10 |
CoRN.reals.fast.CRarctan |
| 11 |
CoRN.reals.fast.CRstreams |
| 12 |
CoRN.reals.fast.CRAlternatingSum |
| 13 |
CoRN.reals.faster.ARAlternatingSum |
| 14 |
CoRN.reals.faster.ARsin. |
| 15 |
Require Export |
| 16 |
CoRN.reals.faster.ARArith. |
| 17 |
|
| 18 |
Section ARarctan_small. |
| 19 |
Context `{AppRationals AQ} |
| 20 |
{num den : AQ} (Pnd : -den < num < den) (dpos : 0 < den). |
| 21 |
|
| 22 |
(* |
| 23 |
Split the stream |
| 24 |
(-1)^i a^(2i+1) / (2i+1) |
| 25 |
up into the streams |
| 26 |
(-1)^i a^(2i+1) and (2i+1) |
| 27 |
because we do not have exact division |
| 28 |
*) |
| 29 |
Definition ARarctanStream (px : positive*(AQ*AQ)) : AQ*AQ |
| 30 |
:= (- fst (snd px) * num * num * ZtoAQ (Zpos (Pos.pred (fst px)~0)), |
| 31 |
snd (snd px) * den * den * ZtoAQ (Zpos (fst px)~1)). |
| 32 |
|
| 33 |
Lemma arctanStream_pos : ∀ x : positive * (AQ * AQ), |
| 34 |
0 < snd (snd x) → 0 < snd (ARarctanStream x). |
| 35 |
Proof. |
| 36 |
assert (0 = ZtoAQ 0) as zero_int. |
| 37 |
{ destruct H4. destruct aq_ints_mor, semiringmor_plus_mor. |
| 38 |
rewrite preserves_mon_unit. reflexivity. } |
| 39 |
intros. destruct x; simpl. |
| 40 |
simpl in H5. |
| 41 |
apply AQmult_lt_0_compat. |
| 42 |
apply AQmult_lt_0_compat. |
| 43 |
apply AQmult_lt_0_compat. |
| 44 |
exact H5. exact dpos. exact dpos. |
| 45 |
rewrite zero_int. |
| 46 |
apply (strictly_order_preserving (cast Z AQ)). |
| 47 |
reflexivity. |
| 48 |
Qed. |
| 49 |
|
| 50 |
Lemma arctanStream_correct : ∀ p : positive, |
| 51 |
Str_pth _ (arctanStream (AQtoQ num / AQtoQ den)) |
| 52 |
p (1%positive, AQtoQ num / AQtoQ den) |
| 53 |
== let (_, r) := iterate _ (fS ARarctanStream) p (1%positive, (num, den)) in |
| 54 |
AQtoQ (fst r) / AQtoQ (snd r). |
| 55 |
Proof. |
| 56 |
assert (forall n:Z, AQtoQ (ZtoAQ n) == (n#1)). |
| 57 |
{ intro n. destruct n as [|n|n]. |
| 58 |
pose proof (rings.preserves_0 (f:=cast Z AQ)). rewrite H5. clear H5. |
| 59 |
rewrite rings.preserves_0. reflexivity. |
| 60 |
apply ZtoQ. change (Z.neg n) with (-Z.pos n)%Z. |
| 61 |
pose proof (rings.preserves_negate (f:=cast Z AQ)). |
| 62 |
rewrite H5. clear H5. rewrite rings.preserves_negate. |
| 63 |
rewrite ZtoQ. reflexivity. } |
| 64 |
apply Pos.peano_ind. |
| 65 |
- unfold Str_pth, iterate, arctanStream, snd. |
| 66 |
rewrite Qred_correct. simpl. |
| 67 |
do 6 rewrite rings.preserves_mult. |
| 68 |
rewrite rings.preserves_negate. |
| 69 |
rewrite H5, H5. |
| 70 |
unfold dec_recip, stdlib_rationals.Q_recip. |
| 71 |
unfold mult, stdlib_rationals.Q_mult. |
| 72 |
unfold negate, stdlib_rationals.Q_opp. |
| 73 |
rewrite Qmult_1_r. |
| 74 |
change (1#3) with (/3)%Q. |
| 75 |
unfold Qdiv. |
| 76 |
do 3 rewrite Qinv_mult_distr. |
| 77 |
do 3 rewrite Qmult_assoc. |
| 78 |
apply Qmult_comp. 2: reflexivity. |
| 79 |
do 2 rewrite Qmult_assoc. |
| 80 |
apply Qmult_comp. 2: reflexivity. |
| 81 |
ring. |
| 82 |
- intros p IHp. unfold Str_pth. unfold Str_pth in IHp. |
| 83 |
rewrite iterate_succ, iterate_succ. |
| 84 |
pose proof (arctanStream_fst (AQtoQ num / AQtoQ den) p) as H7. |
| 85 |
unfold dec_recip, stdlib_rationals.Q_recip. |
| 86 |
unfold dec_recip, stdlib_rationals.Q_recip in IHp. |
| 87 |
unfold mult, stdlib_rationals.Q_mult. |
| 88 |
unfold mult, stdlib_rationals.Q_mult in IHp. |
| 89 |
unfold Qdiv in H7. unfold Qdiv. |
| 90 |
unfold Qdiv in IHp. |
| 91 |
unfold Q_as_MetricSpace, msp_car. |
| 92 |
unfold Q_as_MetricSpace, msp_car in IHp. |
| 93 |
destruct (iterate _ (arctanStream (AQtoQ num * / AQtoQ den)%Q) p |
| 94 |
(1%positive, (AQtoQ num * / AQtoQ den)%Q)). |
| 95 |
simpl in H7. simpl in IHp. subst p0. |
| 96 |
unfold arctanStream, snd, fst. rewrite Qred_correct. |
| 97 |
rewrite IHp. clear IHp. |
| 98 |
pose proof (fS_fst ARarctanStream p (num, den)) as H6. |
| 99 |
destruct (iterate _ (fS ARarctanStream) p (1%positive, (num, den))) as [p0 p1]. |
| 100 |
simpl in H6. subst p0. unfold ARarctanStream, fS. |
| 101 |
simpl (fst (Pos.succ p, p1)). |
| 102 |
simpl (snd (Pos.succ p, p1)). |
| 103 |
replace (Pos.pred (Pos.succ p)~0) with (p~1)%positive. |
| 104 |
do 6 rewrite rings.preserves_mult. |
| 105 |
rewrite rings.preserves_negate. |
| 106 |
unfold mult, stdlib_rationals.Q_mult. |
| 107 |
unfold negate, stdlib_rationals.Q_opp. |
| 108 |
rewrite ZtoQ, ZtoQ. |
| 109 |
do 3 rewrite Qinv_mult_distr. |
| 110 |
setoid_replace (Z.pos p~1 # 2 + p~1)%Q |
| 111 |
with ((Z.pos p~1 # 1) * / (Z.pos (Pos.succ p)~1 # 1))%Q. |
| 112 |
ring. |
| 113 |
unfold Qinv, Qeq, Qmult, Qnum, Qden. |
| 114 |
rewrite Pos.mul_1_l, Z.mul_1_r. |
| 115 |
replace (2 + p~1)%positive with ((Pos.succ p)~1)%positive. |
| 116 |
reflexivity. |
| 117 |
change (p~1)%positive with (2*p+1)%positive. |
| 118 |
change ((Pos.succ p)~1)%positive with (2*Pos.succ p+1)%positive. |
| 119 |
rewrite Pplus_one_succ_l. |
| 120 |
rewrite Pos.mul_add_distr_l. reflexivity. |
| 121 |
rewrite Pplus_one_succ_l. |
| 122 |
change (p~1)%positive with (2*p+1)%positive. |
| 123 |
change ((1+p)~0)%positive with (2*(1+p))%positive. |
| 124 |
rewrite Pos.mul_add_distr_l. |
| 125 |
rewrite Pos.pred_sub. |
| 126 |
rewrite (Pos.add_comm (2*1)). |
| 127 |
rewrite <- Pos.add_sub_assoc. reflexivity. reflexivity. |
| 128 |
Qed. |
| 129 |
|
| 130 |
Lemma AQarctan_small_Qprf : -1 < AQtoQ num / AQtoQ den < 1. |
| 131 |
Proof. |
| 132 |
split. |
| 133 |
- apply Qlt_shift_div_l. |
| 134 |
pose proof (rings.preserves_0 (f:=cast AQ Q)). |
| 135 |
rewrite <- H5. |
| 136 |
apply (strictly_order_preserving (cast AQ Q)), dpos. |
| 137 |
setoid_replace (-1 * AQtoQ den) with (-AQtoQ den) by reflexivity. |
| 138 |
rewrite <- rings.preserves_negate. |
| 139 |
apply (strictly_order_preserving (cast AQ Q)), Pnd. |
| 140 |
- apply Qlt_shift_div_r. |
| 141 |
pose proof (rings.preserves_0 (f:=cast AQ Q)). |
| 142 |
rewrite <- H5. |
| 143 |
apply (strictly_order_preserving (cast AQ Q)), dpos. |
| 144 |
rewrite Qmult_1_l. |
| 145 |
apply (strictly_order_preserving (cast AQ Q)), Pnd. |
| 146 |
Qed. |
| 147 |
|
| 148 |
Definition AQarctan_small : msp_car AR |
| 149 |
:= CRtoAR (inject_Q_CR (AQtoQ num / AQtoQ den)) |
| 150 |
+ AltSeries ARarctanStream arctanStream_pos |
| 151 |
positive (arctanStream (AQtoQ num / AQtoQ den)) |
| 152 |
(num,den) (xH,AQtoQ num / AQtoQ den) arctanStream_correct _ |
| 153 |
(arctanStream_alt (widen_interval AQarctan_small_Qprf)) |
| 154 |
dpos (arctanStream_zl (widen_interval AQarctan_small_Qprf)). |
| 155 |
|
| 156 |
Lemma AQarctan_small_correct : |
| 157 |
'AQarctan_small = rational_arctan_small (widen_interval AQarctan_small_Qprf). |
| 158 |
Proof. |
| 159 |
unfold AQarctan_small, rational_arctan_small. |
| 160 |
rewrite ARtoCR_preserves_plus. |
| 161 |
apply ucFun2_wd. |
| 162 |
pose proof CRAR_id. |
| 163 |
unfold cast. unfold cast in H5. |
| 164 |
rewrite H5. reflexivity. |
| 165 |
apply AltSeries_correct. |
| 166 |
Qed. |
| 167 |
|
| 168 |
End ARarctan_small. |