import ContractExact namespace Submission open ExactRuntime FloatLib.Floats.Formats.BinaryInterchange FloatLib.Floats local notation "Ж"=>FloatArray open USize renaming lt_iff_toNat_lt->β,le_size->ς,toNat_zero->ϝ,size_eq_two_pow->ϡ open Nat renaming and_two_pow_sub_one_eq_mod->γ,mod_eq_of_lt->θ,shiftRight_eq_div_pow->ι,mul_le_mul_right->ψ,shiftLeft_eq->Ζ,pow_le_pow_right->Μ,add_mul_mod_self_right->Ο,div_eq_of_lt->Χ,add_mul_div_right->ό,succ_mul->ώ,toUSize_eq->Ϗ,two_pow_add_eq_or_of_lt->ϗ,add_comm->Ϙ,lt_log2_self->Ϝ,zero_add->ϥ,mul_comm->Ϧ,mod_lt->ϩ,add_sub_cancel_left->ϭ,toUInt64_eq->ϱ,div_lt_of_lt_mul->϶,div_le_div_right->Ϸ,zero_le->ϸ,and_le_right->Ϻ open UInt64 renaming le_iff_toNat_le->κ,lt_iff_toNat_lt->ν,toNat_add->ξ,toNat_shiftRight->ο,toNat_sub_of_le->υ,toNat_inj->χ,toNat_and->Α,toNat_shiftLeft->Η,toNat_ofNat_of_lt'->Θ,toNat_sub->Λ,toNat_zero->ϓ,toNat_toUInt32->Ϡ,toNat_mul->Ϫ open Bool renaming false_eq_true->μ,and_eq_true->Β,eq_iff_iff->Ϥ open Model renaming toModel_ofFloatModel->Ε,isFinite_roundDyadic_of_isIEEE_of_abs_toReal_le_posMaxFinite->Υ,toReal_eq_unpackedToReal_toModel->ϐ,toDyadic?_ofFields_of_isFinite->ϖ,toReal_roundDyadic_eq_roundAt->Ϛ,toDyadic?_isSome_eq_isFinite->Ϟ,abs_signed_mul_bpow_le_toReal_posMaxFinite->Ϣ,ofFloatModel_pack->ϫ,toDyadic?_ieee_eq_model->Ϯ,roundDyadicGeneral_eq_roundDyadic->ϵ local notation "Л"=>true open UInt32 renaming toNat_inj->Ι,toNat_and->Ρ,toNat_shiftRight->ϔ,toNat_toUInt64->ϟ,lt_iff_toNat_lt->ϯ local notation "М"=>false open Finset renaming mem_range->Κ,sum_range_succ->Ξ,sum_congr->Τ,sum_le_sum->ϋ,sum_Ico_succ_top->ϕ,sum_sub_distrib->ϙ,abs_sum_le_sum_abs->ϣ,sum_nonneg->Ϩ,sum_add_distrib->ϰ,card_range->ϴ,sum_mul->Ϲ,sum_le_sum_of_subset_of_nonneg->ϻ local notation "Н"=>rfl open Array renaming getElem_ofFn->Ν,size_replicate->ϧ,size_uset->ϲ local notation "О"=>by simp open Int renaming cast_abs->ϊ,natAbs_mul->Ϭ,abs_eq_natAbs->ϳ local notation "П"=>by ring open Real renaming sqrt_nonneg->ύ local notation "Р"=>by linarith open Float.Model.UnpackedFloat renaming unpackExponent_packComponents->ϑ,unpackMantissa_packComponents->ϒ local notation "С"=>by rfl open FloatLib.Numerics.Dyadic renaming cast_toRat->ϛ local notation "А" =>by omega local notation "Б" =>by decide local notation "В" =>by positivity local notation "Г" =>by norm_num local notation "Д" =>UInt64 local notation "Е" =>UInt32 local postfix:max "а"=>UInt64.toNat local postfix:max "б"=>USize.toNat local postfix:max "в"=>Array.size local postfix:max "г"=>UInt32.toNat local postfix:max "д"=>Nat.toUSize local postfix:max "е"=>FloatArray.size local postfix:max "ж"=>Nat.toUInt64 local postfix:max "з"=>Nat.log2 local postfix:max "и"=>Fin.val local postfix:max "й"=>Int.natAbs local postfix:max "к"=>UInt32.toUInt64 local postfix:max "л"=>Int.toNat local postfix:max "м"=>UInt64.toUInt32 local postfix:max "н"=>Int64.toInt local postfix:max "о"=>UInt32.toUSize open Finset renaming range->iD,Ico->i9,sum_range_succ'->jC,mul_sum->jJ,sum_const->jU,sum_Ico_eq_sum_range->kh open UInt64 renaming reduceToNat->iE,size->jo,toNat->jE,toNat_or->j6,toNat_toBitVec->la,ofNat->lF,toNat_one->lP open FloatLib.Floats.Formats.BinaryInterchange.FloatFormat renaming binary64->iF open ExactRuntime renaming expOf->iG,Word->iJ,idxOf->iL,rowVariance->iS,stableNormDomain->iU,sqrtRational->iY,rowMean->i7,mantOf->jd,toWord->je,signOf->jh,layernormStable->jt,oneW->jN,dotOf->jP,linearSpec->jV,rmsnormStable->jZ,mantOf_lt_24->ke,finishWord->kj,ofIntDyadic->ky,Fmt->kD,finishWord_of_ne->kG,finiteWord->kO open FloatLib.Floats.Formats.BinaryInterchange.Model renaming ofFloatModel->iH,roundDyadic->iI,unpackedToReal->i6,unpackedToDyadic?->ji,ofUInt32->jn,toReal->jp,roundedMantissa_shift_quotient->jq,toReal_eq->jr,roundDyadic_of_representable->jv,roundAt_mono->jw,unpackSign_packComponents->jO,roundAt->jW,toModel->jY,toReal_add_eq_roundAt->kf,isFinite->kk,toNatBits_lt_two_pow->km,posMaxFinite->ko,ofNatBits_toNatBits->ku,pow2_eq_two_pow->lb,ofFloat32Model->ln,add->lp,ofModel->lv,modelSignBit->ly open Real renaming sqrt->iK,sq_sqrt->kP,le_sqrt_of_sq_le->ld,sqrt_mul->lx,sqrt_sq->lM open Nat renaming reduceMod->iM,div_add_mod->js,and_one_is_mod->ju,mul_one->jz,le_log2->jA,testBit_eq_decide_div_mod_eq->jD,one_shiftLeft->jF,cast_ofNat->jI,log2_self_le->jQ,mul_lt_mul''->jS,cast_natAbs->kb,lt_of_le_of_lt->kp,pos_of_ne_zero->ks,cast_zero->kE,le_mul_of_pos_left->kM,cast_sub->kN,add_zero->kQ,log2_eq_iff->kR,cast_nonneg->kW,le_div_iff_mul_le->kZ,div_lt_iff_lt_mul->k9,log2_lt->lf,pow_lt_pow_right->lg,mul_le_mul->li,add_mul->lm,zero_mul->lG,cast_one->lH,abs_cast->lK open Float.Model.UnpackedFloat renaming unpack->iN,abs->i4,isFinite->i5,mul->i8,pack->jj,packedInfinity->jm,accuracyOfFraction->jx,roundWithAccuracy->kB,unpackExponent->lc,packedZero->lq,round->lu,compare->lE,Sign->lI open UInt32 renaming reduceToNat->iO,ofNat->jG,toNat_shiftLeft->jH,toNat_max->jT,toNat_ofNat'->kc,toNat_add->kH,toNat_or->kS,toNat_zero->lJ open FloatArray renaming emptyWithCapacity->iP,size->iX,uget->j8,set!->j9,usize->lQ,uset->lV open FloatLib.Numerics renaming shiftRightJam->iQ,Dyadic->iR,binaryRadix->iT,roundShiftRightEven_shiftRightJam->jB,roundQuotientEven->kA open USize renaming reduceToNat->iV,size->jR,ofNat->j5,toNat_add->j7,toNat_one->kT,toNat_mul->kV open Array renaming ofFn->iZ,getElem?_eq_none->jK,replicate->ka,getElem?_eq_getElem->kx,all_eq_true->kC,size_ofFn->kX,usize->lh,setIfInBounds->lr,getElem?_ofFn->ls,getElem_push->lz,getElem?_set->lB,ext_getElem?->lC,uset_eq_set->lL,ext->lR,set!->lY,uset->lZ open Float.Model renaming totalExponent->i0,pack->kI,sqrt->lS,add->lT,mul->lU,sub->lW open FloatLib.Numerics.Dyadic renaming ofScaledInt->ja,toReal->jg,signedSignificand->jl,cast_signedSignificand->kz,toRat_eq_zero_iff->kK,ofScaledInt_toRat->kL,toRat->lO open Float.Model.Format renaming binary64->jb,binary32->jc open FloatLib.Numerics.FixedWord renaming roundShiftRightEven->jf open Float.Model.UnpackedFloat.ExtendedMantissa renaming shiftRightOne->jk open FloatLib.Floats.Formats.Flocq renaming bpow->jy open FloatLib.Numerics.RationalBinary renaming scaleByPowerOfTwo->jL open FloatLib.Floats.ExecFloat.Binary renaming toModel_ofFloat_int64ToFloat->jM open Int renaming ofNat_eq_natCast->j0,toNat_of_nonneg->kd,log->kg,lt_zpow_succ_log_self->kv,zpow_log_le_self->lj open FloatLib.Floats.Formats.BinaryInterchange.Model.Reduction.Semantics renaming finiteDot_toList_eq_slice->ki,finiteDotSlice->kY open BitVec renaming toInt_eq_toNat_cond->kl open System.Platform renaming numBits_eq->kr,numBits->kJ open Float32 renaming ofBits->kt open FloatLib.Floats.Formats.BinaryInterchange.Model.Reduction.Internal renaming dotState_exact_toRat->kF,dotState->lD,State->lN open Bool renaming or_eq_true->kU open FloatLib.Floats.Formats.Flocq.bpow renaming pos->lk open Or renaming inr->ll,inl->lA open Max renaming max->lX local notation "п"=>Nat local notation "р"=>Int local notation "с"=>Float local notation "т"=>Word local notation "у"=>Array local notation "ф"=>Bool local notation "х"=>USize open _root_ renaming mul_le_mul_of_nonneg_right->AA,zpow_natCast->AB,pow_le_pow_right₀->AC,abs_sub_abs_le_abs_sub->AD,mul_le_mul_of_nonneg_left->AE,abs_nonneg->AF,decide_eq_true_eq->AG,two_ne_zero->AH,zpow_add₀->AI,abs_of_pos->AJ,pow_add->AK,getElem!_pos->AL,abs_mul->AM,ite_false->AN,le_rfl->AO,ite_eq_right->AP,one_div_le_one_div_of_le->AQ,div_le_div_iff₀->AR,abs_of_nonneg->AS,abs_add_le->AT,div_mul_eq_mul_div->AU,ite_true->AV,mul_nonneg->AW,abs_sub_le->AX,abs_le->AZ,beq_iff_eq->Aa,lt_of_le_of_lt->Ac,mul_assoc->Ad,le_trans->Ae,mul_le_mul->Af,mul_lt_mul_of_pos_right->Ag,one_le_pow₀->Ah,zpow_le_one_of_nonpos₀->Ai,one_mul->Aj,zero_add->Ak,bne_iff_ne->Am,lt_of_mul_lt_mul_right->Ao,zpow_sub₀->Ap,sq_nonneg->Aq,lt_irrefl->Ar,dite_eq_left->As,abs_sub_comm->Au,dite_eq_right->Ax,pow_succ->Ay,div_le_one->Az,getElem!_neg->A0,le_abs_self->A1,div_le_iff₀->A2,pow_succ'->A3,gt_iff_lt->A4,dite_eq_right->A5,zpow_ofNat->A6,div_nonneg->A7,add_le_add->BA,decide_eq_true_iff->BB,nsmul_eq_mul->BC,dite_eq_left->BD,le_antisymm->BI,pow_mul->BK,abs_two->BL,abs_neg->BM,abs_div->BN,div_le_div_iff_of_pos_right->BO,div_le_div_of_nonneg_right->BQ,zpow_add_one₀->BR,add_pos_of_nonneg_of_pos->BS,ne_eq->BU,abs_pow->BW,abs_mul_self->BX,le_of_mul_le_mul_left->Bf open Array renaming replicate->AY,emptyWithCapacity->Av,ofFn->Aw open USize renaming reduceToNat->Al,size->BE open FloatArray renaming emptyWithCapacity->An open Nat renaming lt_succ_iff->BF,log2->BG,pos_iff_ne_zero->BV,lt_of_lt_of_le->Ba,lt_of_le_of_ne->Bb,eq_or_lt_of_le->Bc,succ_le_of_lt->Bg,le_of_lt_succ->Bh open Model renaming roundAt->BH,ofFloatModel->BT open Finset renaming range->BJ open UInt64 renaming toNat_lt->BY,le_of_lt->BZ open Int renaming natAbs_eq_zero->Bd open Float32 renaming ofBits->Be open Float.Model.Format renaming targetExponent->Bi structure Acc where pos:у п neg:у п special:ф negZero:ф def Acc.iB:Acc:=⟨AY 18 0,AY 18 0,М,Л⟩ def Acc.iC(acc:Acc):р:=(limbVal acc.pos.toList:р)-limbVal acc.neg.toList @[inline]def Acc.add(acc:Acc)(m idx:п)(neg:ф):Acc:= match acc with | ⟨pos,ng,sp,nz⟩=> if m=0 then⟨pos,ng,sp,nz&&neg⟩ else if neg then⟨pos,addLimbs64 ng mж idx,sp,М⟩ else⟨addLimbs64 pos mж idx,ng,sp,М⟩ section open FloatLib.Numerics lemma br(s:ф)(m:п)(e:р)(j:п)(h:j+25<=mз): iI kD ⟨s,iQ m j,e+j⟩=iI kD ⟨s,m,e⟩:=by have l:m≠0:=by rintro rfl;simp at h have p:2^mз<=m:=jQ l;have v:2^(j+1)<=m:=Ae (Μ Г А) p;have d:(iQ m j)з=mз-j:=log2_shiftRightJam m j v have u:iQ m j≠0:= shiftRightJam_ne_zero m j (Ae (Μ Г А) v) rw[<-ϵ,<-ϵ];unfold Model.roundDyadicGeneral;simp only[u,l,Aa,AN,d];have r:((mз-j:п):р)+(e+j)=(mз:р)+e:=А;rw[r];have t:Fmt.fracWidth=23:=rfl;have q:Fmt.minSubnormalExponent=-149:=rfl;have o:Fmt.minNormalExponent=-126:=rfl;rw[t,q,o];split_ifs with h1 h2 h3 h4<;>try omega .rfl .congr 1 have⟨a,w⟩:∃a:п,e- -149=Int.negSucc a:=⟨(-(e+149)-1)л,А⟩ have x:e+j- -149=Int.negSucc (a-j):=А;rw[w,x];dsimp only;rw[(А:a-j+1=(a+1)-j)] exact jB m j (a+1) А .congr 1 rw[(А:mз-j-23=(mз-23)-j)] exact jB m j _ А end lemma ab(n:п)(f:п->Е)(k:п)(d:kf iи)[k]! =f k:=by rw[AL _ k (by simpa using d),Ν] namespace Core def tm(a b:т):р:=sv a*sv b*2^(idxOf a+idxOf b) def ae(n:п)(fa fb:п->т):р:=∑k∈BJ n,tm (fa k) (fb k) def al(n:п)(fa fb:п->т):Prop:=∀k,kexpOf (fa k)≠255/\expOf (fb k)≠255 lemma ap(n:п)(d e:п->iJ): ae (n+1) d e=ae n d e+tm (d n) (e n):=by unfold ae;rw[Ξ] lemma dI(A B:у Е)(i c:п): dsum A B i c=∑k∈iD c,tm A[i+k]! B[i+k]!:=by induction c generalizing i with | zero=>simp[dsum] | succ c d=> rw[dsum,d (i+1),jC,add_comm];exact congrArg₂ _ (Τ rfl λk _=>by rw[(А:i+1+k=i+(k+1))]) rfl lemma cF(n:п)(d e:п->iJ): dsum (iZ (n:=n) λi=>d iи) (iZ (n:=n) λi=>e iи) 0 n= ae n d e:=by rw[dI,ae] exact Τ rfl λk h=>by rw[Κ]at h;rw[ϥ,ab n d k h,ab n e k h] lemma a8(n:п)(p q:п->iJ)(v:al n p q): jP n p q=kj (ae n p q) (-298) (decide (n≠0)&& dallNZ (iZ (n:=n) λi=>p iи) (iZ (n:=n) λi=>q iи) 0 n):=by rw[jP];set A:=iZ (n:=n) λi=>p iиwith r set B:=iZ (n:=n) λi=>q iиwith u have o:∀k,kiG A[k]!≠255/\iG B[k]!≠255:=λk l=>by rw[r,u,ab n p k l,ab n q k l];exact v k l have y:∀X:у iJ,Xв=n->(∀k,kiG X[k]!≠255)-> ∀k (l:k<(X.map (jn (fmt:=kD)))в), kk (X.map (jn (fmt:=kD)))[k]=Л:=by intro X H h k l;have x:k(o k l).1 have j:=y B (by simp[u]) λk l=>(o k l).2 have l:∀k,0<=k->k<0+Lв->iG A[k]!≠255/\iG B[k]!≠255:= λk _ G=>o k (by simpa[t,r]using G) have d:kY L R 0 Lв (О) (by simp[m])=(ae n p q:ℚ)*2^(-298:ℤ):= (finiteDotSlice_eq A B 0 Lв (by simp[t]) (by simp[t,r,u]) l).trans (by simp[t,r,u,cF]) have z:=kF (destination:=kD) L R m e j;rw[dotSpec,Model.dot];by_cases w:ae n p q=0 .rw[w,finishWord_zero,Model.Reduction.dotWithStatus_eq_zero_of_finite kD L R .nearestEven m e j ((kK _).1 (by rw[z,d,w];simp))] have⟨D,E⟩:=dotStateLoop_flags A B ({}:lN kD) 0 Lв (by simp[t]) (by simp[t,r,u]) l rw[lD];rw[D,E];simp[t,r];rfl .rw[Model.Reduction.dotWithStatus_eq_round_of_finite_nonzero kD L R .nearestEven m e j (by rw[ki L R m];intro h;injection h with h;rw[d]at h;simp at h;exact w h)] exact(kG _ (ae n p q) (-298) _ w (by rw[z,d])).symm lemma bg(n:п)(d e:п->iJ)(h:al n d e) (j:ae n d e≠0): jP n d e=kj (ae n d e) (-298) М:=by rw[a8 n d e h];simp only[kj,j,if_false] @[inline]def ds(w:Е):Д:=if(w>>>23)&&&255!=0 then 1 else 0 @[inline]def mW(w:Е):Д:=(w&&&8388607)к|||(ds w<<<23) @[inline]def iW(w:Е):Д:=((w>>>23)&&&255)к-ds w def bl(x:Д):р:=x.toBitVec.toInt lemma dJ(w:Е):(w&&&8388607)г<2^23:=by rw[Ρ];exact Ac Ϻ Б lemma aU(w:Е):(mW w)а=jd w:=by have h:=dJ w;rw[mW,ds,jd,iG,fracOf];by_cases d:(w>>>23)&&&255=0 .simp[d] .have e:((w>>>23)&&&255!=0)=Л:=by simpa using d simp only[e,d,AV,AN] rw[j6,ϟ,show((1:Д)<<<23)а=2^23*1 fromН,Nat.or_comm, <-ϗ h,jz,Ϙ] lemma bk(w:Е):(iW w)а=iL w:=by rw[iW,ds,iL,iG];have j:=expOf_toNat_lt w;rw[iG]at j;by_cases e:(w>>>23)&&&255=0 .simp[e] .have d:1<=((w>>>23)&&&255)г:= Nat.one_le_iff_ne_zero.2 λh=>e (Ι.mp (by simpa using h)) simp only[show((w>>>23)&&&255!=0)=true by simpa using e,e,AV,AN] rw[υ _ _ (κ.mpr (by rw[ϟ];simpa using d)), ϟ] rfl lemma az(w:Е):jh w=Л↔2^31<=wг:=by rw[jh];have e:=w.toNat_lt;have d:(w&&&0x80000000)г=wг&&&2^31:=by rw[Ρ];rfl rw[Nat.and_two_pow,jD]at d;rw[Am,BU,<-Ι,d];by_cases h:wг/2^31%2=1<;>simp[h]<;>omega @[inline]def sx(k x:Д):Д:=bif x>>>k==0 then x else x>>>k @[inline]def sr(k x r:Д):Д:=bif x>>>k==0 then r else r+k @[inline]def ao(x0:Д):Д:= let x1:=sx 32 x0 let r1:=sr 32 x0 0 let x2:=sx 16 x1 let r2:=sr 16 x1 r1 let x3:=sx 8 x2 let r3:=sr 8 x2 r2 let x4:=sx 4 x3 let r4:=sr 4 x3 r3 let x5:=sx 2 x4 let r5:=sr 2 x4 r4 sr 1 x5 r5 @[inline]def dx(value shift:Д):Д:= let quotient:=value>>>shift let remainder:=value&&&((1<<half then quotient+1 else if(quotient&&&1)==0 then quotient else quotient+1 @[inline]def bV(value shift:Д):Д:= let quotient:=value>>>shift let remainder:=value&&&((1<<half then 1 else 0) @[inline]def aE(value shift:Д):Д:= if shift==0 then value else if shift<64 then bV value shift else if shift==64 then(if value>0x8000000000000000 then 1 else 0) else 0 @[inline]def bR(sign:ф)(e f:Е):Е:= (if sign then(0x80000000:Е)else 0)|||((e&&&255)<<<23)|||(f&&&8388607) @[inline]def cr(n:Д):Е:= (if n<8388608 then 0 else n-8388608)м @[inline]def aw(sign:ф)(product scale:Д):Е:= if product==0 then if sign then 0x80000000 else 0 else let leading:=ao product let position:=leading+scale if position<172 then let fraction:= if scale<149 then aE product (149-scale)else product<<<(scale-149) if fraction==0 then(if sign then 0x80000000 else 0) else if fraction==8388608 then bR sign 1 0 else bR sign 0 fractionм else let roundedMantissa:= if leading<23 then product<<<(23-leading)else aE product (leading-23) let carry:=roundedMantissa==16777216 let normalizedPosition:=if carry then position+1 else position if normalizedPosition>425 then(if sign then 0xff800000 else 0x7f800000) else let normalizedMantissa:=if carry then 8388608 else roundedMantissa bR sign (normalizedPosition-171)м (cr normalizedMantissa) open Model.NativeBinary32 in lemma cy(n k:п)(h:n>>>k≠0):nз=k+(n>>>k)з:=by rw[ι]at h⊢;have e:=(kZ (Nat.two_pow_pos k)).1 (jQ h);have d:=(k9 (Nat.two_pow_pos k)).1 (Ϝ (n:=n/2^k));rw[kR (by rintro rfl;simp at h)] simp only[Nat.pow_succ,Nat.pow_add]at d⊢;constructor<;>nlinarith lemma cx(x:Д):xаз<64:=by by_cases h:xа=0 .simp[h] .exact(lf h).mpr x.toNat_lt lemma bE(l r x k:Д)(q:kа<=32)(p:0>>k)а=xа>>>kа:=by rw[ο,θ А] rw[sx,sr];by_cases j:x>>>k=0 .simp only[j,beq_self_eq_true,Bool.cond_true] exact⟨d,by simpa[e,ι,Nat.div_eq_zero_iff]using congrArg jE j⟩ .simp only[show(x>>>k==0)=М by simpa using j,Bool.cond_false] have t:=cy xа kа λh=>j (χ.mp (by simpa[e]using h)) have m:=cx l;refine⟨by rw[ξ,θ А,e];omega,?_⟩ rw[e,ι];exact ϶ (by rw[<-Nat.pow_add];exact lt_of_lt_of_eq o (by congr 1;omega)) lemma b8(n:п)(h:n<2):nз=0:=by rw[Nat.log2_def,AP А] lemma aK(x:Д):ao x=x.log2:=by apply χ.mp;rw[show x.log2а=xазfromН];have d:xа<2^(2*(32:Д)а):=x.toNat_lt;have⟨p,e⟩:=bE x 0 x 32 Б Б (О) d have⟨q,h⟩:=bE x _ _ 16 Б Б p (by simpa using e) have⟨r,j⟩:=bE x _ _ 8 Б Б q (by simpa using h) have⟨t,l⟩:=bE x _ _ 4 Б Б r (by simpa using j) have⟨u,m⟩:=bE x _ _ 2 Б Б t (by simpa using l) have⟨v,o⟩:=bE x _ _ 1 Б Б u (by simpa using m) rw[b8 (sx 1 (sx 2 (sx 4 (sx 8 (sx 16 (sx 32 x))))))а (by simpa using o)]at v unfold ao;dsimp only;omega lemma dM(v s:Д)(p:s≠0)(h:s<64):bV v s=dx v s:=by have j:sа<64:=h have o:(2:п)^sа<0x10000000000000000:= lt_of_lt_of_le (lg Г j) Г have e:(v&&&((1<<simp[κ, θ j,jF,θ o,γ,Nat.one_le_two_pow] have d:((v>>>s)&&&1)а=(v>>>s)а%2:=by simp[Α,ju] have q:=ϩ vа (show 0<2^sа by positivity) have l:((v&&&((1<<>>s)&&&1))а=vа%2^sа+(v>>>s)а%2:=by rw[ξ,e,d,θ А] have m:((v>>>s)&&&1==0)=decide ((v>>>s)а%2=0):=by rw[<-d,Ϥ,Aa,BB,<-χ,ϓ] unfold bV dx;simp only[A4,ν,l,e,m,AG];split_ifs<;>first | rfl | omega | simp lemma cR(e d:Д): aE e d=jf e dа:=by have p:aE e d=(if d==0 then e else if d<64 then dx e d else if d==64 then(if e>0x8000000000000000 then 1 else 0) else 0):=by rw[aE];split_ifs with a b<;>first | rfl | exact dM _ _ (by simpa using a) b rw[p];rw[dx,jf];have q:=d.toNat_lt;by_cases j:d=0 .subst j;rfl .have l:dа≠0:=λh=>j (χ.mp (by simpa using h)) simp only[j,Aa,l,reduceIte] have o:lF (dа-1)=d-1:=by apply χ.mp;rw[υ _ _ (by rw[κ];simp;omega)];simp;omega have m:(d<64)↔dа<64:=ν;simp only[UInt64.ofNat_toNat,o,<-m,show d=64↔dа=64 by rw[<-χ];rfl] open Model.NativeBinary32 in lemma cN(d:ф)(e f:п): bR d (jG e) (jG f)=mkBits d e f:=by rw[bR,mkBits];cases d<;>rfl lemma bi(x:Д):xм=jG xа:=С lemma bN(n:Д):cr n=jG (nа-8388608):=by rw[cr];split<;>rename_i h<;>rw[ν]at h<;>rw[bi] .rw[show nа-8388608=0 by simp at h;omega];rfl .rw[υ _ _ (by rw[κ];simp at h⊢;omega)];rfl open Model.NativeBinary32 in lemma aZ(h:ф)(d e:Д): aw h d e=roundProduct h d e:=by unfold aw roundProduct;simp only[aK,cR,bN,bi];rw[show(1:Е)=jG 1 from rfl,show(0:Е)=jG 0 from rfl];simp only[cN] open Model.NativeBinary32 in lemma bK(w:Е):je (ofUInt32 w)=w:=by have h:=toUInt32_ofUInt32 w;unfold toUInt32 at h;unfold je;conv_rhs=>rw[<-h] exact Ι.mp (θ (BitVec.isLt _)) open Model.NativeBinary32 in lemma aO(h:ф)(m d:Д)(j:dа<=506): aw h m d=je (iI kD ⟨h,mа,(dа:р)-298⟩):=by rw[aZ,roundProduct_eq_roundDyadic _ _ _ j] have e:iI kD ⟨h,mа,(dа:р)-298⟩= ofUInt32 (roundDyadic ⟨h,mа,Int.ofNat dа-298⟩):= (ofUInt32_roundDyadic _).symm rw[e,bK] def ar(hi lo:Д):р:=bl hi*2^64+loа @[inline]def cz(hi lo:Д):Д:=if hi>>>63!=0 then(0:Д)-lo else lo @[inline]def aH(hi lo:Д):Д:= if hi>>>63!=0 then(if lo==0 then(0:Д)-hi else~~~hi)else hi lemma ck(d:Д):(d>>>63!=0)=decide (2^63<=dа):=by have e:(d>>>63)а=dа/2^63:=by rw[ο];simp[ι] have:=d.toNat_lt;rw[Ϥ,Am,BU,<-χ,e,BB];simp lemma be(d e:Д): ar d e=(dа*2^64+eа:р)-(if 2^63<=dаthen 2^128 else 0):=by rw[ar,bl];rw[kl,la];omega lemma db(e d:Д): (ar e d)й=(aH e d)а*2^64+(cz e d)а/\ decide (ar e d<0)=(e>>>63!=0):=by have o:=e.toNat_lt;have p:=d.toNat_lt;rw[aH,cz];rw[be,ck];by_cases l:2^63<=eа .simp only[l,decide_true,AV] by_cases j:d=0 .subst j simp only[beq_self_eq_true,AV,ϓ];rw[Λ];simp;omega .have m:dа≠0:=λh=>j (χ.mp (by simpa using h)) simp only[show(d==0)=false by simpa using j,μ,AN] rw[Λ,UInt64.toNat_not];simp;omega .simp only[l,decide_false,μ,AN];simp;omega @[inline]def aN(hi lo B:Д):Д:= if hi==0&&lo==0 then 4294967296 else if B>442 then 4294967296 else let neg:=hi>>>63!=0 let mlo:=cz hi lo let mhi:=aH hi lo if mhi==0 then(aw neg mlo B)к else if mhi>>>32==0 then let q:=(mhi<<<32)+(mlo>>>32) (aw neg (if mlo&&&0xFFFFFFFF==0 then q else q|||1) (B+32))к else(aw neg (if mlo==0 then mhi else mhi|||1) (B+64))к lemma ak(x:Е):xкм=x:=О lemma eT(e d:Д)(h:eа<2^32): (if d&&&0xFFFFFFFF==0 then(e<<<32)+(d>>>32) else((e<<<32)+(d>>>32))|||1)а= iQ (eа*2^64+dа) 32:=by have l:=d.toNat_lt have m:((e<<<32)+(d>>>32))а=eа*2^32+dа/2^32:=by simp[ξ,Ζ,ι];omega have j:(d&&&0xFFFFFFFF)а=dа%2^32:=by rw[Α];exact γ _ 32 unfold iQ simp only[(А:(eа*2^64+dа)/2^32=eа*2^32+dа/2^32), show(eа*2^64+dа)%2^32=dа%2^32 by omega, show(d&&&0xFFFFFFFF==0)=decide (dа%2^32=0) by rw[<-j,Ϥ,Aa,BB,<-χ,ϓ]] split_ifs<;>simp_all[j6] lemma eU(e d:Д): (if d==0 then e else e|||1)а= iQ (eа*2^64+dа) 64:=by have m:=d.toNat_lt;have h:(eа*2^64+dа)/2^64=eа:=А;have j:(eа*2^64+dа)%2^64=dа:=А;rw[iQ];rw[h,j];by_cases l:dа=0<;>simp[l,j6,<-χ] lemma cP(s:ф)(q B J:Д)(M:п) (e:qа=iQ M Jа) (j:Bа<=442) (l:Jа<=64) (d:2^(Jа+25)<=M): aw s q (B+J)=je (iI kD ⟨s,M,(Bа:р)-298⟩):=by have h:(B+J)а=Bа+Jа:=by rw[ξ];simp;omega rw[aO _ _ _ А,e,h,<-br s M _ Jа ((jA (BV.1 (lt_of_lt_of_le В d))).2 d)] congr 3;omega lemma b7(d e B:Д)(h:aN d e B<4294967296): ar d e≠0/\Bа<=442/\ (aN d e B)м= je (iI kD (ky (ar d e) ((Bа:р)-298))):=by have⟨o,p⟩:=db d e;have A:=e.toNat_lt;have z:=d.toNat_lt;rw[aN]at h⊢;by_cases u:(d==0&&e==0)=Л .simp[u]at h .simp only[u,μ,AN]at h⊢ have x:ar d e≠0:=λl=>u (by rw[be]at l;simp only[Β,Aa,<-χ,ϓ];split at l<;>omega) by_cases q:B>442 .simp[q]at h .simp only[q,AN]at h⊢ have j:Bа<=442:=by simpa[ν]using q refine⟨x,j,?_⟩;rw[ky];rw[p,o];have r:=ο (aH d e) 32;rw[ι]at r;split .rename_i l rw[(by simpa using congrArg jE (beq_iff_eq.mp l):(aH d e).toNat=0),lG,ϥ, ak,aO _ _ _ А] .rename_i l have w:(aH d e)а≠0:=λm=>l (by simp[<-χ,m]) split .rename_i m have t:(aH d e)а<2^32:=by have:=congrArg jE (beq_iff_eq.mp m);simp at this r;omega rw[ak];exact cP _ _ _ 32 _ (eT _ _ t) j Б (by simp;omega) .rename_i m have v:2^32<=(aH d e)а:=by by_contra y;apply m;simp[<-χ];omega rw[ak];exact cP _ _ _ 64 _ (eU _ _) j Б (by simp;omega) lemma bn(n:п)(e j:п->iJ)(m o B:Д) (l:al n e j) (d:ae n e j=ar m o*2^Bа) (h:aN m o B<4294967296):jP n e j=(aN m o B)м:=by have⟨r,t,q⟩:=b7 m o B h;have p:ae n e j≠0:=by rw[d];exact mul_ne_zero r В rw[bg n e j l p,q];refine kG _ _ _ _ p ?_;rw[toRat_ofIntDyadic,d];push_cast;rw[Ap AH,AB];field_simp @[inline]def ah(N:Д):Д:=(N+(0x3FFFFFFFFF:Д)+((N>>>39)&&&1))>>>39 lemma dL(n:ф)(e f:Е): (bR n e f)г=(if n then 2^31 else 0)+eг%2^8*2^23+fг%2^23:=by have j:=ϩ fг (А:0<2^23) have l:=ϩ eг (А:0<2^8) have h:((e&&&255)<<<23)г=2^23*(eг%2^8):=by rw[jH,Ρ,show(255:Е)г=2^8-1 fromН, γ,Ζ,Ϧ] exact θ (by simp;omega) have d:((e&&&255)<<<23|||(f&&&8388607))г=2^23*(eг%2^8)+fг%2^23:=by rw[kS,h,Ρ,show(8388607:Е)г=2^23-1 fromН, γ,<-ϗ j] rw[bR];rw[UInt32.or_assoc];cases n .simp only[μ,AN,UInt32.zero_or,d];omega .simp only[AV,kS,d] rw[show(0x80000000:Е)г=2^31*1 fromН,<-ϗ А];omega lemma bT(n:ф)(N h:Д)(p:2^62<=Nа)(q:Nа<2^63)(y:110<=hа) (w:hа<363): (aw n N h)г=(if n then 2^31 else 0)+((hа-110)*2^23+(ah N)а)/\ 2^23<=(ah N)а/\(ah N)а<=2^24:=by have m:(N>>>39)а=Nа/2^39:=by simp[ι] have l:((N>>>39)&&&1)а=Nа/2^39%2:=by simp[m,ju] have o:(ah N)а=Nа/2^39+if 2^38omega have d:2^23<=Nа/2^39/\Nа/2^39<2^24:=by clear*-p q;omega have e:2^23<=(ah N)а/\(ah N)а<=2^24:=by rw[o];clear*-d;split<;>omega have j:(aE N (62-23))а=(ah N)а:=by have v:(N&&&0x7FFFFFFFFF)а=Nа%2^39:=by rw[Α];exact γ _ 39 rw[o];show(bV N 39)а=_;rw[bV] simp only[show((1:Д)<<<39)-1=0x7FFFFFFFFF fromН,show(1:Д)<<<(39-1)=0x4000000000 from rfl,A4,ν,ξ,v,l,m,apply_ite jE,iE] clear*-d;split_ifs<;>omega have r:ao N=62:=by rw[aK];apply χ.mp;rw[show N.log2а=NазfromН,kR А];simp;omega refine⟨?_,e⟩;rw[aw];have t:(N==0)=М:=by simp[<-χ];omega simp only[r,t,show¬62+h<172 by simp[ν];omega,(Б:¬(62:Д)<23), AN,μ] generalize aE N (62-23)=R at j⊢;have u:2^23<=Rа/\Rа<=2^24:=by rw[j];exact e rw[<-j];clear m l o j r p q d e cases n<;>split_ifs<;>simp(disch:=first | omega | (simp[κ];omega)) only[Aa, <-χ,A4,ν,dL,bN,Ϡ, kc,ξ,iE,θ,υ,AV, AN,μ,not_true_eq_false]at*<;>omega lemma cQ(n:ф)(M σ:Д)(e:Mа≠0)(d:σа<=506): aw n M σ=kj ((if n then-(Mа:р)else Mа)*2^σа) (-298) М:=by rw[aO _ _ _ d];refine(kG _ _ _ _ (mul_ne_zero (by split<;>omega) В) ?_).symm cases n<;>simp[lO,jl,Ap]<;>field_simp end Core open Core lemma aV(z:Model kD):ofW (je z)=z:=by have h:z.toNatBits<2^32:=km z;rw[ofW,je,jn,kc,θ h];exact ku z namespace Dense lemma ac{k n:х}(h:ksplit<;>push_cast<;>omega @[inline]def aJ(x:Е):Е:=x&&&0x7FFFFFFF lemma aq(x:Е):(aJ x)г=xг%2^31:=by rw[aJ];rw[Ρ];exact γ _ 31 lemma av(x:Е):(iG x)г=(aJ x)г/2^23:=by have:(iG x)г=xг/2^23%2^8:=by unfold iG;rw[Ρ,ϔ];simp only[iO,iM,ι];exact γ _ 8 rw[this,aq,show 2^31=2^23*2^8 by norm_num,Nat.mod_mul_right_div_self] lemma cZ(x:Е):iG x=0↔(aJ x)г<2^23:=by rw[<-Ι,av];simp;try omega lemma gj(x:Е):iL x=(aJ x)г/2^23-1:=by have:=av x;rw[iL];split<;>rename_i h .have:=(cZ x).mp h;omega .have:=mt (cZ x).mpr h;omega lemma aT(x:Е):iL x=(iG x)г-1:=by rw[gj,av] lemma gq(w:Е):wг/2^23=(iG w)г+256*(wг/2^31):=by rw[av,aq];have:=w.toNat_lt;omega lemma a9(x:Е):(iG x)г<256:=by rw[av,aq];omega lemma c9(w:Е):(w&&&8388607)г=wг%2^23:=by rw[Ρ];exact γ _ 23 lemma aQ(w:Е):|sv w|<2^24:=by have:=ke w;rw[sv];split<;>simp<;>omega lemma aF{k:х}{a:у Е}(h:k>>1>>>(63-s))+(if l'simp only[iE]<;>omega @[specialize]def f9(fa fb:п->т)(n t:п)(B:Д):Д:= if tт)(n:п)(B:Д)(t:п)(pH pL nH nL:Д):Д:= if tsplit<;>push_cast<;>omega lemma df(d j:п->iJ)(n:п)(B:Д)(hn:n<2^18): ∀k t (w x u v:Д),n-t=k->t<=n->al t d j-> wа*2^64+xа<=t*2^108->uа*2^64+vа<=t*2^108-> ae t d j=(((wа*2^64+xа:п):р)-((uа*2^64+vа:п):р))* 2^Bа-> bZ d j n B t w x u v<4294967296->jP n d j=(bZ d j n B t w x u v)м:=by intro k;induction k<;>intro t w x u v hk ht hf M K N l .obtain rfl:t=n:=А rw[bZ,AP А]at l⊢;exact bn _ _ _ _ _ _ hf (by rw[N,iy _ _ _ _ А А]) l rename_i k Z;have X:t(Nat.lt_succ_iff_lt_or_eq.mp F).elim (hf s) λe=>e▸⟨I,J⟩ have p:jd (d t)*jd (j t)<2^48:= (jS (ke _) (ke _)).trans_eq Г have U:(mW (d t)*mW (j t))а=jd (d t)*jd (j t):=by rw[Ϫ,aU,aU,θ (p.trans Г)] have E:=ap t d j;have o:=ψ (2^108) t.le_succ;split at l .rename_i G rw[if_pos G];have O:jd (d t)*jd (j t)=0:=by rw[<-U,beq_iff_eq.mp G];rfl refine Z (t+1) w x u v z A y (M.trans o) (K.trans o) ?_ l;rw[E,N,add_eq_left];unfold tm sv;rcases Nat.mul_eq_zero.mp O with h | h<;>simp[h] rename_i G;rw[AP G];obtain⟨hB,Q⟩:=hw λh=>G (by simp[h]) have a0:=idxOf_le _ I;have a1:=idxOf_le _ J have S:(iW (d t)+iW (j t))а=iL (d t)+iL (j t):=by rw[ξ,bk,bk,θ А] rw[S]at hB have F:(iW (d t)+iW (j t)-B)а=iL (d t)+iL (j t)-Bа:=by rw[υ _ _ (by rw[κ,S];omega),S] rw[F]at Q have W:(2:р)^(iL (d t)+iL (j t))=2^(iL (d t)+iL (j t)-Bа)*2^Bа:=by rw[<-AK];congr 1;omega generalize m:(jd (d t)*jd (j t))*2^(iL (d t)+iL (j t)-Bа)=T have r:T<=2^108:= m▸(li p.le (Μ Г (by omega:_<=60))).trans_eq Г have D:tm (d t) (j t)=(if jh (d t)==jh (j t)then(T:р)else-T)*2^Bа:=by rw[<-m];unfold tm sv;rw[W];cases jh (d t)<;>cases jh (j t)<;>simp<;>ring have V:=λH L (as:Hа*2^64+Lа<=t*2^108)=>de H L _ _ (by rw[F];omega) (by rw[U,F,m];omega) rw[U,F,m]at V;cases hg:(jh (d t)==jh (j t))<;>simp only[hg,AV,AN,μ]at D l⊢ .have q:=V u v K refine Z (t+1) w x _ _ z A y (M.trans o) (by rw[q];exact ώ t _▸Nat.add_le_add K r) ?_ l rw[E,N,q,D];push_cast;ring .have q:=V w x M refine Z (t+1) _ _ u v z A y (by rw[q];exact ώ t _▸Nat.add_le_add M r) (K.trans o) ?_ l rw[E,N,q,D];push_cast;ring @[inline]def eE(n:п)(fa fb:п->т):т:= let r:=if n<262144 then bZ fa fb n (f9 fa fb n 0 1023) 0 0 0 0 0 else 4294967296 if r<4294967296 then rмelse dotOf n fa fb lemma bs(n:п)(d e:п->iJ):eE n d e=jP n d e:=by unfold eE;dsimp only;by_cases j:n<262144 .rw[if_pos j];split .exact(df d e n _ А _ 0 0 0 0 0 rfl А (λ_ h=>absurd h А) (О) (О) (by simp[ae]) ‹_›).symm .rfl .rw[AP j,AP Б] @[noinline]def aj(n:п)(relu:ф)(X W b:@&у т)(xo s j:п):т:= act relu (eE (n+1) (λt=>if tif trfl lemma dV(x y:с)(d:fv x)(e:fv y): iH (x+y).toModel=lp (iH x.toModel) (iH y.toModel):=by change iH (lT x.toModel y.toModel)=_;rw[lT,ϫ] have h:=Model.add_eq_ofModel_add_of_isFinite (fmt:=iF) Б (iH x.toModel) (iH y.toModel) (by rw[Ε];exact(bG x).1 d) (by rw[Ε];exact(bG y).1 e) rw[Ε,Ε]at h;exact h.symm lemma pm(E:р)(e:E<=971):(2:ℝ)^E<=jp (ko iF):=by have d:FloatFormat.binary64.maxNormalExponent-Int.ofNat FloatFormat.binary64.fracWidth=971:=Б have h:=Ϣ iF М 1 E Б (by rw[d];exact e) simp only[μ,AN,lH,Aj]at h;change |(2:ℝ)^E|<=_ at h simpa only[AJ (zpow_pos (by norm_num:(0:ℝ)<2) E)]using h open FloatLib.Floats.Formats.Flocq in lemma re(x:ℝ)(E:р)(h:-1021<=E)(e:|x|<(2:ℝ)^E): |BH iF x-x|<=(2:ℝ)^(E-53)/2:=by by_cases d:x=0 .subst x;rw[Model.roundAt_zero];rw[sub_zero,abs_zero];positivity have j:magnitude iT x<=E:=magnitude_le_of_abs_lt_bpow _ x E d e;apply(Model.abs_roundAt_sub_le iF x).trans;apply BQ _ Г;change ulp iT (Model.fexpOf iF) x<=(2:ℝ)^(E-53);rw[ulp.of_ne_zero _ _ x d];change (2:ℝ)^(lX (magnitude iT x-53) (-1074))<=(2:ℝ)^(E-53);apply zpow_le_zpow_right₀ Г;omega lemma dk(x y:с)(d:fv x)(e:fv y)(l:|rv x+rv y|<=jp (ko iF)): fv (x+y)/\rv (x+y)=jW iF (rv x+rv y):=by have j:=dV x y d e have h:=Model.isFinite_add_of_abs_toReal_add_le_posMaxFinite (iH x.toModel) (iH y.toModel) Б d e l refine⟨by rw[fv];rw[j];exact h,?_⟩ rw[rv];rw[j];exact kf _ _ Б d e h lemma d6(x y:с)(m:fv x)(o:fv y)(E:р)(l:-1021<=E)(d:E<=971) (e:|rv x+rv y|<(2:ℝ)^E): fv (x+y)/\|rv (x+y)-(rv x+rv y)|<=(2:ℝ)^(E-53)/2:=by have⟨h,j⟩:=dk x y m o (e.le.trans (pm E d));exact⟨h,by rw[j];exact re _ E l e⟩ lemma rx(d:iR)(m:d.significand<2^53)(h:-1074<=d.exponent) (e:|d.toReal|<=(2:ℝ)^(971:р)): jW iF d.toReal=d.toReal:=by have⟨j,l⟩:=jv iF Б d d.significand 0 (О) m h (e.trans (pm 971 AO)) rw[<-Ϛ _ Б d j,l] lemma gb(x y:с)(p:fv x)(q:fv y)(d:iR)(h:d.toReal=rv x+rv y) (o:d.significand<2^53) (m:-1074<=d.exponent) (e:|d.toReal|<=(2:ℝ)^(971:р)): fv (x+y)/\rv (x+y)=rv x+rv y:=by have⟨j,l⟩:=dk x y p q (by rw[<-h];exact e.trans (pm 971 AO));exact⟨j,by rw[l,<-h];exact rx d o m e⟩ lemma cG(i:Int64)(e:iнй<2^53):fv i.toFloat/\rv i.toFloat=iн:=by have h:iH i.toFloat.toModel= iI iF (ja iн 0):= jM i have d:(ja iн 0).toReal=iн:=by rw[<-ϛ,kL];simp have⟨j,l⟩:=jv iF Б (ja iн 0) iнй 0 (jz _).symm e (by change _<=(0:ℤ);decide) (by rw[d,<-ϊ,ϳ];exact Ae (by exact_mod_cast e.le) (pm 53 Г)) exact⟨by rw[fv];rw[h];exact j,by rw[rv];rw[h,l,d]⟩ lemma gk(x y:с):iH (x*y).toModel= lv iF (i8 jb x.toModel.unpack y.toModel.unpack):=by change iH (lU x.toModel y.toModel)=_;rw[lU,ϫ] lemma eB(b:BitVec 64)(s:lI)(m:п)(e:р)(h:0< m) (d:iN jb b=.finite s m e h): 2^52<=m\/e=-1074:=by revert d;rw[iN];dsimp only;split .split<;>intro d<;>cases d .split .split .intro d;cases d .rename_i o _ intro d;injection d with _ _ l;right;rw[<-l,o];decide .intro d;injection d with _ j _ left;rw[<-j,BitVec.toNat_append];exact Ae Б Nat.left_le_or lemma d7(x y:с)(z:fv x)(A:fv y)(w:|rv x*rv y|<=(2:ℝ)^(971:р)): fv (x*y)/\rv (x*y)=jW iF (rv x*rv y):=by simp only[bG]at z A;rw[bW x,bW y]at w⊢;unfold fv rv;rw[gk];generalize B:x.toModel.unpack=X at z w⊢;generalize D:y.toModel.unpack=Y at A w⊢;cases X<;>cases Y<;>simp only[i5,μ]at z A case finite.finite q l e u r m h v=> have E:=eB _ q l e u B;have F:=eB _ r m h v D have p:e+h<=Float.Model.Format.binary64.targetExponent (i0 (l*m) (e+h)):=by change e+h<=lX ((BG (l*m):р)+1+(e+h)-53) (-1074);have:=(jA (n:=l*m) (k:=52) В).2;have:=Nat.le_mul_of_pos_right l v;have:=kM m u;omega let t:iR:=⟨xor (ly q) (ly r),l*m,e+h⟩ have j:lv iF (i8 jb (.finite q l e u) (.finite r m h v))=iI iF t:=by rw[i8,Model.roundWithAccuracy_exact_eq_round_of_le_targetExponent _ _ _ _ p];cases q<;>cases r<;>rfl have d:t.toReal=i6 (.finite q l e u)*i6 (.finite r m h v):= Model.Dyadic.toReal_mul ⟨_,l,e⟩ ⟨_,m,h⟩ have o:=Υ iF Б t (by rw[d];exact w.trans (pm 971 AO)) rw[j];exact⟨o,by rw[Ϛ _ Б t o,d]⟩ all_goals simp[i8,Model.isFinite_ofModel_zero iF Б, Model.toReal_ofModel_zero iF Б] lemma aD(s:ф)(m:п)(e:р): (⟨s,m,e⟩:iR).toReal=(if s then-(m:ℝ)else m)*(2:ℝ)^e:=by rw[jg,kz];split<;>simp def pw:п->с | 0=>(1:Int64).toFloat | k+1=>let p:=pw k;p+p lemma fX(k:п)(h:k<=900):fv (pw k)/\rv (pw k)=(2:ℝ)^k:=by induction k with | zero=>have:=cG 1 Б;rw[pw];exact⟨this.1,by rw[this.2];simp⟩ | succ k e=> have⟨f,v⟩:=e А have d:(⟨М,1,((k+1:п):р)⟩:iR).toReal=(2:ℝ)^(k+1):=by rw[aD];simp only[μ,AN,lH,Aj];exact AB 2 (k+1) have:=gb (pw k) (pw k) f f _ (by rw[d,v,Ay];ring) (show(1:п)<2^53 by norm_num) (А:(-1074:р)<=((k+1:п):р)) (by rw[d,AJ В,<-AB];exact zpow_le_zpow_right₀ Г А) rw[pw];exact⟨this.1,by rw[this.2,v,Ay];ring⟩ def nm:с:=(-1:Int64).toFloat def P:Ж:=⟨Aw (n:=512) λi=>if iи<256 then pw (iи-1)else nm*pw (iи-256-1)⟩ lemma dT:Pе=512:=by simp[P,iX] lemma eI(i:х)(h:iбif iи<256 then pw (iи-2)else nm*pw (iи-256-2)⟩ lemma bu:P2е=512:=by simp[P2,iX] lemma cB(i:х)(h:iб>>24)г=wг/2^24:=by rw[ϔ];simp[ι] lemma eS(w:Е):(iG w)г=(w<<<1)г/2^24:=by rw[av,aq,jH];simp only[iO,iM,Ζ];have:=w.toNat_lt;omega lemma bX(w:Е):(w>>>23)г=wг/2^23:=by rw[ϔ];simp[ι] @[inline]def dw(w:Е):с:= (Core.mW w).toInt64.toFloat*P.uget (w>>>23)о (by rw[dT,am,bX];have:=w.toNat_lt;omega) lemma bo(z e:р):(ky z e).toReal=(z:ℝ)*(2:ℝ)^e:=by rw[<-ϛ,toRat_ofIntDyadic];push_cast;rfl lemma bf(x y:с)(p:fv x)(q:fv y)(z e:р)(h:rv x*rv y=(z:ℝ)*(2:ℝ)^e) (o:zй<2^53) (m:-1074<=e) (d:|(z:ℝ)*(2:ℝ)^e|<=(2:ℝ)^(971:р)): fv (x*y)/\rv (x*y)=(z:ℝ)*(2:ℝ)^e:=by have⟨j,l⟩:=d7 x y p q (by rw[h];exact d) have:=rx (ky z e) o m (by rw[bo];exact d) rw[bo]at this;exact⟨j,by rw[l,h,this]⟩ lemma cn(w:Е):(sv w)й<2^24:=by have:=ke w;rw[sv];split<;>simp<;>omega lemma cm(a b c:п)(e:a+b<=c)(j:c<=971)(z:р)(h:zй<2^a): |(z:ℝ)*(2:ℝ)^(b:р)|<=(2:ℝ)^(971:р):=by rw[AM,AJ (by positivity:(0:ℝ)<2^(b:р)),AB] have d:|(z:ℝ)|<=2^a:=by rw[<-ϊ,ϳ];exact_mod_cast h.le refine(AA d В).trans ?_;rw[<-AK,<-AB];exact zpow_le_zpow_right₀ Г А lemma mV(u:Д)(n:п)(d:uа=n)(e:n<2^25): fv u.toInt64.toFloat/\rv u.toInt64.toFloat=(n:р):=by have:u.toInt64н=n:=by rw[show u.toInt64н=bl u fromН,aA,d];split<;>omega rw[<-this];exact cG _ (by rw[this];simp;omega) lemma qV(c:п)(A:Ж)(p:∀i h,A.uget i h=if iб<256 then pw (iб-c)else nm*pw (iб-256-c)) (w:Е) (h):fv (A.uget (w>>>23)о h)/\∃σ:р, (∀v,jh v=jh w->σ*jd v=sv v)/\σй=1/\ rv (A.uget (w>>>23)о h)=σ*2^((iG w)г-c):=by have:=a9 w;have:=w.toNat_lt;have d:=az w;have⟨l,m⟩:=fX ((iG w)г-c) А;rw[p,am,bX,gq];split .rw[(А:(iG w)г+256*(wг/2^31)-c=(iG w)г-c)] exact⟨l,1,λv e=>by simp only[sv,e,d];split<;>omega,rfl,by rw[m];push_cast;ring⟩ .rw[(А:(iG w)г+256*(wг/2^31)-256-c=(iG w)г-c)] have j:=cG (-1) Б have⟨o,q⟩:=bf _ _ j.1 l (-1) ((iG w)г-c:ℕ) (by rw[j.2,m,AB];rfl) Б А (cm 1 _ 971 А AO _ Б) exact⟨o,-1,λv e=>by simp only[sv,e,d];split<;>omega,rfl,by rw[<-AB];exact q⟩ lemma dG(c q:п)(A:Ж)(p:∀i h,A.uget i h=if iб<256 then pw (iб-c)else nm*pw (iб-256-c)) (u:Д) (v w:Е) (h) (t:q<=2) (y:uа=q*jd v) (x:jh v=jh w) (r:(q:ℝ)*2^((iG w)г-c)=2^iL v): fv (u.toInt64.toFloat*A.uget (w>>>23)о h)/\ rv (u.toInt64.toFloat*A.uget (w>>>23)о h)=(sv v:ℝ)*2^iL v:=by have:=ke v;have:=ψ (jd v) t;have:=a9 w;have⟨j,l⟩:=mV u _ y А;have⟨m,σ,d,o,z⟩:=qV c A p w h;have e:(((q*jd v:п):р)*σ)й<2^25:=by rw[Ϭ,o];simp;omega have:=bf _ _ j m _ ((iG w)г-c:п) (by rw[l,z,AB];push_cast;ring) (e.trans Г) А (cm 25 _ 971 А AO _ e) exact⟨this.1,by rw[this.2,<-r,AB,<-d v x];push_cast;ring⟩ lemma au(w:Е)(_:iG w≠255):fv (dw w)/\rv (dw w)=(sv w:ℝ)*2^iL w:= dG 1 1 P eI _ w w _ А (by simp[aU]) rfl (by simp[aT]) lemma dt(x w:Е)(l:iG x≠255)(j:iG w≠255): fv (dw x*dw w)/\rv (dw x*dw w)=(tm x w:ℝ):=by have⟨e,m⟩:=au x l;have⟨h,o⟩:=au w j have d:(sv x*sv w)й<2^48:=by rw[Ϭ];exact(jS (cn x) (cn w)).trans_eq Г have:=bf _ _ e h (sv x*sv w) (iL x+iL w:п) (by rw[m,o,AB,AK];push_cast;ring) (lt_trans d Г) А (cm 48 _ 971 (by rw[aT,aT];have:=a9 x;have:=a9 w;omega) AO _ d) refine⟨this.1,?_⟩;rw[this.2,tm,AB];push_cast;ring @[inline]def eF(b:Д):Д:=(b>>>52)&&&2047 @[inline]def mF(b:Д):Д:=(b&&&0xfffffffffffff)|||0x10000000000000 lemma gl(u:Д):(u&&&0x8000000000000000!=0)=(u>>>63!=0):=by apply Ϥ.mpr;simp only[Am,BU,<-χ];rw[Α,ο];change ¬uа&&&2^63=0↔¬uа>>>63=0;rw[Nat.and_two_pow,ι,jD];have d:uа/2^63<2:=by have h:=BY u;omega rw[θ d];by_cases e:uа/2^63=1<;>simp<;>omega lemma dl(v:с):iH v.toModel=Model.ofFields iF (v.toBits>>>63!=0) (((v.toBits>>>52)&&&2047)а) ((v.toBits&&&0xfffffffffffff)а):=by rw[<-Model.ofFields_signBit_expField_fracField (iH v.toModel)];congr 1;rw[<-gl];apply Ϥ.mpr;simp only[Model.signBit,Am,BU];rw[<-UInt64.toBitVec_inj];exact Iff.rfl lemma fq(v:с):((v.toBits>>>52)&&&2047)а<2^11/\(v.toBits&&&0xfffffffffffff)а<2^52:=by rw[Α];exact⟨Ac Ϻ Б,Ac Ϻ Б⟩ lemma aS(v:с)(e:fv v)(j:¬eF v.toBits=0): rv v=(⟨v.toBits>>>63!=0,(v.toBits&&&0xfffffffffffff)а+2^52, ((eF v.toBits)а:р)-1075⟩:iR).toReal:=by unfold eF at j⊢;have l:=(fq v).1;have m:=(fq v).2;have d:((v.toBits>>>52)&&&2047)а≠0:=λh=>j (χ.mp (by simpa using h)) unfold fv at e;unfold rv;rw[dl]at e⊢;rw[jr,ϖ _ _ _ _ l m e,AP d] simp only[show FloatFormat.binary64.fracWidth=52 from rfl,show FloatFormat.binary64.exponentBias=1023 from rfl, lb] congr 2<;>(try simp only[j0,jI])<;>ring lemma aV(z:Model kD):ofW (je z)=z:=by have h:z.toNatBits<2^32:=km z;rw[ofW,je,jn,kc,θ h];exact ku z lemma cA(w:iJ)(d:iG w≠255):jp (ofW w)=(sv w:ℝ)*(2:ℝ)^((iL w:р)-149):=by rw[ofW,jr,toDyadic_ofUInt32 w d];change (decodeD w).toReal=_;rw[<-ϛ,decodeD_toRat];push_cast;rfl lemma ej(w:iJ)(l:iG w≠255)(o:w&&&0x7FFFFFFF≠0):jp (ofW w)≠0:=by rw[cA w l];refine mul_ne_zero ?_ (zpow_ne_zero _ Г) have m:jd w≠0:=by rw[jd];split .rename_i d have e:=(cZ w).mp d;rw[aq]at e;have j:(aJ w)г≠0:=λh=>o (Ι.mp (h.trans UInt32.toNat_zero.symm)) rw[aq]at j;rw[fracOf];rw[c9];omega .omega rw[sv];split<;>simp[m] lemma ew(d h j:iR)(o:d.toReal<=h.toReal)(p:h.toReal<=j.toReal) (x:je (iI kD d)=je (iI kD j)) (v:iG (je (iI kD d))≠255) (y:je (iI kD d)&&&0x7FFFFFFF≠0) (w:|h.toReal|<=(2:ℝ)^(127:р)): je (iI kD h)=je (iI kD d):=by have e:=aV (iI kD d);have l:kk (iI kD d)=Л:=by rw[<-e,ofW,isFinite_ofUInt32];simpa using v have m:=Υ kD Б h (w.trans ((Ϣ kD М (2^23) 104 Б Б).trans' (by change _<=|(ifМ=Лthen(-1:ℝ)else 1)*((2^23:ℕ):ℝ)*(2:ℝ)^(104:ℤ)|;norm_num))) have u:iI kD j=iI kD d:=by rw[<-aV (iI kD j),<-x,e] have r:=Ϛ kD Б;have q:=jw kD o;have t:=jw kD p;rw[<-r d l,<-r h m]at q;rw[<-r h m,<-r j (by rw[u];exact l),u]at t rw[Model.eq_of_toReal_eq_of_nonzero m l (BI t q) (by rw[BI t q,<-e];exact ej _ v y)] lemma g0(x:п)(e:x<2^53)(d:x%2^29≠2^28): (ah (lF (x*2^10)))а=(x+2^28)/2^29:=by simp only[ah,ο,ξ,Α,iE, Θ (by rw[jo];omega:x*2^10>>29 if d<=26&&E-1195<253&&u-(g+1)<536870911-(g+g)&&r&&&8388607!=0 then ((b>>>63)<<<31)+r-0x255000000 else 4294967296 lemma rb(b:Д)(h:(((b&&&0x7FFFFFFFFFFFFFFF)+268435456)>>>29&&&8388607!=0)=Л): 2^28<=(b&&&0xfffffffffffff)а/\(b&&&0xfffffffffffff)а+2^28<2^52:=by simp only[Am,BU,<-χ,Α,ο,ξ, iE,iM,ι]at h⊢ rw[γ _ 63,γ _ 23]at h;rw[γ _ 52];omega lemma fk(h E f:Д)(q:hа<2^63)(o:Eа<2048)(p:fа<2^52) (d:h+1075-E<=26) (j:E-1195<253) (e:((f+268435456)&&&536870911)-(((1:Д)<<<(h+1075-E))+1)< 536870911-(((1:Д)<<<(h+1075-E))+((1:Д)<<<(h+1075-E)))) (m:2^28<=fа/\fа+2^28<2^52): Eа<=hа+1075/\hа+1075-Eа<=26/\1195<=Eа/\Eа<=1447/\ 2^(hа+1075-Eа)+1<=(fа+2^28)%2^29/\ (fа+2^28)%2^29+2^(hа+1075-Eа)<2^29/\ 2^(hа+1075-Eа)<=fа/\fа+2^(hа+1075-Eа)<2^52:=by simp only[κ,ν,Λ,ξ,Α, Η,iE,lP,jF]at d j e have l:(2^64-Eа+(hа+1075)%2^64)%2^64=hа+1075-Eа:=А;rw[l]at d e;have:=Μ (n:=2) Г d;rw[θ (by omega:_<64),γ _ 29]at e omega lemma gy(b:Д)(d:1195<=(eF b)а): (((b>>>63)<<<31)+(((b&&&0x7FFFFFFFFFFFFFFF)+268435456)>>>29)-0x255000000)а= bа/2^63*2^31+(((eF b)а-1085-110)*2^23+ (2^23+((b&&&0xfffffffffffff)а+2^28)/2^29)):=by simp only[eF,Λ,ξ,Η,ο, Α,iE,iM,ι,Ζ]at d⊢ rw[γ _ 11]at d⊢;rw[γ _ 63,γ _ 52];have:=b.toNat_lt;omega lemma cp(S:с)(hS:fv S)(h:Д)(hh:hа<2^63)(T:р) (y:|rv S-(T:ℝ)|<=(2:ℝ)^(hа:р)) (as:|(T:ℝ)|<=(2:ℝ)^(425:р)) (H:an S h<4294967296):T≠0/\(an S h)м=kj T (-298) false:=by unfold an at H⊢;dsimp only at H⊢ split;swap;. simp[*]at H rename_i v;simp only[Β,AG]at v;obtain⟨⟨⟨Y,Z⟩,c3⟩,c4⟩:=v have J:(if(S.toBits>>>63!=0)=true then 2^31 else 0)=S.toBitsа/2^63*2^31:=by simp only[ck,AG];have:=S.toBits.toNat_lt;split<;>omega obtain⟨d1,d2,B,e2,u1,u2,f1,f2⟩:=fk h (eF S.toBits) _ hh (fq S).1 (fq S).2 Y Z c3 (rb _ c4);have U:=gy S.toBits B;have Q:=aS S hS (λh0=>by rw[h0]at B;simp at B) rw[<-J]at U have I:(eF S.toBits-1085)а=(eF S.toBits)а-1085:=by rw[Λ];simp only[iE];omega generalize hW:UInt64.toUInt32 _=W;generalize (S.toBits>>>63!=0)=z at* generalize (eF S.toBits)а=d at* generalize hG:2^(hа+1075-d)=G at* generalize (S.toBits&&&0xfffffffffffff)а=j at* have o:Wг=(if z then 2^31 else 0)+((d-1085-110)*2^23+(2^23+(j+2^28)/2^29)):=by rw[<-hW,Ϡ,U];split<;>omega have x:∀N,j+2^52<=N+G->N<=j+2^52+G-> je (iI kD ⟨z,N*2^10,((d-1085:ℕ):ℤ)-298⟩)=W:=λN l r=>by have n:=Θ (show N*2^10by have:=av W;simp only[K,aq,o,iO]at this;split at this<;>omega have X:W&&&0x7FFFFFFF≠0:=λK=>by have:=aq W;simp only[aJ,K,o,lJ]at this;split at this<;>omega have p:=x (j+2^52-G) А А;have q:=x (j+2^52+G) А А;have E:Gby rw[Nat.cast_mul,Ad,Ad,Nat.cast_pow,jI,<-AB (2:ℝ) 10,<-AI AH, <-AI AH,(А:((10:ℕ):ℤ)+(((d-1085:ℕ):ℤ)-298)=(d:ℤ)-1075+-298)] have hu:(0:ℝ)<(2:ℝ)^((d:р)-1075):=В;have e:(0:ℝ)<(2:ℝ)^(-298:р):=В have u:|(ky T (-298)).toReal|<=(2:ℝ)^(127:р):=by rw[bo,AM,AJ e,show(127:ℤ)=425+-298 by norm_num,AI AH];gcongr rw[hU,Q]at y;generalize j+2^52=M at y p q E;have A:((M-G:ℕ):ℝ)=M-G:=kN E.le;have F:(G:ℝ)simp only[μ,AN,AV]at y<;>obtain⟨L,O⟩:=abs_le.mp y<;> have t:T≠0:=by rintro rfl;push_cast at L O;nlinarith only[L,O,F,hu] all_goals refine⟨t,?_⟩;simp only[kj,t,↓reduceIte] on_goal 2=>refine((ew _ _ _ ?_ ?_ (q.trans p.symm) (q▸V) (q▸X) u).trans q).symm refine((ew _ _ _ ?_ ?_ (p.trans q.symm) (p▸V) (p▸X) u).trans p).symm;all_goals simp only[bo,aD,μ,AN,AV,neg_mul,D,A];push_cast;nlinarith only[L,O,e] @[specialize]def ag(p:п->с)(n t:п)(a:с):с:= if tр)(e:р)(B:ℝ)(h:∀tintro _;simpa using d | succ t j=> intro l;rw[Ξ,<-add_assoc];push_cast;linarith[AT ((e:ℝ)+∑s∈iD t,(z s:ℝ)) (z t),j А,h t А] structure A8 where a0:с a1:с a2:с a3:с a4:с a5:с a6:с a7:с local instance:Inhabited A8:=⟨⟨0,0,0,0,0,0,0,0⟩⟩ @[inline]def A8.f(s:A8):п->с | 0=>s.a0 | 1=>s.a1 | 2=>s.a2 | 3=>s.a3 | 4=>s.a4 | 5=>s.a5 | 6=>s.a6 | _=>s.a7 structure A9 where a0:с a1:с a2:с a3:с a4:с a5:с a6:с a7:с o:т @[inline]def A9.s(R:A9):A8:=⟨R.a0,R.a1,R.a2,R.a3,R.a4,R.a5,R.a6,R.a7⟩ local instance:Inhabited A9:=⟨⟨0,0,0,0,0,0,0,0,0⟩⟩ @[inline]def mX(w:Е):Д:=(((w&&&8388607)<<<1)+16777216)к @[inline]def dX(w:Е):с:= (mX w).toInt64.toFloat*P2.uget (w>>>23)о (by rw[bu,am,bX];have:=w.toNat_lt;omega) def nW(w:т):т:=if expOf w=0 then w+16777216 else if expOf w=1 then w+8388608 else w def aR(x w:т):р:=Core.tm x (nW w) lemma fK(w:iJ):(nW w)г=wг+(2-(iG w)г)*2^23:=by have j:=av w;have:=aq w;have:=w.toNat_lt;rw[nW];by_cases d:iG w=0 .rw[d]at j;rw[if_pos d,kH,d];simp only[lJ,iO]at j⊢;omega by_cases e:iG w=1 .rw[e]at j;rw[AP d,if_pos e,kH,e];simp only[UInt32.toNat_one,iO]at j⊢;omega rw[AP d,AP e];have:(iG w)г≠0:=λh=>d (Ι.mp (h.trans UInt32.toNat_zero.symm)) have:(iG w)г≠1:=λh=>e (Ι.mp (h.trans UInt32.toNat_one.symm)) omega lemma cj(w:iJ):(iG (nW w))г=lX 2 (iG w)г/\jh (nW w)=jh w/\ jd (nW w)=2^23+wг%2^23/\iL (nW w)=lX 2 (iG w)г-1:=by have n:=fK w;have e:=av w;have:=aq w;have j:=av (nW w);have:=aq (nW w);have:=w.toNat_lt;have d:(iG (nW w))г=lX 2 (iG w)г:=А;refine⟨d,Ϥ.mpr (by rw[az,az];omega),?_,by rw[aT,d]⟩ rw[jd,fracOf];rw[AP λh=>by rw[h]at d;simp at d;omega,c9];omega lemma eg(w:iJ):nW w=w\/iL w=0/\iL (nW w)=1:=by by_cases h:(iG w)г<=1 .exact .inr ⟨by rw[aT];omega,by rw[(cj w).2.2.2];omega⟩ .exact .inl (Ι.mp (by rw[fK];omega)) lemma fI(w:Е):(mX w)а=2*jd (nW w):=by unfold mX;rw[(cj w).2.2.1,ϟ,kH,jH,c9];simp only[iO,iM,Ζ];omega lemma gA(w:Е):fv (dX w)/\rv (dX w)=(sv (nW w):ℝ)*2^iL (nW w):=by obtain⟨-,d,-,e⟩:=cj w exact dG 2 2 P2 cB _ _ w _ AO (fI w) d (by rw[e,(А:lX 2 (iG w)г-1=(iG w)г-2+1),Ay];push_cast;ring) lemma uk{i k:х}{S:п}(d:kб<8)(h:iб+8<=S)(e:S<2^32): (i+k)б>>24⟩ termination_by nб-tб decreasing_by have:=β.mp h;rw[ac h];omega lemma eV(W:у iJ)(X:Ж)(d n:х)(L:Wв<2^32/\Xе<2^32) (J:dб+nб<=Wв) (z r:п) (Q:r<8): ∀m (t i:х) (y:iб+8*(nб-tб)<=Xе) (j l p q u v w x:с) (o:iJ), nб-tб=m->iб=z+8*tб-> (λR:A9=>R.s.f r= ag (λs=>X.data[z+8*s+r]!*dX W[dб+s]!) nб tб (A8.f ⟨j,l,p,q,u,v,w,x⟩ r)/\ (∀s,tб<=s->s(iG W[dб+s]!)г<=R.oг)/\ oг/2^24<=R.oг) (k8 W X d n L J t i y j l p q u v w x o):=by intro m;induction m<;>intro t i y j l p q u v w x o O F .rw[k8,Ax (by rw[β];omega),ag,AP А] exact⟨Н,λs G A=>А,(dc o).ge⟩ rename_i M;have:=ς;have D:tбM (t+1) (i+8) y j l p q u v w x o (by rw[ac h];omega) (by rw[ac h,H,F];ring) refine⟨I.1.trans ?_,λs G A=>?_,Ae (Ϸ (by rw[jT];omega)) I.2.2⟩ .rw[ac h];congr 1 have N:∀(c:х) (K:cб<8) (B:(i+c)бby rw[ug,af А,F] interval_cases r<;> (simp only[A8.f];rw[N _ (by simp only[iV];omega),aC,E];simp only[iV]) rcases eq_or_ne s tбwith rfl | e .exact(eS _).trans_le ((Ϸ (by rw[jT,aC,E];omega)).trans I.2.2) exact I.2.1 s (by rw[ac h];omega) A lemma fW(Y:Ж)(v:с):(Y.push v)е=Yе+1:=by rcases Y with⟨d⟩;simp[FloatArray.push,iX] lemma dy(Y:Ж)(i:п)(v:с):(Y.set! i v)е=Yе:=by rcases Y with⟨d⟩;simp[j9,iX] lemma sg(Y:Ж)(i q:п)(v:с)(e:qsimp[*,AL] @[specialize]def aM(f:п->с)(N:п)(Y:Ж):Ж:= if Yес)(N:п):∀k (Y:Ж),N-Yе=k->Yе<=N-> (aM f N Y)е=N/\(∀qq(aM f N Y).data[q]! =f q:=by intro k;induction k<;>intro Y t r .rw[aM,AP А];exact⟨А,λq _=>Н,λq j d=>А⟩ rename_i p;rw[aM,if_pos А];have u:=fW Y (f Yе);have⟨m,h,o⟩:=p (Y.push (f Yе)) А А;refine⟨m,λq l=>by rw[h q А,pg _ _ _ А,if_pos l],λq j d=>?_⟩ rcases eq_or_ne q Yеwith rfl | e .rw[h _ А,pg _ _ _ А,AP (Ar _)] exact o q А d lemma fB(v:с)(h:(eF v.toBits)а<2047):fv v:=by rw[fv];rw[dl];have e:=(fq v).1;have j:=(fq v).2;rw[Model.isFinite_ofFields _ _ _ _ e j];have d:FloatFormat.binary64.expAllOnesNat=2047:=Б;rw[eF]at h;rw[show FloatFormat.binary64.encoding=.ieee fromН,d,Am,BU];omega lemma bm(v:с)(j:fv v):|rv v|<(2:ℝ)^(((eF v.toBits)а:р)-1022):=by have d:∀(m k:ℕ) (e f:ℤ),m<2^k->k+e<=f->(m:ℝ)*2^e<2^f:=λm k e f h l=> (Ag (by exact_mod_cast h:(m:ℝ)<2^k) (zpow_pos two_pos e)).trans_le (by rw[<-AB,<-AI AH];exact zpow_le_zpow_right₀ Г l) unfold rv eF;unfold fv at j;rw[dl]at j⊢;rw[jr,ϖ _ _ _ _ (fq v).1 (fq v).2 j];have:=(fq v).2;split_ifs with o<;>simp only[Model.Dyadic.abs_toReal] .simp;positivity .exact d _ 52 _ _ this (by rw[o];decide) .exact d _ 53 _ _ (by simp only[iF,lb];omega) (by simp[iF];omega) lemma ia(x y:с)(m:fv x)(o:fv y)(t:fv (x+y))(E:р)(e:-1074<=E)(j:E<=971) (h:|rv (x+y)|<(2:ℝ)^E):|rv x+rv y|<(2:ℝ)^E:=by have l:=dV x y m o;have r:=kf _ _ Б m o (l▸t);unfold rv at h⊢;rw[l,r,abs_lt]at h;have q:=rx ⟨false,1,E⟩ Г e (by simp[aD];exact zpow_le_zpow_right₀ Г j) have p:=rx ⟨true,1,E⟩ Г e (by simp[aD];exact zpow_le_zpow_right₀ Г j) simp only[aD,μ,AN,AV,lH,Aj,neg_mul]at q p exact abs_lt.2 ⟨lt_of_not_ge λd=>by linarith[jw iF d], lt_of_not_ge λd=>by linarith[jw iF d]⟩ @[specialize]def sT(p:п->с)(n t:п)(a:с)(m:Д):с×Д:= if trename_i h<;>rw[ν]at h<;>omega lemma eX(p:п->с)(n:п):∀k t a m,n-t=k->mа<=(sT p n t a m).2а:=by intro k;induction k with | zero=>intro t a m h;rw[sT,AP А] | succ k d=> intro t a m h;rw[sT,if_pos А];dsimp only;have:=d (t+1) (a+p t) (if mс)(z:п->р)(r:р)(n K:п)(v:1<=K)(w:K<=1993) (y:∀tt<=n->fv a-> |rv a-((r:ℝ)+∑s∈iD t,(z s:ℝ))|<=t*(2:ℝ)^((K:р)-1076)-> (sT p n t a M).2а<=K-> fv (sT p n t a M).1/\ |rv (sT p n t a M).1-((r:ℝ)+∑s∈iD n,(z s:ℝ))|<=n*(2:ℝ)^((K:р)-1076):=by intro m;induction m<;>intro t a M D E j h l .obtain rfl:t=n:=А rw[sT,AP (Ar _)];exact⟨j,h⟩ rename_i A;have d:tlinarith only[e.1,e.2,h.1,h.2,B] lemma cw(n:п)(d e:п->iJ)(j:al n d e)(S:с)(o:fv S)(h:Д) (r:hа<2^63) (p:|rv S-(ae n d e:ℝ)|<=(2:ℝ)^(hа:р)) (m:|(ae n d e:ℝ)|<=(2:ℝ)^(425:р)) (q:an S h<4294967296): (an S h)м=jP n d e:=by have⟨l,t⟩:=cp S o h r _ p m q;rw[t,bg n d e j l] def aY(A:у т)(i:х)(m:Е):Е:= if h:i>>23)&&&255 aY A (i+1) (if m mг<=(aY A i m)г/\∀q,iб<=q->q(iG A[q]!)г<=(aY A i m)г:=by intro k;induction k<;>intro i m v .have h:¬iby have:=aF h;omega rw[aY,Ax h];exact⟨AO,λq j d=>А⟩ rename_i u;have h:iby split<;>rename_i l<;>rw[ϯ]at l<;>omega have⟨r,t⟩:=u (i+1) (if m<(A.uget i (aF h)>>>23)&&&255 then(A.uget i (aF h)>>>23)&&&255 else m) (by rw[ac h];omega) rw[p]at r;refine⟨А,λq j d=>?_⟩ rcases eq_or_ne q iбwith rfl | e .rw[<-aC A i (aF h)];rw[iG];omega exact t q (by rw[ac h];omega) d lemma dj(A:у iJ)(l:Aвby rw[e]at d;simp at d j;omega,by rw[aT];omega⟩ @[inline]def ai(b:ф)(x:с)(w:Е):с:= if b then(x*P2.uget (w>>>23)о (by rw[bu,am,bX];have:=w.toNat_lt;omega))*(mX w).toInt64.toFloat else x*dX w lemma el(b:ф)(x w:Е)(y:iG x≠255)(_:iG w≠255): fv (ai b (dw x) w)/\rv (ai b (dw x) w)=aR x w:=by obtain⟨l,o⟩:=au x y;obtain⟨-,-,m,r⟩:=cj w;have:=a9 x;have:=a9 w;have:=aT x;unfold ai aR tm;split .obtain⟨e,σ,v,t,j⟩:=qV 2 P2 cB w (by rw[bu,am,bX];have:=w.toNat_lt;omega) obtain⟨p,q⟩:=mV _ _ (fI w) (by rw[m];omega) have u:iL (nW w)=(iG w)г-2+1:=by rw[r];omega have h:(sv x*σ)й<2^24:=by rw[Ϭ,t,jz];exact cn x have d:(sv x*σ*((2*jd (nW w):п):р))й<2^49:=by rw[Ϭ];calc _<2^24*2^25:=jS h (by rw[m];simp;omega) _=2^49:=Г have a:=bf _ _ l e (sv x*σ) (iL x+((iG w)г-2):п) (by rw[o,j,AB,AK];push_cast;ring) (lt_trans h Г) А (cm 24 _ 971 А AO _ h) have b:=bf _ _ a.1 p (sv x*σ*((2*jd (nW w):п):р)) (iL x+((iG w)г-2):п) (by rw[a.2,q];push_cast;ring) (lt_trans d Г) А (cm 49 _ 971 А AO _ d) exact⟨b.1,by rw[b.2,u,<-v _ (cj w).2.1,AB];push_cast;ring⟩ .obtain⟨e,j⟩:=gA w have d:(sv x*sv (nW w))й<2^48:=by rw[Ϭ];exact(jS (cn x) (cn _)).trans_eq Г have:=bf _ _ l e (sv x*sv (nW w)) (iL x+iL (nW w):п) (by rw[o,j,AB,AK];push_cast;ring) (lt_trans d Г) А (cm 48 _ 971 А AO _ d) exact⟨this.1,by rw[this.2,AB];push_cast;ring⟩ @[specialize]def aP(k:п->ф)(p:п->с)(n t:п)(a:с):с:= if t simp(config:={contextual:=Л}) [lE,i6,ji,tm] lemma dP(k:п->ф)(p:п->с)(z:п->р)(e:р)(P L n:п) (E:∀tz t=0) (F:∀tt<=n->fv a-> |rv a-((e:ℝ)+∑s∈iD t,(z s:ℝ))|<=t*((2:ℝ)^(P+L)*2^(-54:р))-> fv (aP k p n t a)/\ |rv (aP k p n t a)-((e:ℝ)+∑s∈iD n,(z s:ℝ))|<=n*((2:ℝ)^(P+L)*2^(-54:р)):=by have x:(2:ℝ)^L*2^L*2^(-54:р)<=1:=by rw[<-AK,<-AB,<-AI AH];exact Ai Г (by push_cast;omega) intro m;induction m<;>intro t a H I h q .obtain rfl:t=n:=А rw[aP,AP (Ar _)];exact⟨h,q⟩ rename_i r;have d:tlinarith have⟨v,u⟩:=eQ a (p t) h w (P+L) А (by rw[AK,abs_lt];constructor<;>linarith) refine r (t+1) (a+p t) А А v ?_;push_cast[Ξ,AK,AZ]at u⊢;constructor<;>linarith lemma cU(a b:iJ)(A B:п)(m:iL a<=A)(o:iL b<=B): |(tm a b:ℝ)|<=(2:ℝ)^(48+A+B):=by have d:=aQ a;have h:=aQ b have e:(tm a b)й<=2^(48+A+B):=by rw[tm];rw[Ϭ,Ϭ,Int.natAbs_pow];rw[ϳ]at d h;have j:(sv a)й<=2^24:=А;have l:(sv b)й<=2^24:=А calc (sv a)й*(sv b)й*(2:р)й^(iL a+iL b) <=2^24*2^24*2^(A+B):=by apply li (li j l);exact Μ Г А _=2^(48+A+B):=by rw[<-AK,<-AK];congr 1;omega rw[<-ϊ,ϳ];exact_mod_cast e @[inline]def s8(Y:Ж)(o:х)(e0 e1 e2 e3 e4 e5 e6 e7:с):Ж:= (((((((Y.set! oб e0).set! (o+1)б e1).set! (o+2)б e2).set! (o+3)б e3).set! (o+4)б e4).set! (o+5)б e5).set! (o+6)б e6).set! (o+7)б e7 lemma dO(Y:FloatArray)(o:х)(e:п->с)(h:oб+8?_⟩ simp(disch:=(try simp only[dy,Al]);omega) only[s8,sg,af,iV] split_ifs<;>first | rfl | omega | (congr 1;omega) lemma gD(X:у iJ)(k:п):X.getD k 0=X[k]!:=by rw[Array.getD];split<;>rename_i h .rw[AL X k h];rfl .rw[A0 X k h];rfl @[inline]def xr(X:у т)(q st:х)(r:п):с:=dw (X.getD (q+rд*st)б 0) def bx(X:у т)(st s:х):п->х->х->Ж->Ж | 0,_,_,Y=>Y | k+1,q,o,Y=>bx X st s k (q+s) (o+8) (s8 Y o (xr X q st 0) (xr X q st 1) (xr X q st 2) (xr X q st 3) (xr X q st 4) (xr X q st 5) (xr X q st 6) (xr X q st 7)) lemma dF(X:у iJ)(d s:х):∀k (q o:х) (Y:Ж), qб+k*sб+8*dб+oб+8*koб+8*k<=Yе-> (bx X d s k q o Y)е=Yе/\(∀pr<8->(bx X d s k q o Y).data[oб+8*τ+r]! =dw X[qб+τ*sб+r*dб]!:=by intro k;induction k with | zero=>intro q o Y _ _;exact⟨Н,λ_ _=>Н,λτ r h=>absurd h А⟩ | succ k z=> intro q o Y w B;rw[ώ]at w;have:=ς;have:=ϡ;obtain⟨t,u⟩:=dO Y o (xr X q d) А;have v:(q+s)б=qб+sб:=af А;have j:(o+8)б=oб+8:=by rw[af (by simp;omega)];simp obtain⟨x,e,y⟩:=z (q+s) (o+8) _ А (by rw[t];omega) rw[j]at e;rw[v,j]at y;refine⟨by rw[bx,x,t],λp D=>by rw[bx,e p А,u p А,AP А],λτ r A l=>?_⟩ rw[bx];rcases τ with _ | τ .have m:(rд*d)б=r*dб:=by rw[kV,aa А,θ (by have:=ψ dб l.le;omega)] rw[e _ А,u _ А,if_pos А,(А:oб+8*0+r-oб=r),xr, af (by rw[m];have:=ψ dб l.le;omega),m,gD];simp .grind def ZT:у Ж:=Aw (n:=10) λk=>⟨AY (2^(kи+7)) 0⟩ def zT(n:п):Ж:= let k:=BG (8*n)+1-7 if k<10 then ZT[k]!else⟨AY (8*n) 0⟩ lemma iA(n:п):8*n<=(zT n)е/\((zT n)е=8*n\/(zT n)е<=2^16):=by unfold zT;dsimp only;split .rw[AL ZT _ (by simp[ZT];omega)] simp only[ZT,Ν,iX,ϧ] exact⟨(Ϝ (n:=8*n)).le.trans (Μ Б А), .inr (Μ Б А)⟩ .simp[iX] def bt(X:у т)(st s n b:п)(Z:Ж):Ж:= if b+n*s+s+8*st+8*n<=4294967295 then bx X stд sд n bд 0 Z else⟨Aw (n:=8*n) λp=>dw X[b+pи/8*s+pи%8*st]!⟩ lemma dg(X:у iJ)(d s n b:п)(Z:FloatArray)(m:8*n<=Zе): 8*n<=(bt X d s n b Z)е/\((bt X d s n b Z)е=Zе\/(bt X d s n b Z)е=8*n)/\ ∀τ r,τr<8->(bt X d s n b Z).data[8*τ+r]! =dw X[b+τ*s+r*d]!:=by unfold bt;split .have:=ς have:=dF X dд sд n bд 0 Z simp only[aa (by omega:dby rw[<-l τ r e h,ϥ]⟩ .refine⟨by simp[iX],.inr (by simp[iX]),λτ r e h=>?_⟩ rw[AL _ _ (by simp;omega),Ν] dsimp only;rw[(А:(8*τ+r)/8=τ),(А:(8*τ+r)%8=r)] def eG(t:ф)(X:у т)(R n rb:п)(Z:Ж):Ж:= bt X (if t then 1 else n) (if t then R else 1) n (if t then 8*rb else 8*rb*n) Z structure XB where xt:Ж c0:Д c1:Д c2:Д c3:Д c4:Д c5:Д c6:Д c7:Д deriving Inhabited @[inline]def rX(X:у т)(i:х):с:=if h:iД | 0=>x.c0 | 1=>x.c1 | 2=>x.c2 | 3=>x.c3 | 4=>x.c4 | 5=>x.c5 | 6=>x.c6 | _=>x.c7 @[inline]def XS.g(x:XS):п->с | 0=>x.a0 | 1=>x.a1 | 2=>x.a2 | 3=>x.a3 | 4=>x.a4 | 5=>x.a5 | 6=>x.a6 | _=>x.a7 def ce(X:у т)(st s s2 s3 s4 s5 s6 s7:х):п->х->х->Ж-> с->с->с->с->с->с->с->с->XS | 0,_,_,Y,a0,a1,a2,a3,a4,a5,a6,a7=>⟨Y,a0,a1,a2,a3,a4,a5,a6,a7⟩ | k+1,q,o,Y,a0,a1,a2,a3,a4,a5,a6,a7=> let v0:=rX X q let v1:=rX X (q+st) let v2:=rX X (q+s2) let v3:=rX X (q+s3) let v4:=rX X (q+s4) let v5:=rX X (q+s5) let v6:=rX X (q+s6) let v7:=rX X (q+s7) ce X st s s2 s3 s4 s5 s6 s7 k (q+s) (o+8) (wF (wF (wF (wF (wF (wF (wF (wF Y o v0) (o+1) v1) (o+2) v2) (o+3) v3) (o+4) v4) (o+5) v5) (o+6) v6) (o+7) v7) (a0+v0.abs) (a1+v1.abs) (a2+v2.abs) (a3+v3.abs) (a4+v4.abs) (a5+v5.abs) (a6+v6.abs) (a7+v7.abs) @[inline]def cE(F a:с):Д:=let e:=eF (F*a).toBits;if 1078с)(bpf:Unit->с)(fbk:Unit->т):т:= let r:=sT p n 0 (bpf ()) 0 let c:=if 1<=r.2а/\r.2а<=1993/\1076<=r.2а+L then an r.1 (r.2а+L-1076)жelse 4294967296 if c<4294967296 then act relu cмelse fbk () @[inline]def tf(relu:ф)(S:с)(hh:Д)(sl:Unit->т):т:= let c:=an S hh if c<4294967296 then act relu cмelse sl () @[inline]def tw(relu:ф)(S:с)(hh:Д)(L n:п)(p:п->с)(bpf:Unit->с) (fbk:Unit->т):т:=tf relu S hh λ_=>tS relu L n p bpf fbk @[inline]def hG(e:т)(ix ib L:п):ф×Д:= let p:=48+ix+max (eг-1) 55 (decide (e<255/\p+L<=425),(max p ib+2*L-54)ж) @[inline]def tG(relu:ф)(S:с)(e:т)(ix ib L:п)(sl fb:Unit->т):т:= let h:=hG e ix ib L if h.1 then tf relu S h.2 sl else fb () lemma iu(h:ф)(n:п)(d e:п->iJ)(p:п->с)(l:Unit->с)(u:Д)(P L:п) (o:Unit->iJ) (H:∀sA s I.le) (A n AO) n AO).trans ?_ calc ((n:ℝ)+1)*2^P<=2^L*2^P:=by gcongr;exact_mod_cast(by omega:n+1<=2^L) _<=2^425:=by rw[<-AK];exact AC Г А rw[tw,tf,tS];split_ifs with F t x<;>try exact G .exact congrArg _ (cw _ _ _ j _ D u (by rw[y];omega) w q F) .obtain⟨v,m⟩:=cT _ _ (tm (d n) (e n)) n _ t.1 t.2.1 H n 0 _ 0 rfl А r.1 (by simp[r.2]) AO rw[<-B]at m refine congrArg _ (cw _ _ _ j _ v _ ?_ (m.trans ?_) q x)<;> rw[ϱ,Θ (by rw[jo];omega)] .omega refine(AA (by exact_mod_cast(by omega:n<=2^L):(n:ℝ)<=2^L) В).trans_eq ?_ rw[<-AB,<-AI AH];congr 1;omega .exact absurd ‹_› Б lemma eZ(l:ф)(n j:п)(o:п->iJ)(W b:у iJ)(p q:п->с)(e:iJ) (u D L E:п) (r:Unit->iJ) (k:п->ф) (A:∀s(iG W[j*n+s]!)г<=eг) (hf:eг<255->∀s(iG W[j*n+s]!)г<255) (G:iG b[j]!≠255/\iL b[j]!<=E) (as:174+E<=D) (F:n+2<=2^L) (t:L<=27) (K:D+L<=425) (hp:∀sfv (p s)/\rv (p s)=tm (o s) W[j*n+s]!) (hq:∀sfv (q s)/\rv (q s)=aR (o s) W[j*n+s]!) (z:∀s∀v,tm (o s) v=0) (M:r ()=act l (jP (n+1) (λs=>if sif stS l L n p (λ_=>dw jN*dw b[j]!) r) r= act l (jP (n+1) (λs=>if sif s UInt32.ne_of_lt (by cases m:k s;exacts[(N s d m).trans_lt J,hf J s d m]) generalize Y:lX (48+u+lX (eг-1) 55) D=P;have y:(P+2*L-54)жа=_:=Θ (by rw[jo];omega) have Q:∀sby cases m:k s exacts[(cU _ _ u (eг-1) (A s d).2 ((aT _).trans_le (Nat.sub_le_sub_right (N s d m) 1))).trans (AC Г А),by simp[z s d m,pow_nonneg]] have H:|(tm jN b[j]!:ℝ)|<=2^P:=(cU _ _ 126 E Б G.2).trans (AC Г А) have w:=dt jN b[j]! Б G.1 have⟨S,O⟩:=dP k q (λs=>aR (o s) W[j*n+s]!) (tm jN b[j]!) P L n (λs d=>hq s d (x s d)) (λs d h=>z s d h _) (λs d=>by rw[aR];rcases eg W[j*n+s]!with h | ⟨-,h⟩ exacts[by rw[h];exact Q s d,(cU _ _ u 1 (A s d).2 h.le).trans (AC Г А)]) H F t А n 0 _ rfl n.zero_le w.1 (by simp[w.2]) have X:∀c≤1,(2:ℝ)^(48+u+c)<=2^((P:р)+-54):=λc _=>by rw[<-AB];exact zpow_le_zpow_right₀ Г А have V:=bD n (λs=>tm (if sby simp only[d,AV];unfold aR;rcases eg W[j*n+s]!with h | ⟨U,B⟩ .simp[h];positivity .push_cast exact(abs_sub _ _).trans (BA ((cU _ _ u 0 (A s d).2 U.le).trans (X 0 А)) ((cU _ _ u 1 (A s d).2 B.le).trans (X 1 AO)))) (by simp;positivity) n AO have I:(0:ℝ)<2^P*2^(-54:р):=В refine iu l n _ _ p _ _ P L r (λs d=>by simpa[d]using hp s d (x s d)) (by simpa using w) (λs _=>by split;exacts[⟨(A s ‹_›).1,x s ‹_›⟩,⟨Б,G.1⟩]) (λs _=>by split;exacts[Q s ‹_›,H]) F t А y M _ S ?_ rw[ap,ae,y,(А:((P+2*L-54:п):р)=P+L+L+(-54))] have B:=sub_nonneg.mpr (by exact_mod_cast F:(n:ℝ)+2<=2^L) push_cast[AI (two_ne_zero' ℝ),AB,Ar,AK,ϙ,AZ]at O V⊢;constructor<;>linarith[AW B (mul_pos I (pow_pos two_pos L)).le,AW B I.le] lemma gg(X:Ж)(i:п):X.get! i=X.data[i]!:=by rcases X with⟨d⟩;rfl lemma f8(v:с)(r:п):A8.f ⟨v,v,v,v,v,v,v,v⟩ r=v:=by unfold A8.f;split<;>rfl @[specialize]def l2(U V:п)(f:п->п->у т->у т)(u v:п)(a:у т): у т:= if uxb.get! (8*s+c)*dw W[o+s]!) (λ_=>dw oneW*dw b[j]!) λ_=>aj n relu X W b xo st j @[inline]def bh(t:ф)(R n:п)(relu:ф)(X W b:у т)(XT:у XB)(e:т)(c hb:Д) (L:п) (ok:ф) (q:х) (i:Unit->п) (j:п) (a:у т) (S:с):у т:= if hq:ok/\qsN n relu X W b XT L (i ()) j (if t then i ()else i ()*n) (if t then R else 1)) else aj n relu X W b (if t then i ()else i ()*n) (if t then R else 1) j) (aF hq.2) else a @[noinline]def w8(tt:ф)(R ow nn:п)(relu:ф)(Xw Ww bw:у т)(XT:у XB)(xb:XB)(hb:Д) (L rb oo:п) (e:т) (a0 a1 a2 a3 a4 a5 a6 a7:с) (acc:у т):у т:= let r:=8*rb let v:=R-r let q0:=(if tt then oo*R+r else r*ow+oo)д let st:=(if tt then 1 else ow)д bh tt R nn relu Xw Ww bw XT e xb.c7 hb L (decide (7r+7) oo (bh tt R nn relu Xw Ww bw XT e xb.c6 hb L (decide (6r+6) oo (bh tt R nn relu Xw Ww bw XT e xb.c5 hb L (decide (5r+5) oo (bh tt R nn relu Xw Ww bw XT e xb.c4 hb L (decide (4r+4) oo (bh tt R nn relu Xw Ww bw XT e xb.c3 hb L (decide (3r+3) oo (bh tt R nn relu Xw Ww bw XT e xb.c2 hb L (decide (2r+2) oo (bh tt R nn relu Xw Ww bw XT e xb.c1 hb L (decide (1r+1) oo (bh tt R nn relu Xw Ww bw XT e xb.c0 hb L (decide (0r) oo acc a0) a1) a2) a3) a4) a5) a6) a7 def bO(tt:ф)(R ow nn:п)(relu:ф)(Xw Ww bw:у т)(XT:у XB)(xb:XB)(hb:Д)(L rb oo:п) (W:у т) (X:Ж) (ou n:х) (hs:Wв<2^32/\Xе<2^32) (hW:ouб+nб<=Wв) (t i:х) (hi:iб+8*(nб-tб)<=Xе) (a0 a1 a2 a3 a4 a5 a6 a7:с) (o:т) (acc:у т):у т:= if h:t>>24) a0 a1 a2 a3 a4 a5 a6 a7 acc termination_by nб-tб decreasing_by have:=β.mp h;rw[ac h];omega def ch(t:ф)(R n ow:п)(relu:ф)(X W b:у т)(L:п) (hs:Wв<2^32/\8*n<2^32) (hW:ow*n<=Wв) (XT:у XB) (xb:XB) (hb:Д) (xt BP:Ж) (hx:8*n<=xtе/\xtе<=4294967295) (rb o:п) (a:у т):у т:= if h:oaG t X R n rbи Z) (ib+L-50)ж (aM (λo=>dw oneW*dw b[o]!) ow (An ow)) 0 (AY (R*ow) 0) else Aw (n:=R*ow) λq=> aj n relu X W b (if t then qи%R else qи/ow*n) (if t then R else 1) (if t then qи/R else qи%ow) lemma fZ(z:ℝ):|BH iF z-z|<=(2:ℝ)^(-53:р)*|z|+2^(-1075:р):=by by_cases h:|z|<(2:ℝ)^(-1021:р) .refine(re z (-1021) AO h).trans ?_ rw[div_eq_mul_inv,<-zpow_sub_one₀ AH];norm_num .have l:0< |z|:=lt_of_lt_of_le В (not_lt.1 h) have d:=lj (b:=2) Г l;have e:=kv (b:=2) Г |z| simp only[jI]at d e have j:(-1021:р)<=kg 2 |z|+1:=by by_contra m;linarith[zpow_le_zpow_right₀ (by norm_num:(1:ℝ)<=2) (by omega:Int.log 2 |z|+1<=-1021)] refine(re z _ j e).trans ?_ rw[div_eq_mul_inv,<-zpow_sub_one₀ AH,show kg 2 |z|+1-53-1=-53+kg 2 |z| by ring, AI AH] linarith[AE d (by positivity:(0:ℝ)<=2^(-53:р)), show(0:ℝ)<=2^(-1075:р) by positivity] lemma ii(x y:с)(h:fv x)(j:fv y)(d:|rv x+rv y|<=(2:ℝ)^(970:р)): fv (x+y)/\|rv (x+y)-(rv x+rv y)|<=(2:ℝ)^(-53:р)*|rv x+rv y|+2^(-1075:р):=by have⟨f,e⟩:=dk x y h j (d.trans ((zpow_le_zpow_right₀ Г Г).trans (pm 971 AO)));exact⟨f,by rw[e];exact fZ _⟩ lemma ij(x y:с)(h:fv x)(j:fv y)(d:|rv x*rv y|<=(2:ℝ)^(971:р)): fv (x*y)/\|rv (x*y)-rv x*rv y|<=(2:ℝ)^(-53:р)*|rv x*rv y|+2^(-1075:р):=by have⟨f,e⟩:=d7 x y h j d;exact⟨f,by rw[e];exact fZ _⟩ lemma eM(v:с)(d:fv v)(e:eF v.toBits=0): rv v=(⟨v.toBits>>>63!=0,(v.toBits&&&0xfffffffffffff)а,-1074⟩:iR).toReal:=by rw[eF]at e;rw[fv]at d;rw[rv];rw[dl]at d⊢;rw[jr,ϖ _ _ _ _ (fq v).1 (fq v).2 d,ite_eq_left (by rw[e];rfl)] split_ifs with h .dsimp only;rw[aD,aD,h];simp .rfl lemma cf(v:с)(e:fv v): |rv v|<(2:ℝ)^(((eF v.toBits)а:р)-1022):=by have h:=(fq v).2;by_cases d:eF v.toBits=0 .rw[eM v e d,aD,show(eF v.toBits)а=0 by rw[d];rfl, show(2:ℝ)^(((0:п):р)-1022)=2^52*2^(-1074:р) by rw[show(2:ℝ)^52=2^(52:р) by norm_num,<-AI AH];norm_num] have:((v.toBits&&&0xfffffffffffff)а:ℝ)<2^52:=by exact_mod_cast h split<;>simp only[neg_mul,BM,AM,abs_zpow,BL,lK]<;> exact Ag this В .rw[aS v e d,aD,show(2:ℝ)^(((eF v.toBits)а:р)-1022)= 2^53*2^(((eF v.toBits)а:р)-1075) by rw[show(2:ℝ)^53=2^(53:р) by norm_num,<-AI AH];congr 1;ring] have:(((v.toBits&&&0xfffffffffffff)а+2^52:п):ℝ)<2^53:=by exact_mod_cast(by omega:(v.toBits&&&0xfffffffffffff).toNat+2^52<2^53) split<;>simp only[neg_mul,BM,AM,abs_zpow,BL,lK]<;> exact Ag this В lemma f6(p:п->с)(z:п->ℝ)(d:ℝ)(n:п)(J:∀tt<=n->fv a-> |rv a-(d+∑s∈iD t,z s)|<= t*((2:ℝ)^(-53:р)*(1+2^(-20:р))*(|d|+∑s∈iD t,|z s|)+2^(-1074:р))-> fv (ag p n t a)/\|rv (ag p n t a)-(d+∑s∈iD n,z s)|<= n*((2:ℝ)^(-53:р)*(1+2^(-20:р))*(|d|+∑s∈iD n,|z s|)+2^(-1074:р)):=by have l:(2:ℝ)^(970:р)=2^(968:р)*4:=by rw[show(970:р)=968+2 by norm_num,AI AH];norm_num have L:(2:ℝ)^(-1075:р)=2^(-1074:р)/2:=by rw[show(-1074:р)=-1075+1 by norm_num,BR AH];ring have u:(4294967296:ℝ)*2^(-1074:р)<=2^(968:р):=by rw[show(4294967296:ℝ)=2^(32:р) by norm_num,<-AI AH] exact zpow_le_zpow_right₀ Г Г have o:(0:ℝ)<2^(-1074:р):=В;intro m;induction m with | zero=> intro t a I K q h;obtain rfl:t=n:=А;rw[ag,AP (Ar _)];exact⟨q,h⟩ | succ m M=> intro t a I K q h;have j:tAF (z i)) have x:=(AT d _).trans (BA AO (ϣ z (iD (t+1))));simp only[Ξ]at w x;have y:=AT (rv a-(d+∑s∈iD t,z s)) (d+(∑s∈iD t,z s+z t)) rw[show rv a-(d+∑s∈iD t,z s)+(d+(∑s∈iD t,z s+z t))=rv a+rv (p t) by rw[A];ring]at y have e:(t:ℝ)<=4294967296:=by exact_mod_cast(by omega:t<=2^32) have N:=AA e (AF d);have O:=AA e (Ϩ λi (_:i∈iD t)=>AF (z i)) have W:=AA e (AF (z t));have Q:=AA e o.le;have r:0<=∑s∈iD t,|z s|:=Ϩ λi _=>AF (z i) have X:=AW (kW t:(0:ℝ)<=t) (AF (z t));have S:=AF d;have U:=AF (z t) have F:|rv a-(d+∑s∈iD t,z s)|<=1/9007199254740992*(1+1/1048576)*(t*|d|)+ 1/9007199254740992*(1+1/1048576)*(t*∑s∈iD t,|z s|)+t*2^(-1074:р):=h.trans_eq (by ring) obtain⟨D,B⟩:=ii a (p t) q E (by rw[l];generalize (2:ℝ)^(968:р)=H at*;generalize (2:ℝ)^(-1074:р)=η at* linarith only[y,F,x,w,G,N,O,Q,u,r,S,U,o]) refine M (t+1) (a+p t) А А D ?_;rw[L,show(2:ℝ)^(-53:р)=1/9007199254740992 by norm_num]at B have v:=AT (rv (a+p t)-(rv a+rv (p t))) (rv a-(d+∑s∈iD t,z s)) rw[show rv (a+p t)-(rv a+rv (p t))+(rv a-(d+∑s∈iD t,z s))= rv (a+p t)-(d+(∑s∈iD t,z s+z t)) by rw[A];ring]at v simp only[Ξ];generalize (2:ℝ)^(-1074:р)=η at* calc _<=1/9007199254740992*(1+1/1048576)*(t*|d|+t*∑s∈iD t,|z s|+t*|z t|+ (|d|+(∑s∈iD t,|z s|+|z t|)))+t*η+η:=by linarith _=_:=by push_cast;ring lemma fc(m:Float.Model):(kI m.unpack.abs).unpack=m.unpack.abs:=by have d:(kI m.unpack).unpack=m.unpack:=by have:=Model.toFloatModel_ofFloatModel m;conv_rhs=>rw[<-this] rfl generalize m.unpack=u at d⊢;rw[kI,Float.Model.unpack,UInt64.toBitVec_ofBitVec]at d⊢;cases u with | notANumber=>exact d | finite s j e h=> simp only[i4,jj,jm]at d⊢;split_ifs at d⊢<;> simp only[iN,ϑ, ϒ,jO]at d⊢<;> split_ifs at d⊢<;>simp_all | _=> simp only[i4,jj,jm, lq,iN, ϑ,ϒ, jO]at d⊢ split_ifs at d⊢<;>simp_all lemma gh(v:с)(d:fv v):fv v.abs/\rv v.abs=|rv v|:=by have e:v.abs.toModel.unpack=v.toModel.unpack.abs:=fc v.toModel;rw[bG]at d⊢;rw[bW,bW,e];generalize v.toModel.unpack=u at d⊢;cases u with | notANumber | infinity _=>simp[i5]at d | zero _=>simp[i4,i5,i6,ji] | finite s l e j=> refine⟨by simp[i4,i5],?_⟩ simp only[i4,Model.unpackedToReal_finite,AM];have h:=lk iT e;split<;>split<;>simp_all[AJ h] lemma gx(S:с)(l:fv S)(h:Д)(B:hа<2^63)(T:ℝ) (A:|rv S-T|<=(2:ℝ)^(hа:р)) (d:an S h<4294967296):|T|<=(2:ℝ)^(425:р):=by unfold an at d;dsimp only at d;split at d swap;. exact absurd d Б rename_i g;simp only[Β,AG]at g;obtain⟨⟨⟨q,r⟩,t⟩,u⟩:=g;obtain⟨v,w,j,x,-,-,-,m⟩:=fk h (eF S.toBits) (S.toBits&&&0xfffffffffffff) B (fq S).1 (fq S).2 q r t (rb _ u);have e:=aS S l (λy=>by rw[y]at j;simp at j) rw[aD]at e;generalize (eF S.toBits)а=E at v w j x m e;generalize (S.toBits&&&0xfffffffffffff)а=f at m e;have p:(0:ℝ)<2^((E:р)-1075):=В have z:((f+2^52:п):ℝ)+((2^(hа+1075-E):п):ℝ)<=2^53:=by exact_mod_cast(by omega:f+2^52+2^(h.toNat+1075-E)<=2^53) have l:|rv S|=((f+2^52:п):ℝ)*2^((E:р)-1075):=by rw[e,AM,AJ p];split<;>simp only[BM,lK] have:=abs_sub (rv S) (rv S-T);rw[sub_sub_cancel,l]at this rw[show(2:ℝ)^(hа:р)=((2^(hа+1075-E):п):ℝ)*2^((E:р)-1075) by push_cast;rw[<-AB,<-AI AH];congr 1;omega]at A have o:(2:ℝ)^(53:п)*2^((E:р)-1075)<=2^(425:р):=by rw[<-AB,<-AI AH];exact zpow_le_zpow_right₀ Г А linarith[AA z p.le] lemma fl(n:п)(e j:п->iJ)(d:al n e j)(S:с)(l:fv S)(h:Д) (p:hа<2^63) (m:|rv S-(ae n e j:ℝ)|<=(2:ℝ)^(hа:р)) (o:an S h<4294967296):(an S h)м=jP n e j:= cw n e j d S l h p m (gx S l h p _ m o) o lemma it(d:ф)(n:п)(j l:п->iJ)(p:п->с)(e:Unit->с)(w:Д)(L:п) (q:Unit->iJ) (F:∀srw[fl _ _ _ h _ E w u x y] generalize B:sT p n 0 (e ()) 0=r;split next v=> split next y=> have⟨o,m⟩:=cT _ _ (tm (j n) (l n)) n r.2а v.1 v.2.1 F n 0 _ 0 rfl А t.1 (by simp[t.2]) (by rw[B]) rw[B]at m o have D:((r.2а+L-1076)ж)а=r.2а+L-1076:=by rw[ϱ,Θ (by rw[jo];omega)] refine congrArg _ (fl _ _ _ h _ o _ (by rw[D];omega) ?_ y) rw[ap,D];rw[ae];push_cast;rw[add_comm] exact m.trans ((AA (by exact_mod_cast(by omega:n<=2^L):(n:ℝ)<=2^L) В).trans_eq (by rw[<-AB,<-AI AH];exact congrArg (2^·) А)) .exact A .rw[ite_eq_right Б];exact A lemma fd(Y:Ж)(j:Yе<2^32)(i:х)(v:с):wF Y i v=Y.set! iб v:=by rcases Y with⟨d⟩;rw[wF];split next h=>simp only[lV,j9,lZ,lY,lr];rw[BD (show iб rw[j9,lY,lr] rw[A5 λe=>h (by rw[β,lQ,aa (lt_of_lt_of_le j ς)];exact e)] lemma du(X:у iJ)(e:Xв<2^32)(i:х):rX X i=dw X[iб]!:=by rw[rX];split .rw[aC] next h=> rw[A0 X _ λd=>h (by rw[β,lh,aa (lt_of_lt_of_le e ς)];exact d)];rfl lemma iw(Y:Ж)(i:х)(v:с):(wF Y i v)е=Yе:=by rw[wF];split .rcases Y with⟨d⟩;simp only[lV,iX,lZ];apply Array.size_set .rfl lemma aI(X:у iJ)(e:Xв<2^32)(q d:х)(r:п)(o:х)(h:o=rд*d): rX X (q+o)=xr X q d r:=by rw[du X e,xr,gD,h] lemma dY(X:у iJ)(e:Xв<2^32)(d s w x y z A B:х) (D:w=(2:п)д*d) (E:x=(3:п)д*d) (F:y=(4:п)д*d) (G:z=(5:п)д*d) (H:A=(6:п)д*d) (I:B=(7:п)д*d): ∀k q o (Y:Ж) (h j l m p r t u:с),Yе<2^32-> (ce X d s w x y z A B k q o Y h j l m p r t u).xt=bx X d s k q o Y:=by intro k;induction k with | zero=>intro q o Y h j l m p r t u _;rfl | succ k J=> intro q o Y h j l m p r t u v rw[ce,bx,<-aI X e q d 1 d (by rw[Ϗ,show j5 1=1 fromН,USize.one_mul]), <-aI X e q d 2 w D,<-aI X e q d 3 x E,<-aI X e q d 4 y F,<-aI X e q d 5 z G, <-aI X e q d 6 A H,<-aI X e q d 7 B I,show xr X q d 0=rX X q by rw[<-aI X e q d 0 0 (by rw[Ϗ,show j5 0=0 fromН,USize.zero_mul]),USize.add_zero]] simp(disch:=first | exact v | (simp only[dy,iw];exact v)) only[s8,fd] exact J _ _ _ _ _ _ _ _ _ _ _ (by simp only[dy];exact v) lemma cd(p:п->с)(n:п):∀m t a,n-t=m-> ag p (n+1) (t+1) a=ag (λτ=>p (τ+1)) n t a:=by intro m;induction m with | zero=>intro t a h;unfold ag;rw[AP А,AP А] | succ m d=>intro t a h;unfold ag;rw[if_pos А,if_pos А];exact d (t+1) _ А lemma dE(X:у iJ)(A s u v w x y z:х)(O:п->х) (B:O 0=0/\O 1=A/\O 2=u/\O 3=v/\O 4=w/\O 5=x/\O 6=y/\O 7=z) (r:п) (M:r<8): ∀k q o (Y:Ж) (d e h j l m p t:с), (ce X A s u v w x y z k q o Y d e h j l m p t).g r= ag (λτ=>(rX X (q+τд*s+O r)).abs) k 0 (A8.f ⟨d,e,h,j,l,m,p,t⟩ r):=by have⟨E,F,G,H,I,J,K,L⟩:=B;intro k;induction k with | zero=>intro q o Y d e h j l m p t;rw[ag,AP А];interval_cases r<;>rfl | succ k D=> intro q o Y d e h j l m p t;rw[ce,D];conv_rhs=>rw[ag,if_pos А,cd _ _ _ 0 _ rfl] simp only[λτ:п=>show q+s+τд*s=q+(τ+1)д*s by rw[Ϗ,Ϗ,USize.ofNat_add,USize.add_mul,show j5 1=1 fromН,USize.one_mul, USize.add_assoc,USize.add_comm s]] congr 1;interval_cases r<;>simp[A8.f,E,F,G,H,I,J,K,L,show j5 0=0 fromН] lemma gu(n:ℕ)(σ l E A C H M:ℝ)(v:0<=σ)(d:0omega obtain⟨x,j⟩:=cG (9*(n+1))ж.toInt64 (by rw[e];simp;omega) rw[e]at j;push_cast at j have t:(2:ℝ)^(((eF ((9*(n+1))ж.toInt64.toFloat*a).toBits)а:р)-1022)<= 2^(((cE (9*(n+1))ж.toInt64.toFloat a)а:р)+56):=by apply zpow_le_zpow_right₀ Г;unfold cE;dsimp only;split .rw[υ _ _ (BZ ‹_›)];have:=ν.mp ‹_› simp only[iE]at this⊢;omega .have:=κ.mp (UInt64.not_lt.mp ‹_›);simp only[iE]at this⊢;omega have u:(n:ℝ)<=536870912:=by exact_mod_cast I.le have J:(2:ℝ)^(-1074:р)=2^(-1075:р)*2:=by rw[<-BR AH];norm_num have W:(2:ℝ)^(-1075:р)*2^64<=2^(-900:р):=by rw[<-AB,<-AI AH];exact zpow_le_zpow_right₀ Г Г have U:(2:ℝ)^40*2^(400:р)<=2^(971:р):=by rw[<-AB,<-AI AH];exact zpow_le_zpow_right₀ Г Г have V:(1:ℝ)<=2^(400:р):=one_le_zpow₀ Г Г;have h:(0:ℝ)<2^(-1075:р):=В;have G:(2:ℝ)^(-900:р)<=1:=Ai Г Г rw[show(2:ℝ)^(-53:р)=1/9007199254740992 by norm_num,show(2:ℝ)^(-20:р)=1/1048576 by norm_num, J,mul_add,<-Ad]at d have X:=AA u h.le;generalize H:(n:ℝ)*(1/9007199254740992*(1+1/1048576))=L at d;have o:L<=1/8388608:=by rw[<-H];nlinarith have Y:=AA o v have B:|rv a|<=3*2^(400:р):=by have:=AD (rv a) σ;rw[AS v]at this;generalize (2:ℝ)^(-1075:р)=y at*;generalize (2:ℝ)^(-900:р)=ε at* generalize (2:ℝ)^(400:р)=Z at*;linarith have F:|rv (9*(n+1))ж.toInt64.toFloat*rv a|<=2^(971:р):=by rw[j,AM,AJ В];have:=AE B (by positivity:(0:ℝ)<=9*(n+1)) have:=AA u (by positivity:(0:ℝ)<=2^(400:р)) generalize (2:ℝ)^(400:р)=Z at*;generalize (2:ℝ)^(971:р)=M at*;linarith obtain⟨p,l⟩:=ij _ a x E F;have S:=lt_of_le_of_lt' t (Ac (AF _) (cf _ p));have O:=lt_of_lt_of_le (Ac (A1 _) (cf _ p)) t;rw[j,show(2:ℝ)^(-53:р)=1/9007199254740992 by norm_num]at l rw[show(2:ℝ)^(-20:р)=1/1048576 by norm_num] generalize (2:ℝ)^(((cE (9*(n+1))ж.toInt64.toFloat a)а:р)+56)=Q at* generalize rv ((9*(n+1))ж.toInt64.toFloat*a)=P at* generalize rv a=A at* generalize (2:ℝ)^(-1075:р)=y at* generalize (2:ℝ)^(-900:р)=ε at* have m:(n:ℝ)*(y*2)<=1073741824*y:=by linarith generalize (n:ℝ)*(y*2)=w at d m;have r:(0:ℝ)<=9*(n+1):=В;have D:=AA (by linarith:9*((n:ℝ)+1)<=2^33) h.le generalize 9*((n:ℝ)+1)=N at* obtain⟨z,-⟩:=abs_le.mp d;rcases le_or_gt 0 A with q | q .rw[AS (AW r q)]at l have:=AE z (by linarith:0<=N*(1-1/9007199254740992)) nlinarith[(abs_le.mp l).1] .have:=AE (by linarith:σ<=2*w) r nlinarith lemma fu(x:iJ)(d:iG x≠255):|rv (dw x)|<=2^(277:р):=by rw[(au x d).2,AM,BW,BL];have:(iG x)г≠255:=λh=>d (Ι.mp (by simpa using h)) have:=a9 x calc _<=(2:ℝ)^24*2^253:=Af (by rw[<-ϊ];exact_mod_cast(aQ x).le) (AC Г (by rw[aT];omega)) В В _=2^(277:р):=by rw[<-AK,<-AB];rfl lemma f0:fv (0:с)/\rv (0:с)=0:=by have e:(0:с).toModel.unpack=.zero .positive:=Н;refine⟨by rw[bG,e];rfl,by rw[bW,e];simp[i6,ji]⟩ lemma gM(b s d τ r:п)(p:s<2^32)(j:d<2^32)(q:τ<2^32)(o:r<2^32) (h:b+τ*s+r*d<2^32): (bд+τд*sд+rд*dд)б=b+τ*s+r*d:=by have:=ς;have:=ϡ have m:∀x y:п,x<2^32->y<2^32->x*y<2^32->(xд*yд)б=x*y:= λx y t u h=>by rw[kV,aa А,aa А,θ А] have e:=m τ s q p А;have l:=m r d o j А rw[af (by rw[af (by rw[aa А,e];omega),aa А,e,l];omega), af (by rw[aa А,e];omega),aa А,e,l] lemma cW(t:ф)(X:у iJ)(R n h:п)(Z:Ж)(A:8*n<=Zе) (o:Zе<2^32) (v:Xв<2^32) (w:∀q:п,iG X[q]!≠255) (E:8*n<2^32): (aG t X R n h Z).xt=eG t X R n h Z/\∀r<8, 9*((n:ℝ)+1)*(∑τ∈iD n,|rv (dw X[(if t then 8*h else 8*h*n)+τ*(if t then R else 1)+ r*(if t then 1 else n)]!)|)*(1-2^(-20:р))<= 2^((((aG t X R n h Z).cc r)а:р)+56)+2^(-900:р):=by have x:∀(b s d r:п),0<=∑τ∈iD n,|rv (dw X[b+τ*s+r*d]!)|/\ ∑τ∈iD n,|rv (dw X[b+τ*s+r*d]!)|<=2^(400:р):=λb s d r=>by refine⟨Ϩ λ_ _=>AF _,(ϋ λτ _=>fu _ (w _)).trans ?_⟩ have:(n:ℝ)<=2^29:=by exact_mod_cast(by omega:n<=2^29) rw[jU,ϴ,BC] calc (n:ℝ)*2^(277:р)<=2^29*2^(277:р):=by gcongr _<=2^(400:р):=by rw[<-AB,<-AI AH];exact zpow_le_zpow_right₀ Г Г rw[aG,eG];generalize (if t then 1 else n)=d;generalize (if t then R else 1)=s;generalize (if t then 8*h else 8*h*n)=b;dsimp only;split .rename_i y refine⟨by rw[bt,if_pos y];exact dY X v _ _ _ _ _ _ _ _ rfl rfl rfl rfl rfl rfl _ _ _ _ _ _ _ _ _ _ _ _ o, λr p=>?_⟩ have e:=dE X dд sд (2*dд) (3*dд) (4*dд) (5*dд) (6*dд) (7*dд) (λk=>kд*dд) ⟨by simp[Ϗ,show j5 0=0 fromН],by simp[Ϗ,show j5 1=1 fromН], rfl,Н,Н,Н,Н,Н⟩ r p n bд 0 Z 0 0 0 0 0 0 0 0 rw[f8]at e;have⟨m,j⟩:=x b s d r have⟨u,l⟩:=f6 (λτ=>(rX X (bд+τд*sд+rд*dд)).abs) (λτ=>|rv (dw X[b+τ*s+r*d]!)|) 0 n (λτ z=>by have:=ψ s z.le;have:=ψ d p.le;rw[du X v,gM b s d τ r А А А А А];exact gh _ (au _ (w _)).1) А (by simpa using j.trans (zpow_le_zpow_right₀ Г (by norm_num:(400:ℤ)<=968))) n 0 0 rfl (ϸ _) f0.1 (by simp[f0.2]) simp only[abs_zero,Ak,abs_abs]at l;rw[<-e]at u l;have:=dH n А _ _ u m j l;interval_cases r<;>exact this .refine⟨Н,λr p=>?_⟩ rw[show((⟨bt X d s n b Z,400,400,400,400,400,400,400,400⟩:XB).cc r)а=400 by interval_cases r<;>rfl] have⟨m,j⟩:=x b s d r;have:(n:ℝ)<=2^29:=by exact_mod_cast(by omega:n<=2^29) have:=Af (by linarith:9*((n:ℝ)+1)<=2^33) j m Г have:(2:ℝ)^33*2^(400:р)<=2^(((400:п):р)+56):=by rw[<-AB,<-AI AH];exact zpow_le_zpow_right₀ Г Г have:(0:ℝ)<2^(-900:р):=В;have:0<=9*((n:ℝ)+1)*(∑τ∈iD n,|rv (dw X[b+τ*s+r*d]!)|)*2^(-20:р):=В generalize (2:ℝ)^(400:р)=B at*;generalize (2:ℝ)^(((400:п):р)+56)=Q at* generalize (2:ℝ)^(-900:р)=D at*;generalize (2:ℝ)^(-20:р)=δ at* linarith lemma gn(x w:iJ)(e:п)(h:(iG w)г<=e): |(aR x w:ℝ)|<=|(sv x:ℝ)*2^iL x| *2^(lX e 56+23):=by unfold aR tm;obtain⟨-,-,-,d⟩:=cj w;push_cast rw[show(sv x:ℝ)*sv (nW w)*2^(iL x+iL (nW w))= (sv x*2^iL x)*(sv (nW w)*2^iL (nW w)) by rw[AK];ring,AM] gcongr;rw[AM,BW,BL] refine(Af (b:=2^24) (by rw[<-ϊ];exact_mod_cast(aQ _).le) (AC Г (by rw[d];omega:_<=max e 56-1)) В В).trans_eq ?_ rw[<-AK];congr 1;omega lemma go(x w:iJ):|(tm x w:ℝ)-aR x w|<=|(sv x:ℝ)*2^iL x| *2^26:=by rw[aR];rcases eg w with h | ⟨j,l⟩ .rw[h,sub_self,abs_zero];positivity .unfold tm;push_cast rw[show(sv x:ℝ)*sv w*2^(iL x+iL w)-sv x*sv (nW w)*2^(iL x+iL (nW w))= (sv x*2^iL x)*(sv w*2^iL w-sv (nW w)*2^iL (nW w)) by rw[AK,AK];ring, AM,j,l] gcongr;have A:∀w:iJ,|(sv w:ℝ)|<=2^24:=λw=>by rw[<-ϊ];exact_mod_cast(aQ _).le have d:=A w;have e:=A (nW w);rw[AZ]at d e⊢;constructor<;>linarith lemma e9(b:iJ)(d:п)(h:iL b<=d):|(tm jN b:ℝ)|<=2^(173+d):=by rw[tm] rw[(Б:sv jN=2^23),(Б:iL jN=126),Int.cast_mul,Int.cast_mul,AM,AM, Int.cast_pow,Int.cast_pow,Int.cast_ofNat,BW,BW,BL] have e:|(sv b:ℝ)|<=2^24:=by rw[<-ϊ];exact_mod_cast(aQ _).le calc (2:ℝ)^23*|(sv b:ℝ)| *2^(126+iL b)<=2^23*2^24*2^(126+d):=by gcongr;norm_num _=2^(173+d):=by rw[<-AK,<-AK];congr 1;omega lemma gY(t:ф)(R n:п)(d:ф)(X W b:у iJ)(y:у XB)(L i j G D:п) (e:iJ) (c m:Д) (S:с) (u:∀q:п,iG X[q]!≠255) (o:∀q:п,iG b[q]!≠255/\iL b[q]!<=D) (a1:174+D<=G) (Y:n+2<=2^L) (v:L<=27) (O:G+L<=425) (hn:8*n<2^32) (r:∀s(y[i/8]!).xt.data[8*s+i%8]!*dX W[j*n+s]!) n 0 (dw jN*dw b[j]!)) (M:∀ssN n d X W b y L i j (if t then i else i*n) (if t then R else 1)) else aj n d X W b (if t then i else i*n) (if t then R else 1) j)= act d (jP (n+1) (λs=>if sif s(2:ℝ)^a<=2^b:=AC Г;generalize hP:(if eк<56 then 56 else eк)+23+c=p have hp:pа=lX eг 56+23+cа:=by have:=UInt32.toNat_lt e rw[<-hP];split<;>rename_i h<;>simp only[ν,ϟ,ξ, iE]at h⊢<;>omega split;swap;. simp only[aj,bs] rename_i hg;simp only[Β,AG,ϯ,κ, iO,iE]at hg generalize V:(if p< m then m else p)=N have hq:Nа=lX pа mа:=by rw[<-V];split<;>rename_i h<;>simp only[ν]at h<;>omega have F:∀sby have:=M s l;simp[h]at this;omega have E:=dt jN b[j]! Б (o j).1;generalize B:(∑s∈iD n,|rv (dw X[x+s*w]!)|)=z at A have J:0<=z:=B▸Ϩ λ_ _=>AF _ rw[AI AH,AB]at A;have Q:=e9 b[j]! D (o j).2;have K:(n:ℝ)<=2^32:=by exact_mod_cast(А:n<=2^32) have Z:z<=n*2^277:= B▸(ϋ λs (_:s∈iD n)=>fu X[x+s*w]! (u _)).trans_eq (by simp) have hZ:∑s∈iD n,|(aR X[x+s*w]! W[j*n+s]!:ℝ)|<=2^(lX eг 56+23)*z:=by rw[<-B,jJ] exact ϋ λs l=>by rw[(au _ (u _)).2];exact(gn _ _ _ (M s (Κ.1 l))).trans_eq (mul_comm _ _) have U:|(tm jN b[j]!:ℝ)|+∑s∈iD n,|(aR X[x+s*w]! W[j*n+s]!:ℝ)|<= 2^(968:р):=by rw[show(2:ℝ)^(968:р)=2^967+2^967 by rw[<-two_mul,<-A3];norm_num] refine BA (Q.trans (P А)) (hZ.trans ((Af (P (by omega:_<=400)) (Z.trans (AA K В)) J В).trans ?_)) rw[<-AK,<-AK];exact P Г obtain⟨I,H⟩:=f6 (λs=>(y[i/8]!).xt.data[8*s+i%8]!*dX W[j*n+s]!) _ _ n (λs l=>by rw[r s l];simpa[ai]using el false _ _ (u (x+s*w)) (F s l)) А U n 0 _ А (ϸ _) E.1 (by rw[E.2];simp) rw[<-hS]at I H refine it d n _ _ _ _ N L _ ?_ ?_ ?_ Y v А (by simp only[aj,bs]) S I (gu n z (tm jN b[j]!:ℝ) _ (2^(lX eг 56+23)) _ (2^mа) _ J В (Ah Г) (by simpa using K) ?_ ?_ A ?_ ?_ ?_ ?_) .intro s l;simp only[gg,r s l,l,↓reduceIte];exact dt _ _ (u _) (F s l) .simpa using E .intro k _;by_cases h:ksimp only[h,↓reduceIte];exacts[⟨u _,F k h⟩,⟨Б,(o j).1⟩] .refine(AX _ _ _).trans (BA (H.trans (by gcongr)) ?_) rw[ap];unfold ae;push_cast;simp only[Ar,AN];rw[add_comm (Finset.sum _ _),add_sub_add_left_eq_sub,<-ϙ];refine(ϣ _ _).trans ?_;rw[<-B,jJ] exact ϋ λs l=>by simp only[Κ.1 l,↓reduceIte];rw[Au,(au _ (u _)).2];exact(go _ _).trans_eq (by norm_num;ring) .rw[<-AB,<-AI AH];exact zpow_le_zpow_right₀ Г А .rw[show(2:ℝ)^(49:р)=2^49 by norm_num,<-AK] refine(Af (by exact_mod_cast(А:n<=2^L):(n:ℝ)<=2^L) Q (AF _) В).trans ?_ rw[<-AK];exact P А .rw[<-AK,AB];exact P А .rw[AB];exact P А .exact zpow_le_zpow_right₀ Г А lemma eO(b:Д):(eF b)а<=2047:=by unfold eF;simp only[Α,iE];exact Ϻ lemma eN(F a:с):(cE F a)а<=969:=by unfold cE;dsimp only;split .rename_i h;have:=eO (F*a).toBits;have d:=ν.mp h rw[υ _ _ (BZ h)];simp only[iE]at d⊢;omega .simp lemma dS(t:ф)(X:у iJ)(R n d:п)(Z:Ж)(r:п): ((aG t X R n d Z).cc r)а<=1000:=by have h:∀F a,(cE F a)а<=1000:=λF a=>Nat.le_trans (eN F a) Б rcases r with _|_|_|_|_|_|_|_|r<;>simp only[XB.cc,aG]<;>split_ifs<;>first | exact h _ _ | exact(by decide:(400:Д).toNat<=1000) lemma d9(D:ф)(R A y:п)(e:ф)(r p u:у iJ)(q:у XB)(E:XB)(w:Д) (L B z:п) (W:у iJ) (X:Ж) (l n:х) (x:Wв<2^32/\Xе<2^32) (v:lб+nб<=Wв): ∀m (t i:х) (j:iб+8*(nб-tб)<=Xе) (a0 a1 a2 a3 a4 a5 a6 a7:с) (o:iJ) (d:у iJ),nб-tб=m-> bO D R A y e r p u q E w L B z W X l n x v t i j a0 a1 a2 a3 a4 a5 a6 a7 o d= (λK:A9=>w8 D R A y e r p u q E w L B z K.o K.a0 K.a1 K.a2 K.a3 K.a4 K.a5 K.a6 K.a7 d) (k8 W X l n x v t i j a0 a1 a2 a3 a4 a5 a6 a7 o):=by intro m;induction m with | zero=> intro t i j a0 a1 a2 a3 a4 a5 a6 a7 o d F;have h:¬tby have:=β.mp h;omega rw[bO,Ax h,k8,Ax h] | succ m G=> intro t i j a0 a1 a2 a3 a4 a5 a6 a7 o d F;have h:tт)(a:у т)(P:п->Prop)(A:у т):Prop:= Aв=aв/\∀q,(A[q]?=a[q]?\/A[q]?=some (F q))/\(P q->qA[q]?=some (F q)) lemma bb(F:п->iJ)(o p r:у iJ)(S T U:п->Prop)(y:∀q,U q->S q\/T q) (d:Iv F o S p) (l:Iv F p T r):Iv F o U r:=by refine⟨l.1.trans d.1,λq=>?_⟩ have⟨t,u⟩:=d.2 q;have⟨j,v⟩:=l.2 q;refine⟨?_,λh m=>?_⟩ .rcases j with e | e .rw[e];exact t .exact ll e .rcases y q h with w | x .rcases j with e | e .rw[e];exact u w m .exact e .exact v x (d.1▸m) lemma cM(F:п->iJ)(e j:у iJ)(S U:п->Prop)(l:∀q,U q->S q) (h:Iv F e S j):Iv F e U j:= ⟨h.1,λq=>⟨(h.2 q).1,λd m=>(h.2 q).2 (l q d) m⟩⟩ lemma cK(t:ф)(R n m:п)(d:ф)(X W b:у iJ)(L:п) (I:Wв<2^32/\8*n<2^32) (G:m*n<=Wв) (u:у XB) (D:XB) (z:Д) (r j:Ж) (J:8*n<=rе/\rе<=4294967295) (p:п) (F:п->iJ) (C:п->п->п->Prop) (N:п) (H:∀(o:п) (a:у iJ),o< m->aв=N->∀B x A,Iv F a (C p o) (bO t R m n d X W b u D z L p o W r (o*n)д nд B x 0 0 A (j.get! o) (j.get! o) (j.get! o) (j.get! o) (j.get! o) (j.get! o) (j.get! o) (j.get! o) 0 a)) (o:п) (a:у iJ) (y:aв=N): Iv F a (λq=>∃l,o<=l/\l< m/\C p l q) (ch t R n m d X W b L I G u D z r j J p o a):=by induction o,a using ch.induct t R n m d X W b L I G u D z r j J p with | case1 o a h M K=> rw[ch,BD h] refine bb F a _ _ _ _ _ (λq ⟨l,v,w,E⟩=>by rcases Bc v with e | e .subst e;exact lA E .exact ll ⟨l,e,w,E⟩) (H o a h y _ _ _) (K ?_) exact(H o a h y _ _ _).1.trans y | case2 o a h=> rw[ch,A5 h];exact⟨Н,λq=>⟨lA rfl,λ⟨l,v,w,_⟩ _=>absurd (kp v w) h⟩⟩ lemma cL(t:ф)(R n r:п)(m:ф)(X W b:у iJ)(L:п) (E:Wв<2^32/\8*n<2^32) (z:r*n<=Wв) (j:у XB) (w:Д) (p:Ж) (F:п->iJ) (C:п->п->п->Prop) (N:п) (O:∀(l o:п) (a:у iJ) (u:laв=N-> ∀(G:Wв<2^32/\j[l].xtе<2^32) (A:((o*n)д)б+(nд)б<=Wв) (D:(0:х)б+8*((nд)б-(0:х)б)<=j[l].xtе),Iv F a (C l o) (bO t R r n m X W b j j[l] w L l o W j[l].xt (o*n)д nд G A 0 0 D (p.get! o) (p.get! o) (p.get! o) (p.get! o) (p.get! o) (p.get! o) (p.get! o) (p.get! o) 0 a)) (l:п) (a:у iJ) (B:aв=N): Iv F a (λq=>∃d o,l<=d/\d rw[ci,BD h] have K:∀q,(∃d o,l<=d/\d (∃o,oby rcases Bc u with e | e .subst e;exact lA ⟨o,v,I,J⟩ .exact ll ⟨d,o,e,y,v,I,J⟩ by_cases x:8*n<=xtе/\xtе<=4294967295 .have:=cK t R n r m X W b L E z j S w xt p x l F C N (λo a Q=>O l o a h Q) 0 a B refine bb F a _ _ _ _ _ K ?_ (M ?_)<;>rw[BD x];exacts[cM F a _ _ _ (λq ⟨o,u,_,v⟩=>⟨o,ϸ _,u,v⟩) this,this.1.trans B] .refine bb F a _ _ _ _ _ K ?_ (M ?_)<;>rw[A5 x] exacts[⟨Н,λq=>⟨lA rfl,λ⟨o,_,H,_⟩ _=>absurd (by rwa[AL j l h]at H) x⟩⟩,B] | case2 l a h=> rw[ci,A5 h];exact⟨Н,λq=>⟨lA rfl,λ⟨d,_,u,y,_⟩ _=>absurd (kp u y) h⟩⟩ lemma dQ(o:ф)(R r v:п)(l:ф)(B A D:у iJ)(J:у XB)(z:XB)(G:Д) (L d m:п) (e:iJ) (K M N O S U V W:с) (p:у iJ) (F:п->iJ) (hR:R*r<=4294967295) (Z:m (if e<255&&(if eк<56 then 56 else eк)+23+z.cc k<=400 then tf l (A8.f ⟨K,M,N,O,S,U,V,W⟩ k) (if(if eк<56 then 56 else eк)+23+z.cc ksN v l B A D J L (8*d+k) m (if o then 8*d+k else(8*d+k)*v) (if o then R else 1)) else aj v l B A D (if o then 8*d+k else(8*d+k)*v) (if o then R else 1) m)= F (if o then m*R+(8*d+k)else(8*d+k)*r+m)): Iv F p (λq=>∃k,k<8/\8*d+k∃j,jk<8->(8*d+kUSize.toNat H=I k)-> Q (k+1) (bh o R v l B A D J e (z.cc k) G L (decide (k8*d+k) m a (A8.f ⟨K,M,N,O,S,U,V,W⟩ k)):=by intro k a H ⟨E,u⟩ hk hq;rw[bh];split next X=> have y:=Nat.lt_sub_iff_add_lt'.1 (of_decide_eq_true X.1);refine⟨by simp[E],λq=>?_⟩ rw[lL,lB,hv k hk y];by_cases h:Hб=q .subst h;simp[hq y,I] .rw[ite_eq_right h] exact⟨(u q).1,λ⟨j,Y,w,x⟩=>(u q).2 ⟨j,Bb (Bh Y) λe=>by subst e;exact h ((hq w).trans x.symm),w,x⟩⟩ next X=> refine⟨E,λq=>⟨(u q).1,λ⟨j,Y,w,x⟩ as=>(u q).2 ⟨j,Bb (Bh Y) λe=>X ⟨decide_eq_true А,?_⟩,w,x⟩ as⟩⟩ subst e;rw[β,lh,aa (by have:=ς;omega),hq w,<-x];omega refine t 7 (t 6 (t 5 (t 4 (t 3 (t 2 (t 1 (t 0 ?_ ?_ ?_) ?_ ?_) ?_ ?_) ?_ ?_) ?_ ?_) ?_ ?_) ?_ ?_) ?_ ?_ all_goals first | decide | ( intro h;have E:=ψ r h;have u:=ψ R Z;have:=Ϧ r R rcases kr with hn | hn<;>cases o<;> simp[I,hn,lm]at E u⊢<;>omega) | simp[Q,Iv] def ec(rows n ow:п)(relu:ф)(X W b:у т)(ix ib L:п) (hs:Wв<2^32/\8*n<2^32) (hW:ow*n<=Wв):у т:= ct М rows n ow relu X W b ix ib L hs hW lemma bB{t:ф}(d n j:п)(l:ф)(X W b:у iJ)(ix M L:п) (J:Wв<2^32/\8*n<2^32) (hW:j*n<=Wв) (Q:п) (hx:∀q:п,iG X[q]!≠255/\iL X[q]!<=ix) (hb:∀q:п,iG b[q]!≠255/\iL b[q]!<=Q) (as:174+Q<=M) (hL:n+2<=2^L) (A:L<=27) (G:M+L<=425): ct t d n j l X W b ix M L J hW=iZ (n:=d*j) λq=>act l (jP (n+1) (λs=>if sif s(a*m+c)/m=a/\(a*m+c)%m=c:=λa c m h=> ⟨by rw[Ϙ,ό _ _ А,Χ h,ϥ], by rw[Ϙ,Ο,θ h]⟩ rw[ct];split;swap .congr 1;funext q;cases t<;>simp only[aj,bs,jz,↓reduceIte,μ] rename_i hg;have Y:=iA n;have D:Xв<2^32:=А;have E:=λe=>cW t X d n e _ Y.1 А D (λq=>(hx q).1) J.2 have x:∀e,8*n<=(aG t X d n e (zT n)).xtе/\(aG t X d n e (zT n)).xtе<=4294967295/\ ∀srw[h]<;>rcases Y.2 with h | h<;>omega,λs p k H=>?_⟩ rw[v.2.2 s k p H];congr 2;cases t<;>simp only[↓reduceIte,μ]<;>ring have hn:nдб=n:=aa (by have:=ς;omega) dsimp only;generalize r:(iZ (n:=(d+7)/8) λe=>aG t X d n eи (zT n))=y have K:=cL t d n j l X W b L J hW y (M+L-50)ж (aM (λo=>dw jN*dw b[o]!) j (iP j)) (λq=>act l (jP (n+1) (λs=>if sif s∃k,k<8/\8*e+kdw jN*dw b[o]!) j (iP j)).get! o=dw jN*dw b[o]!:=by rw[gg];exact(bj _ j _ _ rfl (ϸ _)).2.2 o (ϸ _) O rw[hB,d9 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ rfl];refine dQ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ hg.1 O ha λk H a0=>?_ set B:=dw jN*dw b[o]!;have K:=eV W _ _ _ p V 0 k H _ 0 0 Z B B B B B B B B 0 rfl (О) simp only[a1,hn,ϝ,ϥ,f8,zero_le,true_implies]at K;have e8:(8*e+k)/8=e:=А;have z:(8*e+k)%8=k:=А;have w:=(E e).2 k H;rw[<-u]at w have ei:∀τ,(if t then 8*e else 8*e*n)+τ*(if t then d else 1)+k*(if t then 1 else n)= (if t then 8*e+k else(8*e+k)*n)+τ*(if t then d else 1):=λτ=>by cases t<;>simp only[↓reduceIte,μ]<;>ring simp only[ei]at w refine(gY t d n l X W b _ L (8*e+k) o M Q _ _ _ _ (λq=>(hx q).1) hb as hL A G J.2 (λs p=>by rw[e8,z,AL _ e N,u];exact(x e).2.2 s p k H) ?_ (λs p=>K.2.1 s p) w (by rw[u];exact dS ..) ?_).trans ?_ .rw[e8,z,AL _ e N];exact K.1 .rw[ϱ,Θ (by rw[jo];omega)] .cases t .obtain⟨S,U⟩:=dm (8*e+k) o j O;simp only[S,U,μ,↓reduceIte,jz] .obtain⟨S,U⟩:=dm o (8*e+k) d a0;simp only[S,U,↓reduceIte] refine lC λq=>?_ by_cases I:qby subst h;simp at I have hR:0by subst h;simp at I have F:∀e,e<(d+7)/8->8*n<=y[e]!.xtе/\y[e]!.xtе<=4294967295:=λe h=>by subst r;rw[AL _ _ (by simpa using h),Ν];exact⟨(x e).1,(x e).2.1⟩ have J:yв=(d+7)/8:=by subst r;simp cases t .have N:=js q j have h2:q/jт->т)(h:т->т)(W:у т)(ou n t:х)(hs:Wв<2^32) (hW:ouб+8*nб<=Wв) (ht:tбiJ->iJ)(h:iJ->iJ)(P:iJ->п)(q:∀x y,P x<=P (g x y)/\P y<=P (g x y)) (W:у iJ) (d n t:х) (l:Wв<2^32) (j:dб+8*nб<=Wв) (m:tбez (c:=c) l j m u v have L:∀{z x y},P z<=P x->P z<=P (g x y):=λe=>e.trans (q _ _).1 have R:∀{z x y},P z<=P y->P z<=P (g x y):=λe=>e.trans (q _ _).2 rw[m8];simp(disch:=simp) only[p,iV];exact⟨L AO,λr w=>by interval_cases r<;>solve_by_elim only[L,R,AO]⟩ def kw(W:у т)(X:Ж)(ou n:х)(hs:Wв<2^32) (hW:ouб+8*nб<=Wв) (hX:nб<=Xе) (z:с) (t:х) (a0 a1 a2 a3 a4 a5 a6 a7:с) (o f:т):A9:= if h:t>>24⟩ termination_by nб-tб decreasing_by all_goals (rw[ac h];omega) lemma cs(W:у iJ)(X:Ж)(d n:х)(N:Wв<2^32) (L:dб+8*nб<=Wв) (U:nб<=Xе) (z:с) (r:п) (S:r<8):∀m (t:х) (j l p q u v A B:с) (o f:iJ),nб-tб=m-> (λR:A9=>R.s.f r= aP (λs=>X.data[s]! ==z) (λs=>ai (r%2==1) X.data[s]! W[dб+nб*r+s]!) nб tб (A8.f ⟨j,l,p,q,u,v,A,B⟩ r)/\ (∀s,tб<=s->s(X.data[s]! ==z)=М->(iG W[dб+nб*r+s]!)г<= R.oг)/\ oг/2^24<=R.oг/\ (R.oг<255->(iG f)г<255/\∀s,tб<=s->s(X.data[s]! ==z)=true-> (iG W[dб+nб*r+s]!)г<255)) (kw W X d n N L U z t j l p q u v A B o f):=by intro m;induction m<;>intro t j l p q u v A B o f Z .rw[kw,Ax (by rw[β];omega),aP,AP (show¬tбА,by split<;>simp only[dc,iO]<;>omega,λK=>⟨?_,λs O D _=>А⟩⟩ split at K;exacts[ϯ.mp ‹_›,by simp only[dc,iO]at K;omega] rename_i Y;have H:tбez (c:=c) N L H E V have M:=bC lX (.<<<1) UInt32.toNat (λx y=>by rw[jT];omega) W d n t N L H o have F:=bC (. ||| ·) aJ (λw=>(iG w)г) eo W d n t N L H f have I:=λ{j l p q u v A B o f}=>Y (t+1) j l p q u v A B o f (by rw[ac h];omega) rw[kw,As h,aP,if_pos H];dsimp only by_cases E:(X.data[tб]! ==z)=Л<;>simp only[ug X t,E,μ,↓reduceIte]<;> refine⟨I.1.trans ?_,λs O D G=>if e:s=tбthen(by subst e;first | exact Bool.noConfusion (E.symm.trans G) | exact Ae (by rw[eS];exact Ϸ (M.2 r S)) I.2.2.1) else I.2.1 s (by rw[ac h];omega) D G, Ae (Ϸ (by first | exact M.1 | exact AO)) I.2.2.1,λK=>?_⟩<;> try(have J:=I.2.2.2 K;exact⟨by first | exact Ac F.1 J.1 | exact J.1,λs O D G=>if e:s=tбthen(by subst e;first | exact absurd G E | exact Ac ((eA _).ge.trans (F.2 r S)) J.1)else J.2 s (by rw[ac h];omega) D G⟩) all_goals rw[ac h] congr 1 interval_cases r<;> (simp only[A8.f,iM,Nat.reduceBEq];rw[Q _ _ (by simp only[iV];omega)];simp only[iV]) def cH(W:у т)(X:Ж)(ou n:х)(hs:Wв<2^32) (hW:ouб+8*nб<=Wв) (hX:nб<=Xе) (t:х) (a0 a1 a2 a3 a4 a5 a6 a7:с) (o:т):A9:= if h:t (λR:A9=>R.s.f r= aP (λ_=>М) (λs=>ai (r%2==1) X.data[s]! W[yб+nб*r+s]!) nб tб (A8.f ⟨d,j,l,p,q,u,v,x⟩ r)/\ (∀s,tб<=s->s(iG W[yб+nб*r+s]!)г<=R.oг)/\ (iG o)г<=R.oг) (cH W X y n A z G t d j l p q u v x o):=by intro m;induction m with | zero=> intro t d j l p q u v x o H;rw[cH,Ax λh=>by have:=β.mp h;omega,aP,AP А] exact⟨Н,λs E D=>А,AO⟩ | succ m K=> intro t d j l p q u v x o H;have h:t(iG w)г) eo W y n t A z B o have I:=λd j l p q u v x=>K (t+1) d j l p q u v x (m8 (. ||| ·) id W y n t A z B o) (by rw[ac h];omega) rw[cH,As h,aP,if_pos B];dsimp only refine⟨(I _ _ _ _ _ _ _ _).1.trans ?_,λs E D=>if e:s=tбthen(by subst e;exact(F.2 r J).trans (I _ _ _ _ _ _ _ _).2.2)else(I _ _ _ _ _ _ _ _).2.1 s (by rw[ac h];omega) D, F.1.trans (I _ _ _ _ _ _ _ _).2.2⟩ rw[ac h,ug X t];congr 1 interval_cases r<;> (simp only[A8.f,iM,Nat.reduceBEq,μ,↓reduceIte] rw[ez A z B (by simp only[iV];omega)];simp only[iV]) def bM(A:у т)(e:х)(he:e<=A.usize)(i:х)(m:Е):Е:= if h:i>>23)&&&255))else m termination_by eб-iб decreasing_by have:=β.mp h;rw[ac h];omega lemma cX(A:у iJ)(e:х)(d:e<=A.usize):∀k (i:х) (m:Е),eб-iб=k-> mг<=(bM A e d i m)г/\∀q,iб<=q->q(iG A[q]!)г<=(bM A e d i m)г:=by intro k;induction k with | zero=> intro i m p;rw[bM,Ax λh=>by have:=β.mp h;omega];exact⟨AO,λq w j=>А⟩ | succ k v=> intro i m p;have h:i>>23)&&&255)) (by rw[ac h];omega) rw[jT]at t;refine⟨А,λq o j=>?_⟩ by_cases r:q=iб .subst r;rw[<-aC A i (aF l)];rw[iG];omega .exact u q (by rw[ac h];omega) j lemma iq(d:ф)(S:с)(e:iJ)(j h L:п)(p m o l:Unit->iJ)(v:iJ) (q:tG d S e j h L m l=v) (r:p ()=v) (t:o ()=v):tG d S e j h L p o=v:=by unfold tG tf at*;dsimp only at* by_cases g:(hG e j h L).1=Л<;>by_cases c:an S (hG e j h L).2<4294967296<;>simp_all lemma gI(g:п->с)(r:п)(d:r<8): A8.f ⟨g 0,g 1,g 2,g 3,g 4,g 5,g 6,g 7⟩ r=g r:=by interval_cases r<;>rfl @[inline]def yW(xr:Ж)(q:ф)(n ow:п)(W b:у т)(hs:Wв<2^32/\8*n<2^32) (hW:ow*n<=Wв) (g:п):A9:= let bq:=λr=>dw oneW*dw b[min (8*g) (ow-8)+r]! if h:xrе=n/\8<=ow then have hA:(min (8*g) (ow-8)*n)дб+8*nдб<=Wв:=by have h1:(min (8*g) (ow-8)+8)*n<=ow*n:=ψ n А;have:=ς;rw[Nat.add_mul]at h1;rw[aa А,aa А];omega have hB:nдб<=xrе:=by have:=ς;rw[aa А];omega if q then cH W xr (min (8*g) (ow-8)*n)д nд hs.1 hA hB 0 (bq 0) (bq 1) (bq 2) (bq 3) (bq 4) (bq 5) (bq 6) (bq 7) 0 else kw W xr (min (8*g) (ow-8)*n)д nд hs.1 hA hB 0 0 (bq 0) (bq 1) (bq 2) (bq 3) (bq 4) (bq 5) (bq 6) (bq 7) 0 0 else default @[specialize]def bS{α:Type}(f:п->α)(N:п)(a:у α):у α:= if aвα)(N:п): bS f N (Av N)=iZ (n:=N) λq=>f qи:=by suffices h:∀k (a:у α),N-aв=k->aв<=N->(∀i (h:i bS f N a=iZ (n:=N) λq=>f qиfrom h _ _ rfl (О) (λi h=>by simp at h) intro k;induction k with | zero=> intro a l j d;rw[bS,AP А];exact lR (by simp;omega) λi e _=>by rw[d i e,Ν] | succ k m=> intro a l j d;rw[bS,if_pos А];refine m _ (by simp;omega) (by simp;omega) λi h=>?_ rw[lz];split .exact d i ‹_› .grind def d8:Bool:=System.Platform.target.startsWith "aarch64" def cu(n ow:п)(relu:ф)(X W b:у т)(ix ib L:п) (hs:Wв<2^32/\8*n<2^32) (hW:ow*n<=Wв):у т:= if 8<=ow then let xr:=aM (λk=>dw X[k]!) n (An n) let q:=not d8&&!X.any (.<<<1==0) let Y:=bS (λg=>yW xr q n ow W b hs hW g) ((ow+7)/8) (Av ((ow+7)/8)) bS (λj=> let y:=Y[j/8]! let o:=j*n let S:=y.s.f (j-min (8*(j/8)) (ow-8)) let fb:=λ(_:Unit)=>aj n relu X W b (j/ow*n) 1 j let ts:=λ(_:Unit)=>tS relu L n (λs=>xr.get! s*dw W[o+s]!) (λ_=>dw oneW*dw b[j]!) fb let r:=λ(_:Unit)=>tG relu S (if h:(o+n)д<=W.usize then bM W _ h oд 0 else 255) ix ib L ts fb if q then tG relu S y.o ix ib L r r else tG relu S y.o ix ib L ts fb) (1*ow) (Av (1*ow)) else linearSpec 1 n ow relu X W b lemma cg(n l:п)(m:ф)(X W b:у iJ)(V M L:п) (J:Wв<2^32/\8*n<2^32) (H:l*n<=Wв) (N:п) (K:∀q:п,iG X[q]!≠255/\iL X[q]!<=V) (hb:∀q:п,iG b[q]!≠255/\iL b[q]!<=N) (S:174+N<=M) (hL:n+2<=2^L) (B:L<=27) (F:M+L<=425): cu n l m X W b V M L J H=jV 1 n l m X W b:=by unfold cu;split;rename_i h8;swap;rfl;unfold jV linearWith;dsimp only;simp only[gg,eh];congr 1;funext q;have hq:=q.isLt;have a0:0by subst h;simp at hq have hi:qи/l=0:=Χ А;have hj:qиdw X[k]!) n _ (iP n) rfl (by simp[iP,iX]) have u:∀sdw X[k]!) n (iP n)).data[s]! =dw X[0*n+s]!:=by intro s d;rw[x.2.2 _ (by simp[iP,iX]) d];simp generalize aM (λk=>dw X[k]!) n (iP n)=w at x u⊢ have hY:∀Q,(iZ (n:=(l+7)/8) λg=> yW w Q n l W b J H gи)[j/8]! = yW w Q n l W b J H (j/8):=λ_=>by rw[AL _ _ (by simp;omega),Ν] rw[hY] have hS:∀Q y,yW w Q n l W b J H (j/8)=y->∃k:п->ф,(∀s,k s=Л->(w.data[s]! ==0)=Л)/\ y.s.f (j-min (8*(j/8)) (l-8))= aP k (λs=>ai ((j-min (8*(j/8)) (l-8))%2==1) w.data[s]! W[j*n+s]!) n 0 (dw jN*dw b[j]!)/\(∀s(iG W[j*n+s]!)г<=y.oг)/\ (y.oг<255->∀s(iG W[j*n+s]!)г<255):=by rintro Q _ rfl;rw[yW];dsimp only;rw[As ⟨x.1,h8⟩];have A:nдб=n:=aa (by have:=ς;omega) set c:=min (8*(j/8)) (l-8)with as;have p:j-c<8/\c+(j-c)=j/\c+8<=l:=А have z:(c*n)дб=c*n:=by have Z:(c+8)*n<=l*n:=ψ n p.2.2;rw[lm]at Z;exact aa (by have:=ς;omega) have U:c*n+n*(j-c)=j*n:=by grind have v:∀s,(iG W[j*n+s]!)г=(iG W[(c*n)дб+nдб*(j-c)+s]!)г:= λs=>by rw[A,z,U] have I:=gI (λr=>dw jN*dw b[c+r]!) _ p.1 cases Q .rw[AP nofun] refine⟨λs=>w.data[s]! ==0,λ_ h=>h,?_,λs d G=>?_,λhR s d G=>?_⟩ .rw[(cs _ _ _ _ _ _ _ _ (j-c) p.1 _ _ _ _ _ _ _ _ _ _ _ _ rfl).1,I,A,z,ϝ,p.2.1,U] .exact(v s).trans_le ((cs _ _ _ _ _ _ _ _ (j-c) p.1 _ _ _ _ _ _ _ _ _ _ _ _ rfl).2.1 s (О) (by rw[A];exact d) G) .exact(v s).trans_lt (((cs _ _ _ _ _ _ _ _ (j-c) p.1 _ _ _ _ _ _ _ _ _ _ _ _ rfl).2.2.2 hR).2 s (О) (by rw[A];exact d) G) .rw[if_pos rfl] refine⟨λ_=>М,λ_=>nofun,?_,λs d _=>?_,λ_ _ _=>nofun⟩ .rw[(cI _ _ _ _ _ _ _ (j-c) p.1 _ _ _ _ _ _ _ _ _ _ _ rfl).1,I,A,z,ϝ,p.2.1,U] .exact(v s).trans_le ((cI _ _ _ _ _ _ _ (j-c) p.1 _ _ _ _ _ _ _ _ _ _ _ rfl).2.1 s (О) (by rw[A];exact d)) obtain⟨k,G,O,D,E⟩:=hS _ _ rfl;rw[O] have hE:∀sby have Z:j*n+n<=Wв:=by have:=ψ n (А:j+1<=l);rw[ώ]at this;omega have:=ς;split .exact(cX W _ ‹_› _ _ 0 rfl).2 _ (by rw[aa А];omega) (by rw[aa А];omega) .have:=a9 W[j*n+s]!;simp only[iO];omega have T:=λe v I=>eZ m n j (λt=>X[0*n+t]!) W b (λs=>w.data[s]!*dw W[j*n+s]!) (λs=>ai ((j-min (8*(j/8)) (l-8))%2==1) w.data[s]! W[j*n+s]!) e V M L N (λ_=>aj n m X W b (0*n) 1 j) k (λs _=>K _) v I (hb j) S hL B F (λs d v=>by rw[u s d];exact dt _ _ (K _).1 v) (λs d v=>by rw[u s d];exact el _ _ _ (K _).1 v) (λs d h=>by have Y:=G s h;rw[u s d]at Y;exact λ_=>bz _ _ (K _).1 Y) (by unfold aj;simp only[bs,jz]) have R:=T _ (λs d _=>hE s d) λh s d _=>(hE s d).trans_lt h split .exact iq _ _ _ _ _ _ _ _ _ _ _ (T _ D E) R R .exact T _ D E lemma dN(n:п)(e d:п->iJ):∀c i,i+c=n-> dallNZ (iZ (n:=n+1) λt=>if tиif tиe tи) (iZ (n:=n) λt=>d tи) i c:=by intro c;induction c with | zero=> intro i h;obtain rfl:i=n:=А simp only[dallNZ,ab (i+1) (λt=>if t< i then d t else jN) i А, ab (i+1) (λt=>if t< i then e t else 0x80000000) i А,Ar,if_false];rfl | succ c j=> intro i h rw[dallNZ,j (i+1) А,dallNZ,ab (n+1) (λt=>if tif tiJ)(j:0if tif tby split;exacts[(h t ‹_›).symm,Б],a8 _ _ _ h,ap, dN n d e n 0 А] congr 1 .simp only[Ar,if_false,(Б:tm jN 0x80000000=0),add_zero] exact Τ rfl λt l=>by simp only[if_pos (Κ.mp l)];unfold tm;rw[Ϙ];ring .simp[j.ne'] end F lemma iz(X:у iJ)(a n t:п)(d:tProp)(d:∀q:п,P X[q]!)(q:п): P (X.extract a e)[q]!:=by have:=d (a+q);have:=d Xв;grind lemma ed(r n e:п)(d:ф)(X W b:у iJ): jV r n e d X W b++jV 1 n e d (X.extract (r*n) (r*n+n)) W b= jV (r+1) n e d X W b:=by unfold jV linearWith;refine lR (by simp[lm]) λq l m=>?_ rw[Array.getElem_append];simp only[kX,Ν] split;. rfl rw[kX,Array.size_append,lm,Nat.one_mul]at* have h:q/e=r:=Nat.div_eq_of_lt_le А (by rw[ώ];omega) have j:q-r*eiG w≠255/\iL w<=_) m) j AO l h.2.2.2.1 h.2.2.1) .exact F.bB _ _ _ _ _ _ _ _ _ _ _ _ _ m j AO l h.2.2.2.1 h.2.2.1 .rfl def da(batch m k n:п)(A B:у т):у т:= let ea:=F.aY A 0 0 let eb:=F.aY B 0 0 let L:=BG (k+1)+1 if h:batch=1/\0by by_cases h:q< m<;>simp[h]<;>decide) AO (by have:=@Ϝ (k+1);omega) u r).trans ?_ rw[gemmSpec,gemmWith];refine lR (by simp[Ϧ]) λq e _=>?_ rw[kX]at e;have j:q/n< m:=϶ e;have x:(ka m (0x80000000:iJ))[q/n]! =0x80000000:=by simp[j] simp only[Ν,↓reduceIte,x,Χ (show q< m*n by rwa[Ϧ]), θ j,lG,ϥ] exact(F.dz k (λt=>A[q/n*k+t]!) (λt=>B[q%n+t*n]!) v λt _=>⟨(w _).1,(l _).1⟩).trans (by simp only[Ϙ (q%n)]) end Dense namespace Bn namespace NativeAdd lemma cD(x:Float32):ln x.toModel=ofW x.toBits:= congrArg Model.mk (ofUInt32_bits x.toBits).symm lemma eW(x:Float32):je (ln x.toModel)=x.toBits:= UInt32.ofNat_toNat lemma bc(a:iJ)(h:iG a≠255): (kt a).toBits=a/\(kt a).isFinite=Л:=by have j:lc (spec:=jc) a.toBitVec≠-1#8:=by intro d;apply h;apply Ι.mp rw[show(iG a)г=(a.toBitVec.extractLsb' 23 8).toNat by rw[iG,Ρ,ϔ,BitVec.extractLsb'_toNat];exact γ _ 8] exact(congrArg BitVec.toNat d:) have e:(kt a).toBits=a:=by change UInt32.ofBitVec (jj jc (iN jc a.toBitVec))=a rw[Model.pack_unpack_eq,AP (j ·.1)] refine⟨e,?_⟩;change (iN jc (kt a).toBits.toBitVec).isFinite=true;simp only[e,iN,j,AN];split<;>(try split)<;>rfl @[noinline]def c8(relu:ф)(a b:т):т:= act relu (toWord (Model.add (ofW a) (ofW b))) @[inline]def add(relu:ф)(a b:т):т:= if expOf a !=255&&expOf b !=255 then act relu (Be a+Be b).toBits else c8 relu a b lemma dW(d:ф)(a b:iJ): add d a b=act d (je (lp (ofW a) (ofW b))):=by rw[add];split .rename_i h simp only[Β,Am]at h;have e:=bc a h.1;have j:=bc b h.2;have l:=ExecFloat.Binary.toModel_ofFloat32_add_of_isFinite _ _ e.2 j.2;simp only[ExecFloat.Binary.toModel_ofFloat32,cD,e.1,j.1]at l;rw[<-l,<-cD,eW] .rfl end NativeAdd @[inline]def ad(rb:Е)(a b:т)(_slow:Unit->т):т:=NativeAdd.add (rb !=0) a b @[specialize]def bY(stop:х)(f:(i:х)->iбт->т)(i:х) (x:у т) (h:stopб<=xв):у т:= if hi:iiбiJ->iJ)(F:п->iJ->iJ) (m:∀i e w,f i e w=F iб w) (i:х) (x:у iJ) (h:dб<=xв): (bY d f i x h)в=xв/\ ∀j,(bY d f i x h)[j]?=if iб<=j/\j refine⟨by rw[l.1,ϲ],λj=>?_⟩ rw[l.2,Dense.ac e,lL,lB А];split_ifs<;>first | rfl | omega | (subst_vars;rw[kx А,Option.map_some,m];rfl) .next i x h e=>exact⟨Н,λj=>by rw[AP (by rw[β]at e;omega)]⟩ lemma xw(A X:п)(S:A<2^64)(N:X=(A+268435457)%2^64/2^29) (I:X=(A+268435453)%2^64/2^29) (K:(2^64-1195+X/2^23%2^11)%2^64<253) (L:X%2^23≠0): 1195<=A/2^52%2^11/\A/2^52%2^11<=1447/\2<=(A%2^52+2^28)%2^29/\ (A%2^52+2^28)%2^29+2<=2^29/\1<=A%2^52/\A%2^52+2<=2^52/\ X/2^34=A/2^63/\X%2^34=A/2^52%2^11*2^23+(A%2^52+2^28)/2^29:=by have o:1195<=X/2^23%2^11/\X/2^23%2^11<=1447:=А;clear K obtain⟨s,E,f,rfl,V,F,U⟩:∃s E f,A=s*2^63+E*2^52+f/\s<2/\E<2^11/\f<2^52:= ⟨A/2^63,A/2^52%2^11,A%2^52,А,А,А,А⟩ rw[(А:(s*2^63+E*2^52+f)/2^63=s),show(s*2^63+E*2^52+f)/2^52%2^11=E by omega,(А:(s*2^63+E*2^52+f)%2^52=f)] have v:s*2^63+E*2^52+f+268435457<2^64:=by by_contra M;have:X=0:=А;omega rw[θ v]at N;rw[θ (kp (Nat.add_le_add_left (by norm_num:268435453<=268435457) _) v)]at I obtain⟨q,r,rfl,x⟩:∃q r,f=q*2^29+r/\r<2^29:=⟨f/2^29,f%2^29,А,А⟩ have m:X=s*2^34+E*2^23+q+(r+268435457)/2^29:=А;have J:X=s*2^34+E*2^23+q+(r+268435453)/2^29:=А;have w:r+1≠2^28/\r≠2^28/\r≠2^28+1:=А;rw[(А:(r+268435457)/2^29=(r+2^28)/2^29)]at m have G:(r+2^28)/2^29<=1:=А;generalize j:(r+2^28)/2^29=d at m G;have t:X=(q+d)+(E+s*2^11)*2^23:=by rw[m];ring have e:X%2^23=(q+d)%2^23:=by rw[t,Ο] have l:q+d<2^23:=by by_contra M;rw[(А:q+d=2^23),Nat.mod_self]at e exact L e rw[θ l]at e have y:X/2^23%2^11=E:=by rw[t,ό _ _ Г,Χ l,ϥ,Ο, θ F] rw[y]at o have u:E*2^23+(q+d)<2^34:= calc E*2^23+(q+d)r<2^28:=by intro H;rw[H]at j;clear*-j x;omega clear*-O Q G x;omega have B:1<=q*2^29+r:=by rcases Nat.eq_zero_or_pos r with h | h .subst h;rw[show d=0 by rw[<-j];norm_num]at e have:2^29<=q*2^29:=kM _ А;clear*-this;omega .clear*-h;omega rw[z,ό _ _ Г,Ο,j,p,ό _ _ Г,Χ u,Ο,θ u] refine⟨o.1,o.2,by clear*-x w;omega,by clear*-x w;omega,B,D,А,by ring⟩ lemma eK(d:ф)(a b:iJ)(e:Unit->iJ) (h:e ()=act d (je (lp (ofW a) (ofW b)))): ad (if d then 1 else 0) a b e=act d (je (lp (ofW a) (ofW b))):=by cases d<;>simp[ad,NativeAdd.dW] @[noinline]def gi(relu:ф)(x y:т):т:=act relu (toWord (Model.add (ofW x) (ofW y))) def bA(relu:ф)(a b:у т):у т:= if h:aв<=bв/\aв let y:=b.uget i (by rw[Dense.aa h.2]at hi;omega) ad rb x y λ_=>gi relu x y) 0 a (by rw[Dense.aa h.2]) else addReluSpec relu a b lemma co:bA=addReluSpec:=by funext d a b;unfold bA;dsimp only split;swap;. rfl rename_i h;have l:=Dense.aa h.2;refine lC λj=>?_ rw[(cV _ _ (λj x=>act d (je (lp (ofW x) (ofW b[j]!)))) (λi m x=>?_) 0 a _).2 j, addReluSpec,ls] .by_cases e:jrw[h]<;>norm_num lemma gN{n:п}(h:n<2^32):n%2^kJ=n:=θ (lt_of_lt_of_le h eD) lemma aa(n:п)(h:n<2^32):nдб=n:=gN h end Conv section open Float.Model.UnpackedFloat local notation "ZA" =>rationalWord local notation "ZB" =>Array Word local notation "ZC" =>Core.mW local notation "ZD" =>Core.iW local notation "ZE" =>FloatFormat.toModel Fmt local notation "ZF" =>AB local notation "ZG" =>UInt64.toNat_ofNat' local notation "ZH" =>AG local notation "ZI" =>Core.aU local notation "ZJ" =>Nat.div_eq_zero_iff_lt local notation "ZK" =>sqrtLower local notation "ZL" =>AI local notation "ZM" =>BJ local notation "ZO" =>mantOf_lt_24 local notation "ZQ" =>AH local notation "ZR" =>Core.ao local notation "ZS" =>Core.bk local notation "ZT" =>roundRational local notation "ZU" =>Nat.div_add_mod' local notation "ZV" =>Nat.div_le_self local notation "ZW" =>mantOf local notation "ZX" =>signOf local notation "ZY" =>Aa local notation "ZZ" =>idxOf local notation "XA" =>AN local notation "XB" =>Ap local notation "XC" =>two_ne_zero' local notation "XD" =>Ad local notation "XE" =>ExtendedMantissa.ofMantissaAndAccuracy local notation "XF" =>UInt64.ofNat local notation "XG" =>Bool.xor local notation "XH" =>rowVariance local notation "XI" =>(А) local notation "XJ" =>(В) local notation "XK" =>(by simp) namespace Norm def Ya:Accuracy->п | .exact=>0 | .inexact _=>1 lemma Yc{α:Type}(f:α->α)(n:п)(a:α): Nat.repeat f (n+1) a=Nat.repeat f n (f a):=by induction n generalizing a with | zero=>rfl | succ n d=>exact congrArg f (d a) lemma QA(R k:п)(d:Accuracy): XE (2*R+Ya d) .exact>>>(k+2)= XE R d>>>(k+1):=by show Nat.repeat jk (k+2) _= Nat.repeat jk (k+1) _ rw[Yc,Yc,Yc];congr 1;rcases d with _ | ⟨_ | _ | _⟩<;> simp[ExtendedMantissa.ofMantissaAndAccuracy,jk,Ya]<;>omega open FloatLib.Numerics in lemma VY(q r D t:п)(e:0rfl,<-h, show(q*D+r)/D=q by rw[Ϙ,ό _ _ e,Χ d,Ak], show(q*D+r)%D=r by rw[Ϙ,Ο,θ d]] lemma Y5(e:р):Model.bpow e=(2:ℝ)^e:=С lemma Vi(q b:п)(d:q≠0)(j:b<=1):(2*q+b)з=qз+1:=by have e:=jQ d;have h:=Ϝ (n:=q);rw[kR XI];omega open FloatLib.Numerics in lemma V0(s:ф)(P d:п)(p:P≠0)(m:d≠0)(q r D:п) (y:0omega have h:=Vi q _ l z;have H:(r:ℝ)/D<1:=by rw[div_lt_one XJ];exact_mod_cast u have F:(0:ℝ)<=r/D:=XJ;push_cast at v w;have x:RationalBinary.floorLog2 P d=(qз:р)+e:=by apply Model.floorLog2_eq_of_bounds P d _ p m .rw[j,Y5,ZL ZQ,ZF];gcongr;grind .rw[j,Y5,show(qз:р)+e+1=((qз+1:п):р)+e by push_cast;ring,ZL ZQ,ZF];gcongr;linarith have t:kA (jL P d (23-((qз:р)+e))).1 (jL P d (23-((qз:р)+e))).2= roundShiftRightEven (2*q+if r=0 then 0 else 1) ((2*q+if r=0 then 0 else 1)з-23):=by rw[roundShiftRightEven_eq_roundQuotientEven,h,show qз+1-23=(qз-23)+1 by clear*-o h;omega,<-VY q r D _ y u XI] apply Model.roundQuotientEven_eq_of_rat_eq _ _ _ _ (RationalBinary.scaleByPowerOfTwo_snd_ne_zero _ _ _ m) XJ rw[Model.scaleByPowerOfTwo_real];unfold Model.scaledRatToReal;rw[j,Y5,XD,<-ZL ZQ, show e+(23-((qз:р)+e))=-((qз-23:п):р) by clear*-o h;omega, zpow_neg,ZF] push_cast;field_simp generalize G:2*q+(if r=0 then 0 else 1)=J at h t⊢;rw[iI,ite_eq_left Б,Model.ieeeRoundDyadic_eq_ieeeRoundDyadicImpl];simp only[Model.roundRat,Model.roundRatScaled,(Б:Fmt.isIEEE=true),↓reduceDIte, Model.ieeeRoundRatScaled,Model.ieeeRoundDyadicImpl,ZY,p,m,XA,x, Int.add_zero,j0,h,(Б:(FloatFormat.ieeeMaxNormalExponent kD:р)=127), show FloatFormat.ieeeMinNormalExponent kD=-126 by decide, show(FloatFormat.normalMantissaExpOffset kD:р)=150 by decide, show Fmt.fracWidth=23 by decide,show J≠0 by omega, show((qз+1:п):р)+(e-1)=(qз:р)+e by push_cast;ring, show¬((qз:р)+e>127) by omega,show¬((qз:р)+e< -150) by omega, show¬((qз:р)+e< -126) by omega,(А:23<=qз+1),AV, jI,t] lemma Y8(v:ℚ)(x:v≠0)(s:ф)(w:decide (v<0)=s) (q:п) (ρ:ℚ) (p:0<=ρ) (h:ρ<1) (e:р) (l:|v|=((q:ℚ)+ρ)*(2:ℚ)^e) (t:2^25<=q) (m:-126<=(qз:р)+e) (o:(qз:р)+e<=126): ZT v= je (iI kD ⟨s,2*q+(if ρ=0 then 0 else 1),e-1⟩):=by have j:ρ=(ρ.numл:ℚ)/ρ.den:=by conv_lhs=>rw[<-Rat.num_div_den ρ] congr 1;exact_mod_cast(kd (Rat.num_nonneg.mpr p)).symm have d:=ρ.den_pos;generalize ρ.den=D,ρ.numл=r at j d;subst j;have u:r(z:ℝ)) l;rw[Rat.abs_def,Rat.divInt_eq_div]at this;push_cast at this;rwa[kb,ϊ] lemma Q7(R:п)(s:р)(h:2^25<=R): -s+1<=(ZE).targetExponent (i0 R (-s)):=by have:=(jA XI).2 h;have:(ZE).mantissaBits<=25:=Б;rw[Bi,i0];omega lemma Vd(v:ℚ)(r:0simp lemma YN(w:iJ):(sv w:ℚ)=0↔ZW w=0:=by rw[sv];split_ifs<;>simp lemma Vr(w:iJ):(sv w:ℚ)=(if ZX w then-1 else 1)*ZW w:=by rw[sv];simp lemma Y7(x:Д):(ZR x)а=xаз:=by rw[aK];rfl lemma YK(w:iJ):(ZC w==0)=decide (ZW w=0):=by by_cases h:ZW w=0 .have:ZC w=0:=χ.mp (by rw[ZI,h];rfl);grind .have:ZC w≠0:=λd=>h (by rw[<-ZI,d];rfl) grind lemma Yk(n:п)(f:п->ℚ)(a:ℚ): (List.range n).foldl (λt j=>t+f j) a=a+∑j∈ZM n,f j:=by induction n generalizing a with | zero=>simp | succ n d=> rw[List.range_succ,List.foldl_append,d,Ξ];simp;ring def Yf(num den:п)(s:р):т:= toWord (Model.ofModel Fmt (roundWithAccuracy (ZE) .positive (ZK num den) (-s) (sqrtAccuracy num den))) open Float.Model in lemma Q4(spec:Format)(h:lI)(R:п)(e:р)(d:Accuracy)(m:R≠0) (q:e+1<=spec.targetExponent (i0 R e)): kB spec h R e d=lu spec h (2*R+Ya d) (e-1):=by have o:Ya d<=1:=by cases d<;>simp[Ya] have j:i0 (2*R+Ya d) (e-1)=i0 R e:=by unfold i0;rw[Vi R _ m o];omega unfold lu decreaseExponent;simp only[j];rw[(А:(e-1-spec.targetExponent (i0 R e))л=0)];simp;unfold kB shiftToTargetExponent shiftToExponent;rw[j];generalize p:spec.targetExponent (i0 R e)=T at* have⟨k,l⟩:∃k,(T-e)л=k+1:=⟨(T-e)л-1,XI⟩;dsimp only;rw[l,(А:(T-(e-1))л=k+2),QA,show e-1+((k+2:п):р)=e+((k+1:п):р) by push_cast;ring] lemma Vh(e d:п): Ya (sqrtAccuracy e d)=if e=ZK e d^2*d then 0 else 1:=by unfold sqrtAccuracy;dsimp only;split_ifs<;>rfl lemma V9(e d:п)(s:р)(q:33554432<=ZK e d) (m:ZK e d>>>31=0) (o:-209<=s) (p:s<=297): Yf e d s=aw false (XF (2*ZK e d+ (if e=ZK e d*ZK e d*d then 0 else 1))) (XF (297-s)л):=by set R:=ZK e d with h have j:(XF (297-s)л)а=(297-s)л:=by rw[ZG,θ XI] have r:(if e=R*R*d then 0 else 1)<=1:=by split_ifs<;>omega have l:(XF (2*R+(if e=R*R*d then 0 else 1)))а= 2*R+(if e=R*R*d then 0 else 1):=by rw[ZG,θ XI] rw[aO _ _ _ XI,j,l];rw[Yf];rw[<-h,Q4 _ _ R (-s) _ XI (Q7 R s XI),Vh,<-h,sq, show(((297-s)л:п):р)-298=-s-1 by omega] rfl def V8(B:п)(c:р):п:=if 0<=c then B<<rw[Ζ] .refine⟨e,?_⟩;push_cast;rw[<-ZF (2:ℚ) cл,(А:((cл:п):р)=c)];ring .refine⟨XJ,?_⟩;push_cast;rw[<-ZF (2:ℚ) (-c)л,(А:(((-c)л:п):р)=-c)];have:(2:ℚ)^(-c)≠0:=XJ;rw[zpow_neg];grind @[inline]def V2(r:п)(st:ф):п:=if r !=0||st then 1 else 0 lemma VI(N M:п)(e:0decide (v<0)=s) (q:0<=δ) (r:δ<1) (x:m=Л↔δ≠0) (y:0simp only[AV,μ,AN]at l⊢<;>rw[x]at l<;> constructor<;>linarith only[l,t,u,q,r] end NF namespace NE open NF Dense.F open Dense (aA) @[inline]def mx(a b:Д):Д:=if arename_i h<;>rw[ν]at h<;>omega @[inline]def pk(s:ф)(q σ:Д):т:= ((if s then(0x80000000:Д)else 0)+((σ-146)<<<23+Core.ah (((2:Д)*q+1)<<<36)))м lemma fT(s:ф)(q σ:Д)(l:2^25<=qа)(m:qа<2^26)(o:146<=σа) (p:σа<=398):pk s q σ=aw s ((2:Д)*q+1) σ:=by have d:((2:Д)*q+1)а=2*qа+1:=by rw[ξ,Ϫ];simp only[iE];omega have h:(((2:Д)*q+1)<<<36)а=(2*qа+1)*2^36:=by rw[Η,d];simp only[iE,iM,Ζ];omega have j:(σ-36)а=σа-36:=by rw[υ σ 36 (κ.2 (by simp only[iE];omega))];rfl have e:aw s ((2:Д)*q+1) σ=aw s (((2:Д)*q+1)<<<36) (σ-36):=by rw[cQ s ((2:Д)*q+1) σ А А, cQ s (((2:Д)*q+1)<<<36) (σ-36) А А,d,h,j, show(2:р)^σа=2^36*2^(σа-36) by rw[<-AK,Nat.add_sub_cancel' (А:36<=σа)]] cases s<;>simp only[AV,AN,μ]<;>push_cast<;>ring_nf have r:(pk s q σ)г=(if s then 2^31 else 0)+((σа-146)*2^23+ (ah (((2:Д)*q+1)<<<36))а):=by obtain⟨-,-,u⟩:=bT s (((2:Д)*q+1)<<<36) (σ-36) А А А А;unfold pk rw[Ϡ,ξ,ξ,Η, υ σ 146 (κ.2 (by simp only[iE];omega))] cases s<;>simp only[AV,AN,μ,iE,iM,Ζ]<;>omega obtain⟨t,-,-⟩:=bT s (((2:Д)*q+1)<<<36) (σ-36) А А А А;rw[e];apply Ι.mp;omega lemma pB(a b:ℝ)(p q:ℕ)(d:|a|<=2^p)(e:|b|<=2^q):|a*b|<=2^(p+q):=by rw[AM,AK];exact Af d e (AF _) В lemma mo(a:ℝ)(p q:ℕ)(h:|a|<=2^p)(d:p<=q):|a|<=2^q:= h.trans (AC Г d) lemma z9(a:ℝ)(p:ℕ)(h:|a|<=2^p)(d:p<=971):|a|<=(2:ℝ)^(971:ℤ):=by rw[show(971:ℤ)=((971:ℕ):ℤ)fromН,AB];exact mo a p 971 h d lemma wB(w:iJ):|(sv w:ℝ)*2^iL w|<=2^(24+iL w):=by rw[AM,AJ (by positivity:(0:ℝ)<2^idxOf w),AK] have:|(sv w:ℝ)|<=2^24:=by rw[<-ϊ,ϳ];exact_mod_cast(cn w).le exact AA this В end NE namespace NR open NF Dense.F open Dense (aA) @[inline]def pt(j:п):с:=P.get! (j+1) @[inline]def p2(e:п):с:=pt (min e 254)*pt (e-min e 254) lemma gX(j:п)(l:j<=254):fv (pt j)/\rv (pt j)=(2:ℝ)^j:=by have h:pt j=pw j:=by have d:P.get! (j+1)=P.data[j+1]!:=by rcases P with⟨e⟩;rfl rw[pt];rw[d,AL P.data (j+1) (by simp[P];omega)] simp only[P,Ν];rw[if_pos А];rfl rw[h];exact fX j А lemma gT(n:п)(h:n<2^29):fv nж.toInt64.toFloat/\rv nж.toInt64.toFloat=n:=by have d:nжа=n:=Θ (А:n<2^64) have e:nж.toInt64н=n:=by show bl nж=n;rw[aA,d];split<;>omega have:=cG _ (by rw[e];simp;omega);rw[e]at this;omega lemma d5(a:ZB)(h:∀i (d:iα)(h:k< m): (iZ f)[k]! =f ⟨k,h⟩:=by rw[AL _ k (by simpa using h),Ν] @[inline]def SN(rows n:п)(eps:т)(x g:ZB):ф:= rows>0&&n>0&&xв==rows*n&&gв==n&&x.all finiteWord&&g.all finiteWord&&finiteWord eps&&(!ZX eps&&ZC eps !=0) lemma eJ(e n:п)(d:iJ)(x g:ZB):SN e n d x g=iU e n d x g:=by rw[SN,iU];congr 1;rw[Q6,Y2];have:(0:ℚ)<2^((ZZ d:р)-149):=XJ;rw[sg];cases ZX d<;>simp[this,BV] lemma fj{d n:п}{e:iJ}{x g:ZB}(h:iU d n e x g=Л): 0iG x[i]!≠255)/\∀j,jiG g[j]!≠255:=by simp only[iU,Β,ZH,A4]at h;have p:xв=d*n:=by simpa using h.1.1.1.1.1.2 have l:gв=n:=by simpa using h.1.1.1.1.2 exact⟨h.1.1.1.1.1.1.2,h.2,λi m=>NR.d5 x (by simpa[kC]using h.1.1.1.2) i А, λj o=>NR.d5 g (by simpa[kC]using h.1.1.2) j А⟩ namespace NF open Dense.F lemma gm(x y:с)(d:fv x)(e:fv y): iH (x-y).toModel=Model.sub (iH x.toModel) (iH y.toModel):=by change iH (lW x.toModel y.toModel)=_;rw[lW,ϫ] have h:=Model.sub_eq_ofModel_sub_of_isFinite (fmt:=iF) Б (iH x.toModel) (iH y.toModel) (by rw[Ε];exact(bG x).1 d) (by rw[Ε];exact(bG y).1 e) rw[Ε,Ε]at h;exact h.symm lemma gK(x y:с)(d:fv x)(e:fv y)(l:|rv x-rv y|<=jp (ko iF)): fv (x-y)/\rv (x-y)=jW iF (rv x-rv y):=by have j:=gm x y d e have h:=Model.isFinite_sub_of_abs_toReal_sub_le_posMaxFinite (iH x.toModel) (iH y.toModel) Б d e l refine⟨by rw[fv];rw[j];exact h,?_⟩ rw[rv];rw[j];exact Model.toReal_sub_eq_roundAt _ _ Б d e h lemma ip(x:с):jY (iH x.sqrt.toModel)=jY (Model.sqrt (iH x.toModel)):=by change jY (iH (lS x.toModel))=_;rw[lS,ϫ,show jb=FloatFormat.binary64.toModel fromН];have h:=Model.canonicalizeModel_sqrt_eq_model (fmt:=iF) Б (iH x.toModel);rw[Ε]at h;rw[<-h,Model.toModel_canonicalizeModel] lemma gQ{y z:Model iF}(h:jY y=jY z):kk y=kk z/\jp y=jp z:=by constructor .rw[<-Ϟ,Ϯ _ Б,<-Ϟ,Ϯ _ Б,h] .rw[ϐ Б,ϐ Б,h] lemma io(x:с)(m:fv x)(h:0rfl | true=> exfalso;rw[e]at h;simp only[jg,l]at h;have:(0:ℝ)<=(d.significand:ℝ)*(2:ℝ)^d.exponent:=В;simp only[jl,l]at h;rw[j0]at h;push_cast at h;linarith lemma gJ(x:с)(e:fv x)(j:0norm_num rw[Au]at m;generalize (1:ℝ)/2^1075=τ at* refine⟨j,?_⟩;rw[show rv r-1/rv y=(rv r*rv y-1)/rv y by field_simp,BN,AJ d];gcongr norm_num at*;linarith end NF open NF Dense.F @[inline]def pq(B:Д):т:=(((B>>>63)<<<31)+(((B&&&0x7FFFFFFFFFFFFFFF)+268435456)>>>29)-((1045:Д)<<<23))м lemma ic(q:Д)(h:qа<2^26):(ah ((2*q+1)<<<36))а=(qа+2)/4:=by have e:((2*q+1)<<<36)а=(2*qа+1)*2^36:=by simp only[Η,ξ,Ϫ,iE,iM,Ζ];omega unfold ah;simp only[ο,ξ,Α,e,iE,iM,ι,ju];generalize qа=a at* obtain⟨k,j,d,rfl⟩:∃k j,j<8/\a=8*k+j:=⟨a/8,a%8,ϩ _ Г,(js a 8).symm⟩;interval_cases j<;>omega lemma gC(B:Д):(eF B)а=Bа/2^52%2048:=by unfold eF;rw[Α,ο];simp only[iE,iM,ι];exact γ _ 11 lemma gS(B:Д):(mF B)а=Bа%2^52+2^52:=by rw[fH,Α];congr 1;exact γ _ 52 lemma gV(B:Д)(d:146<=(eF B-900)а)(e:(eF B-900)а<=398):pq B=NE.pk (B>>>63!=0) (mF B>>>27) (eF B-900):=by have h:(eF B)а=Bа/2^52%2048:=by unfold eF;rw[Α,ο];simp only[iE,iM,ι];exact γ _ 11 have j:=fH B;have r:(B&&&0xfffffffffffff)а=Bа%2^52:=by rw[Α];exact γ _ 52 have l:(B>>>63)а=Bа/2^63:=by rw[ο];simp only[iE,iM,ι] have q:(B&&&0x7FFFFFFFFFFFFFFF)а=Bа%2^63:=by rw[Α];exact γ _ 63 have u:=B.toNat_lt;rw[r]at j;have m:(mF B>>>27)а=(Bа%2^52+2^52)/2^27:=by rw[ο,j];simp only[iE,iM,ι] have p:(eF B-900)а=Bа/2^52%2048-900:=by rw[Λ,h];simp only[iE]at d e⊢;rw[Λ,h]at d e;simp only[iE]at d e;omega have o:=ic (mF B>>>27) (by rw[m];omega) rw[m]at o have t:(B>>>63!=0)=decide (Bа/2^63=1):=by rw[Ϥ];simp only[Am,BU,AG,<-χ,l,iE];omega apply Ι.mp;rw[pq,NE.pk];rw[t] simp only[Ϡ,ξ,Λ,Η,ο, l,q,p,o,iE,iM,Ζ,ι] rw[p]at d e;generalize Bа=N at* split<;>simp only[iE,AG]at*<;>omega lemma fU(B:Д)(d:1046<=(eF B)а)(e:(eF B)а<=1298):pq B=NE.pk (B>>>63!=0) (mF B>>>27) (eF B-900):=by have:(eF B-900)а=(eF B)а-900:=υ _ _ (κ.2 (by simp only[iE];omega)) exact gV B А А lemma tc(B c:Д)(m:c<=25)(h:(B&&&0x7FFFFFF)-((1:Д)<<0 by norm_num) omega lemma te(E:Д)(h:E-1046<=252):1046<=Eа/\Eа<=1298:=by have d:=κ.1 h;rw[Λ]at d;have:=E.toNat_lt;simp only[iE]at d;omega lemma cl(V:с)(x:fv V)(c:ℕ)(Z:ℝ)(j:1046<=(eF V.toBits)а)(r:(eF V.toBits)а<=1298) (l:2^c>>27)а/\(mF V.toBits>>>27)а<2^26/\ ((mF V.toBits>>>27)а:ℝ)*2^(((eF V.toBits)а:р)-1048)<(if V.toBits>>>63!=0 then-Z else Z)/\ (if V.toBits>>>63!=0 then-Z else Z)<(((mF V.toBits>>>27)а:ℝ)+1)*2^(((eF V.toBits)а:р)-1048):=by have p:¬eF V.toBits=0:=λh=>by rw[h]at j;simp at j have d:=aS V x p;rw[aD]at d;have q:=gS V.toBits;have t:(V.toBits&&&0xfffffffffffff)а=V.toBitsа%2^52:=by rw[Α];exact γ _ 52 rw[t,show V.toBitsа%2^52+2^52=(mF V.toBits)а by rw[q]]at d have u:V.toBitsа%2^27=(mF V.toBits)а%2^27:=by rw[q];omega rw[u]at l m;have o:=eY _ Z _ _ _ _ c В d rfl l m v;have w:(mF V.toBits>>>27)а=(mF V.toBits)а/2^27:=by rw[ο];simp only[iE,iM,ι] have y:=V.toBits.toNat_lt have e:(2:ℝ)^27*2^(((eF V.toBits)а:р)-1075)=2^(((eF V.toBits)а:р)-1048):=by rw[<-AB,<-AI Г];congr 1;push_cast;ring rw[w];refine⟨А,А,?_,?_⟩ .rw[<-e,<-Ad];exact o.1 .rw[<-e,<-Ad];exact o.2 lemma eC(V:с)(L:fv V)(c:ℕ)(Y:ℚ)(m:1046<=(eF V.toBits)а)(o:(eF V.toBits)а<=1298) (t:2^c>>27)аwith K;set s:=V.toBits>>>63!=0 with O;set E:=(eF V.toBits)аwith N;set e:ℤ:=(E:ℤ)-1197 with v;have k:∀a:ℝ,a*2^((E:ℤ)-1048)=a*2^e*2^149:=λa=>by rw[Ad,<-AB (2:ℝ) 149,<-AI Г];congr 2;rw[v];push_cast;ring have G:(if s then-((Y:ℝ)*2^149)else(Y:ℝ)*2^149)=((if s then-Y else Y:ℚ):ℝ)*2^149:=by split<;>push_cast<;>ring rw[k,G]at H;rw[k,G]at F;have B:=Ao H В;have w:=Ao F В;have r:(q:ℚ)*2^e<(if s then-Y else Y):=by exact_mod_cast(by push_cast;ring:(((q:ℚ)*2^e:ℚ):ℝ)=(q:ℝ)*2^e).trans_lt B have x:(if s then-Y else Y)<((q:ℚ)+1)*2^e:=by exact_mod_cast w.trans_eq (by push_cast;ring:((q:ℝ)+1)*2^e=((((q:ℚ)+1)*2^e:ℚ):ℝ)) have p:(0:ℚ)<2^e:=В;have l:0<(if s then-Y else Y):=Ac В r;have d:|Y|=(if s then-Y else Y):=by grind set δ:ℚ:=(if s then-Y else Y)/2^e-q with y;have z:0<δ:=by rw[y,sub_pos,lt_div_iff₀ p];exact r have A:δ<1:=by rw[y,sub_lt_iff_lt_add,div_lt_iff₀ p];linarith only[x] have j:qз=25:=BI (BF.1 ((lf А).2 I)) ((jA А).2 D) rw[<-Qx s q Л 1 e Y δ ((2:Д)*(mF V.toBits>>>27)+1) (eF V.toBits-900) (by intro _;split at d<;>rename_i h<;>simp only[h,AV,μ,AN]at l⊢<;> simp only[AG,decide_eq_false_iff_not,not_lt]<;>linarith only[l]) z.le A (by grind) one_pos (by rw[d,y];field_simp;ring) (by simpa using D) (by simp[j];omega) (by simp[j];omega) (by rw[ξ,Ϫ];simp[V2,<-K];omega) (by rw[M];omega)] lemma dC(t:с)(O:fv t)(w:ℕ)(v:ℚ)(r:0>>27)аwith Z;set E:=(eF t.toBits).toNat with X;have Y:0>>63!=0)=false:=by by_contra h;simp only[Bool.not_eq_false]at h;rw[if_pos h]at m;linarith[show(0:ℝ)<=(q:ℝ)*2^((E:ℤ)-1048) by positivity] rw[J]at m p;simp only[μ,AN]at m p;set s:ℤ:=1197-E with N;have k:(2:ℝ)^149=2^s*2^((E:ℤ)-1048):=by rw[<-AB,<-AI AH];congr 1;omega rw[k,<-Ad]at m p;have Q:=Ao m В;have S:=Ao p В have l:(iK v*2^s)^2=(v:ℝ)*2^(2*s):=by rw[mul_pow,kP (by exact_mod_cast r.le),<-AB,<-zpow_mul];ring_nf have D:(q:ℝ)^2<(v:ℝ)*2^(2*s):=by rw[<-l];exact pow_lt_pow_left₀ Q В Г have F:(v:ℝ)*2^(2*s)<((q:ℝ)+1)^2:=by rw[<-l];exact pow_lt_pow_left₀ S В Г have M:0(z:ℝ)) u;push_cast at this;exact this rw[<-H]at D F;have I:(0:ℝ)this ((az w).1 d)) have r:(iG w)г≠255:=by rw[j,h];omega refine⟨λd=>r (by rw[d];rfl),p,?_⟩ have e:iG w≠0:=λd=>by rw[d]at j;simp at j;omega unfold sv jd iL;rw[p,AP e,AP e];simp only[μ,AN];rw[u,j,h];rcases Nat.lt_or_ge R (2^24)with t|t .have m:(K*2^23+R)/2^23%256=K+1:=А have o:(K*2^23+R)%2^23=R-2^23:=А;rw[m,o,(А:K+1-1=K),Nat.cast_add,kN q];push_cast;ring .have l:R=2^24:=А subst l;have m:(K*2^23+2^24)/2^23%256=K+2:=А;have o:(K*2^23+2^24)%2^23=0:=А;rw[m,o,(А:K+2-1=K+1)];push_cast;ring lemma gW(B:Д)(t:1046<=(eF B)а)(u:(eF B)а<=1298)(j:Bа<2^63): (pq B)г=((eF B)а-1046)*2^23+(2^23+(Bа%2^52+2^28)/2^29):=by have r:=gC B;have d:(eF B)а=Bа/2^52:=by rw[r];exact θ А have l:((B>>>63)<<<31)а=0:=by rw[Η,ο];simp only[iE,iM,ι,Ζ];rw[Χ j] have m:(B&&&0x7FFFFFFFFFFFFFFF)а=Bа:=by rw[Α];simp only[iE];rw[show 0x7FFFFFFFFFFFFFFF=2^63-1 by norm_num,γ];exact θ j have o:(((B&&&0x7FFFFFFFFFFFFFFF)+268435456)>>>29)а=(Bа+2^28)/2^29:=by rw[ο,ξ,m];simp only[iE,iM,ι];rw[θ А];norm_num have p:(Bа+2^28)/2^29=Bа/2^52*2^23+(Bа%2^52+2^28)/2^29:=А have e:(((B>>>63)<<<31)+(((B&&&0x7FFFFFFFFFFFFFFF)+268435456)>>>29))а=(Bа+2^28)/2^29:=by rw[ξ,l,o,Ak];exact θ А have h:((1045:Д)<<<23)а=1045*2^23:=Б have q:(((B>>>63)<<<31)+(((B&&&0x7FFFFFFFFFFFFFFF)+268435456)>>>29)-((1045:Д)<<<23))а=(Bа+2^28)/2^29-1045*2^23:=by rw[υ _ _ (κ.2 (by rw[e,h];omega)),e,h] unfold pq;rw[Ϡ,q,p,d];omega lemma bP(b:с)(j:fv b)(m:0>>63!=0)=М:=by by_contra d;rw[Bool.not_eq_false]at d;rw[d,if_pos rfl]at h;have:(0:ℝ)<=((b.toBits&&&0xfffffffffffff)а+2^52:ℕ)*(2:ℝ)^(((eF b.toBits)а:р)-1075):=В;push_cast at this h;linarith rw[e]at h;simp only[μ,AN]at h;refine⟨?_,?_⟩ .have:b.toBits>>>63=0:=by simpa using e have:=congrArg jE this;rw[ο]at this;simp only[iE,iM,ι]at this;have:=BY b.toBits;omega .rw[h];congr 2;rw[Α];simp only[iE];rw[show(0xFFFFFFFFFFFFF:ℕ)=2^52-1 by norm_num,γ] lemma gU(b:с)(o:fv b)(l:0by rw[h]at d;simp at d) have r:=gW b.toBits d m p;have⟨x,y,z⟩:=wV _ _ _ r А А А;refine⟨x,y,?_⟩;rw[z,q];set E:=(eF b.toBits)а;set F:=b.toBitsа%2^52;set R:=2^23+(F+2^28)/2^29;have t:R*2^29<=F+2^52+2^28:=А;have u:F+2^52+2^28dw a[j]!) aв (An aв) lemma ax(a:ZB):(ba a)е=aв/\∀j,j(ba a).data[j]! =dw a[j]!:=by have d:(iP aв)е=0:=rfl;obtain⟨e,-,h⟩:=bj (λj=>dw a[j]!) aв aв _ (by rw[d];omega) (by rw[d];omega) exact⟨e,λj l=>h j (by rw[d];omega) l⟩ lemma ey(X:Ж)(i:х)(h:iбс)(x:ZB)(e:х)(he:eб<=xв)(hb:eб+1<2^32)(i:х)(hi:iб<=eб)(s t:с):с:= have:=ς if h:i+1с)(x:ZB)(e:х)(O:eб<=xв)(N:eб+1<2^32)(d:п)(w:п->ℝ) (v:∀k,d<=k->kfv (f x[k]!)/\|rv (f x[k]!)|<=w k) (V:∑k∈i9 d eб,w k<=2^960) (hn:eб<=d+2^29) (i:х) (W:iб<=eб) (s t:с) (c:п) (m q o r:ℝ) (hc:iб=d+2*c) (G:fv s) (H:fv t) (E:|rv s-m|<=c*((1/2^53+1/2^73)*o+1/2^1074)) (F:|rv t-q|<=c*((1/2^53+1/2^73)*r+1/2^1074)) (y:|m|<=o) (z:|q|<=r) (M:m+q=∑k∈i9 d iб,rv (f x[k]!)) (l:o+r=∑k∈i9 d iб,w k): fv (PP f x e O N i W s t)/\|rv (PP f x e O N i W s t)-∑k∈i9 d eб,rv (f x[k]!)|<= (((eб-d:ℕ):ℝ)+3)/2*((1/2^53+1/2^73)*∑k∈i9 d eб,w k)+(((eб-d:ℕ):ℝ)+1)*(1/2^1074):=by have S:∀k,d<=k->k0<=w k:=λk u L=>(AF _).trans (v k u L).2 have Q:∀j≤eб,∑k∈i9 d j,w k<=2^960:=λj hj=>(ϻ (Finset.Ico_subset_Ico_right hj) (λk hk _=>(Finset.mem_Ico.1 hk).elim (S k))).trans V have:=(AF _).trans y;have:=(AF _).trans z;have:=ς;rw[PP];dsimp only;split next h=> have u:=u1 (i:=i) А;have h0:=β.mp h;have L:(i+1+1)б=iб+1+1:=by rw[u1 А,u] rw[bH x i А,bH x (i+1) А,u];have⟨I,J⟩:=v iб А А;have⟨g3,g4⟩:=v (iб+1) А А have U:∀g:ℕ->ℝ,∑k∈i9 d (i+1+1)б,g k=∑k∈i9 d iб,g k+g iб+g (iб+1):=λg=>by rw[L,ϕ А,ϕ А] have:=Q _ (by omega:(i+1+1).toNat<=_);rw[U,<-l]at this have:=S iб А А;have:=S (iб+1) А А;have⟨A,B,D⟩:=ek s _ m o (w iб) c А G I E y J (Р) have⟨X,Y,Z⟩:=ek t _ q r (w (iб+1)) c А H g3 F z g4 (Р) exact fe f x e O N d w v V hn (i+1+1) А _ _ (c+1) _ _ _ _ А A X B Y D Z (by rw[U,<-M];ring) (by rw[U,<-l];ring) next h=> split next K=> have h0:=β.mp K;have u:=u1 (i:=i) А;have p:eб=iб+1:=by have:=mt β.mpr h;omega rw[bH x i А];have⟨I,J⟩:=v iб А А;have:=Q (iб+1) А;rw[ϕ А,<-l]at this;have⟨A,B,D⟩:=ek s _ m o (w iб) c А G I E y J (Р) rw[p,ϕ А,ϕ А,<-M,<-l,add_right_comm m,add_right_comm o];exact fO _ t _ q _ r (c+1) c _ А А А А A H B F D z (Р) next K=> have p:eб=iб:=by have:=mt β.mpr K;omega rw[p,<-M,<-l];exact fO s t m q o r c c _ А А А А G H E F y z (by rw[l];exact Q _ А) termination_by eб-iб decreasing_by all_goals omega lemma ff(f:iJ->с)(x:ZB)(e:х)(j:eб<=xв)(h:eб+1<2^32)(d:х)(l:dб<=eб)(w:п->ℝ) (o:∀k,dб<=k->kfv (f x[k]!)/\|rv (f x[k]!)|<=w k) (m:∑k∈i9 dб eб,w k<=2^960) (p:eб<=dб+2^29): fv (PP f x e j h d l 0 0)/\|rv (PP f x e j h d l 0 0)-∑k∈i9 dб eб,rv (f x[k]!)|<= (((eб-dб:ℕ):ℝ)+3)/2*((1/2^53+1/2^73)*∑k∈i9 dб eб,w k)+(((eб-dб:ℕ):ℝ)+1)*(1/2^1074):= fe f x e j h dб w o m p d l 0 0 0 0 0 0 0 А dq.1 dq.1 (by rw[dq.2];simp) (by rw[dq.2];simp) (О) (О) (О) (О) structure RS where ok:ф m:с ri:с d:т A:Д @[inline]def rq(y r:с):ф:=eF r.toBits<1100&&(r*y).toBits-0x3FEFFFFFFFFFFFFF<2 @[inline]def dn(V:с)(w:Д)(k:Д->ф):ф×т:= let B:=(Float.sqrt V).toBits let t:=(1:Д)<<ф)(Ep rn:с)(x:ZB)(lo hi:х)(h:hiб<=xв)(hb:hiб+1<2^32)(hl:loб<=hiб):RS:= let m:=PP dw x hi h hb lo hl 0 0*rn let V:=PP (λw=>let d:=dw w-m;d*d) x hi h hb lo hl 0 0*rn+Ep let t:=dn V Ln k let D:=dw t.2 let ri:=1/D let a:=eF m.toBits let b:=eF D.toBits let mD:=if b<=a then a-b+1 else 0 ⟨t.1&&Ln+mD<=25&&rq D ri,m,ri,t.2,Ln+mD+1047⟩ @[inline]def rR(Ln:Д)(k:Д->ф)(Ep rn:с)(x:ZB)(lo hi:х)(h:hiб<=xв)(hb:hiб+1<2^32)(hl:loб<=hiб):RS:= let V:=PP (λw=>let d:=dw w;d*d) x hi h hb lo hl 0 0*rn+Ep let t:=dn V Ln k let D:=dw t.2 let ri:=1/D ⟨t.1&&rq D ri,0,ri,t.2,0⟩ @[noinline]def sL(n:п)(x:ZB)(r:п)(xw gw bw d:т):т:=ZT ((ZA xw-rowMean n x r)*ZA gw/ZA d+ZA bw) def mL(x:ZB)(b:п):п->Д->Д | 0,u=>u | k+1,u=>let w:=x[b]!;let i:=Core.iW w;mL x (b+1) k (if Core.mW w==0||u< i then u else i) @[inline]def zS(w:т)(lo:Д):п:=let M:=Core.mW w;let h:=Core.iW w-lo;if h<=38 then(M<<п->п->п×п | 0,p,q=>(p,q) | k+1,p,q=>let w:=x[b]! if Core.mW w==0 then sS x lo (b+1) k p q else if ZX w then sS x lo (b+1) k p (q+zS w lo)else sS x lo (b+1) k (p+zS w lo) q @[noinline]def sI(n:п)(x:ZB)(r:п)(xw gw bw d:т):т:= let lo:=mL x (r*n) n 255 let S:=sS x lo (r*n) n 0 0 let X:=if Core.mW xw==0 then 0 else n*zS xw lo let T:=(if ZX xw then-(X:р)else X)-((S.1:р)-S.2) let s1:р:=(loа:р)+idxOf gw-idxOf d let s2:р:=idxOf bw let f:=min s1 s2 let md:=ZW d let P:=T*sv gw*((1<<<(s1-f)л:п):р)+sv bw*(n*md:п)*((1<<<(s2-f)л:п):р) let Q:=n*md let a:=Pй let k1:р:=26+(Qз:р)-(aз:р) let k:=if V8 a k1/YF Q k1<67108864 then k1 else k1-1 let W:=V8 a k let Dd:=YF Q k let q:=W/Dd let e:=f-149-k if 0(mL x b k u)а<=iL x[b+j]!:=by intro k;induction k with | zero=>intro b u;exact⟨AO,λj h=>absurd h (Nat.not_lt_zero _)⟩ | succ k o=> intro b u;rw[mL];generalize m:(if mW x[b]! ==0||u< iW x[b]!then u else iW x[b]!)=v have d:vа<=uа/\(ZW x[b]!≠0->vа<=iL x[b]!):=by rw[<-m];have:=ZS x[b]!;split<;>rename_i h<;>simp only[kU,YK,AG,ν,not_or,not_lt]at h<;>omega have⟨p,e⟩:=o (b+1) v;refine⟨А,λj q l=>?_⟩ rcases j with _|j .have:=d.2 l;simp only[kQ]at*;omega .have:=e j А (by rwa[(А:b+1+j=b+(j+1))]);rw[(А:b+1+j=b+(j+1))]at this;exact this lemma eH(w:iJ)(d:Д)(h:dа<=iL w):zS w d=ZW w*2^(iL w-dа):=by have p:=ZS w;have l:=ZI w;have o:=ZO w;have j:(iW w-d)а=iL w-dа:=by rw[υ _ _ (κ.2 А),p] unfold zS;dsimp only;split<;>rename_i m .have e:iL w-dа<=38:=by have:=κ.1 m;rw[j]at this;simpa using this rw[Η,l,j,θ (А:iL w-dа<64),Ζ] apply θ;calc ZW w*2^(iL w-dа)<2^24*2^38:=Nat.mul_lt_mul_of_lt_of_le o (Μ Г e) В _=2^62:=Г _<2^64:=Г .rw[Ζ,l,j] lemma im(x:ZB)(d:Д):∀k b p q,(∀jdа<=iL x[b+j]!)-> ((sS x d b k p q).1:ℤ)-(sS x d b k p q).2=(p:ℤ)-q+∑j∈ZM k,sv x[b+j]!*2^(iL x[b+j]!-dа):=by intro k;induction k with | zero=>intro b p q _;simp[sS] | succ k o=> intro b p q h;have e:∀jdа<=iL x[b+1+j]!:=λj u=>by rw[(А:b+1+j=b+(j+1))];exact h _ А rw[jC,Τ rfl (λt _=>by rw[(А:b+(t+1)=b+1+t)]),kQ] rw[sS];split<;>rename_i m .rw[o _ _ _ e];have:ZW x[b]! =0:=by simpa[YK]using m simp[sv,this] .have l:=h 0 А (by simpa[YK]using m);rw[kQ]at l split<;>rename_i r<;>rw[o _ _ _ e,eH _ _ l]<;>simp[sv,r]<;>ring lemma dh(w:iJ)(d:ℕ)(h:ZW w=0\/d<=iL w):((ZA w:ℚ))=(sv w*2^(iL w-d):ℤ)*(2:ℚ)^((d:ℤ)-149):=by rw[Y1];rcases h with h|h .have:(sv w:ℚ)=0:=(YN w).2 h;rw[this];simp[show sv w=0 by exact_mod_cast this] .push_cast;rw[Ad,<-AB,<-AI Г];congr 2;push_cast[h];ring lemma fY(n:п)(x:ZB)(r:п):i7 n x r=(((sS x (mL x (r*n) n 255) (r*n) n 0 0).1:ℤ)-(sS x (mL x (r*n) n 255) (r*n) n 0 0).2:ℤ)*(2:ℚ)^(((mL x (r*n) n 255)а:ℤ)-149)/n:=by obtain⟨-,d⟩:=ef x n (r*n) 255;generalize mL x (r*n) n 255=e at d⊢;have l:=im x e n (r*n) 0 0 (λj m h=>d j m h) unfold i7;rw[Yk,Ak];congr 1;rw[l];simp only[kE,sub_zero,Ak];push_cast;rw[Ϲ];refine Τ rfl λt o=>?_ rw[dh _ eа (by by_cases h:ZW x[r*n+t]! =0;exact lA h;exact ll (d t (Κ.1 o) h))];push_cast;ring lemma ik(n:п)(x:ZB)(r j:п)(A z d:iJ)(U:jpush_cast<;>field_simp have K:=Y1 A;have G:=Y1 z;have H:=Y1 d;have L:(sv d:ℚ)=w:=by unfold sv;simp[hd,w] have m:(ZA x[r*n+j]!-i7 n x r)*ZA A/ZA d+ZA z=(P:ℚ)*2^f/(Q*2^149)\/Q=0:=by by_cases p:Q=0;exact ll p;left;have as:(w:ℚ)≠0:=by intro h;apply p;simp only[Q];exact_mod_cast(show n*w=0 by rw[show w=0 by exact_mod_cast h];simp) rw[hX,u,K,G,H,L];have M:(2:ℚ)^(B-f)=2^B/2^f:=by rw[Ap Г] have N:(2:ℚ)^(D-f)=2^D/2^f:=by rw[Ap Г] have I:0<=B-f:=by simp only[f];omega have J:0<=D-f:=by simp only[f];omega simp only[P,Q,T,jF];push_cast;rw[<-AB,<-AB,kd I,kd J,M,N];simp only[B,D,Ap (show(2:ℚ)≠0 by norm_num),AI (show(2:ℚ)≠0 by norm_num)] field_simp split_ifs with E O .simp only[Β,AG,Aa]at E obtain⟨p,ha⟩:=E;rcases m with m|m .rw[m,show P=0 from Bd.1 ha];simp .omega .simp only[Β,AG]at O obtain⟨⟨⟨⟨V,q2⟩,M⟩,N⟩,p⟩:=O;rcases m with m|m;swap;omega rw[m];have F:a≠0:=by intro h;apply E;simp[p,h] obtain⟨Z,hW⟩:=VE a Q p k;have hP:(P:ℚ)≠0:=by intro h;apply F;simp only[a];exact_mod_cast Bd.2 (by exact_mod_cast h) have l:qз=25:=BI (BF.1 ((lf А).2 q2)) ((jA А).2 V);refine Qx _ W false y e _ 0 _ _ ?_ AO one_pos (by simp) Z ?_ V (by rw[l];omega) (by rw[l];omega) ?_ ?_ .intro _;congr 1;apply propext;constructor<;>intro h .by_contra Y;push Not at Y;have:(0:ℚ)<=P*2^f/(Q*2^149):=В linarith .apply div_neg_of_neg_of_pos (mul_neg_of_neg_of_pos (by exact_mod_cast h) В) В .rw[add_zero,BN,AM,AJ (show(0:ℚ)<2^f by positivity),AJ (show(0:ℚ)omega exact θ А .rw[ϱ,ZG,θ А];omega .rfl lemma zQ(w:iJ)(d:Д)(h:ZW w=0\/dа<=iL w):(ZA w)^2=((zS w d:ℕ):ℚ)^2*((2:ℚ)^((dа:ℤ)-149))^2:=by rw[dh _ _ h,mul_pow];congr 1;rcases h with h|h .have:mW w=0:=χ.mp (by rw[ZI,h];rfl) rw[show sv w=0 by exact_mod_cast(YN _).2 h];rw[zS];simp[this] .rw[eH _ _ h];rw[sv];split<;>push_cast<;>ring def qZ(x:ZB)(lo:Д)(b:п):п->п->п | 0,a=>a | k+1,a=>let z:=zS x[b]! lo;qZ x lo (b+1) k (a+z*z) lemma gZ(x:ZB)(d:Д):∀k b a,(qZ x d b k a:ℚ)=a+∑j∈ZM k,((zS x[b+j]! d:ℕ):ℚ)^2:=by intro k;induction k with | zero=>intro b a;simp[qZ] | succ k e=> intro b a;rw[jC,Τ rfl (λt _=>by rw[(А:b+(t+1)=b+1+t)]),kQ,qZ,e];push_cast;ring def V5(A Dn u:п)(eps:т):т:= let E:=ZW eps let ie:=ZZ eps let w0:=min (2*u) (ie+149) let B:=(A<<<(2*u-w0))+((Dn*E)<<<(ie+149-w0)) let s:р:=(350-(w0:р)-((Bз:р)-(Dnз:р)))/2 let c:р:=(w0:р)-298+2*s let num:=V8 B c let den:=YF Dn c let R:=ZK num den if 33554432<=R then Yf num den s else sqrtRational ((A:ℚ)*2^(2*(u:р)-298)/Dn+ZA eps) lemma YW(A e u:п)(d:iJ)(v:0 (2:ℚ)^j=2^k*2^((l:р)-298):=by intro k j h;rw[h,<-ZF,<-ZL ZQ];ring_nf have:=congrArg (λz:ℚ=>(z:ℝ)) (x.trans (by rw[<-w,ZL ZQ,o (2*u-l) (2*(u:р)-298) XI, o (m+149-l) ((m:р)-149) XI,Ζ,Ζ] push_cast;field_simp: _=((A:ℚ)*2^(2*(u:р)-298)/e+E*2^((m:р)-149))*2^(2*s))) push_cast at this⊢;omega .rfl @[noinline]def xD(n:п)(x:ZB)(r:п)(eps:т)(c:ф)(B:Д):ф:= let lo:=mL x (r*n) n 255 let S:=sS x lo (r*n) n 0 0 let s:=if c then((S.1:р)-S.2)йelse 0 V5 (n*n*qZ x lo (r*n) n 0-n*s*s) (n*n*n) loа eps==pq B @[noinline]def sQ(xw gw d:т):т:=ZT (ZA xw*ZA gw/ZA d) @[inline]def eL(n:п)(x:ZB)(r:п)(e:RS)(xw gw bw:т)(gv bv:с):т:= let v:=(dw xw-e.m)*(gv*e.ri)+bv let B:=v.toBits let E:=eF B let c:=NE.mx (NE.mx (E+5) (Core.iW bw+1051)) (Core.iW gw+e.A)-E let t:=(1:Д)<<jт)(hN:loб+Nб<2^32)(i:х)(out:ZB)(ho:loб+Nб<=outв):ZB:= if h:ijiJ)(h:eб+Nб<2^32)(i:х)(d:ZB)(l:eб+Nб<=dв): (QE e N f h i d l)в=dв:=by rw[QE];split .rw[dU];exact ϲ .. .rfl termination_by Nб-iб decreasing_by have:=β.mp ‹_›;have:=N.toNat_lt_size;rw[uS А];omega lemma gL(a:ZB)(i:п)(v:iJ)(h:ifirst|rfl|omega lemma cC(e N:х)(f:(j:х)->jiJ)(F:п->iJ)(m:eб+Nб<2^32) (r:∀j h,f j h=F (eб+jб)) (i:х) (d:ZB) (p:eб+Nб<=dв): (QE e N f m i d p)в=dв/\∀q,(QE e N f m i d p)[q]! =if eб+iб<=q/\q?_⟩ rw[w q,o];rw[lZ];rw[gL,l,r];split_ifs<;>first|rfl|omega|(subst_vars;rfl) .rename_i h have t:¬iбh (β.mpr u) exact⟨Н,λq=>by rw[AP А]⟩ termination_by Nб-iб decreasing_by have:=ς;rw[uS А];omega @[noinline]def fL(n:п)(eps:т)(x g b:ZB)(r:п)(lo N:х)(hN:loб+Nб<2^32)(out:ZB)(ho:loб+Nб<=outв):ZB:= let M:=rowMean n x r let d:=sqrtRational (rowVariance n x r M+ZA eps) QE lo N (λj _=>ZT ((ZA x[r*n+jб]!-M)*ZA g[jб]!/ZA d+ZA b[jб]!)) hN 0 out ho @[noinline]def fR(n:п)(eps:т)(x g:ZB)(r:п)(lo N:х)(hN:loб+Nб<2^32)(out:ZB)(ho:loб+Nб<=outв):ZB:= let d:=sqrtRational (rowVariance n x r 0+ZA eps) QE lo N (λj _=>ZT (ZA x[r*n+jб]!*ZA g[jб]!/ZA d)) hN 0 out ho def RL(rows n:п)(Ln:Д)(Ep rn:с)(eps:т)(x g b:ZB)(gd bd:Ж)(hn:rows*n+1<2^32) (hx:rows*n<=xв) (hg:n<=gв) (hb:n<=bв) (hgd:n<=gdе) (hbd:n<=bdе) (r:п) (out:ZB) (ho:rows*n<=outв):ZB:= if hr:r have:=β.mp hj eL n x r e (x.uget ((r*n)д+j) (by rw[Dense.af (by have:=ς;omega)];omega)) (g.uget j А) (b.uget j А) (gd.uget j А) (bd.uget j А)) (by rw[h2,h3];omega) 0 out (by rw[h2,h3];omega) else fL n eps x g b r (r*n)д nд (by rw[h2,h3];omega) out (by rw[h2,h3];omega)) (by split<;>simp only[dU,fL]<;>exact ho) else out termination_by rows-r def RR(rows n:п)(Ln:Д)(Ep rn:с)(eps:т)(x g:ZB)(gd:Ж)(hn:rows*n+1<2^32) (hx:rows*n<=xв) (hg:n<=gв) (hgd:n<=gdе) (r:п) (out:ZB) (ho:rows*n<=outв):ZB:= if hr:r have:=β.mp hj eR e (x.uget ((r*n)д+j) (by rw[Dense.af (by have:=ς;omega)];omega)) (g.uget j А) (gd.uget j А)) (by rw[h2,h3];omega) 0 out (by rw[h2,h3];omega) else fR n eps x g r (r*n)д nд (by rw[h2,h3];omega) out (by rw[h2,h3];omega)) (by split<;>simp only[dU,fR]<;>exact ho) else out termination_by rows-r @[inline]def lw(n:п):Д:=Core.ao (n+16)ж+1 @[inline]def bF(rows n:п)(eps:т)(x g:ZB):ф:= SN rows n eps x g&&rows*n<=4294967294&&n<=1048576&&rq nж.toInt64.toFloat (1/nж.toInt64.toFloat) lemma dZ(w:iJ)(h:iG w≠255):fv (dw w)/\rv (dw w)=(ZA w:ℝ)*2^149:=by have⟨d,e⟩:=au w h;refine⟨d,?_⟩;rw[e,Y1];push_cast;rw[Ad,<-AB,<-AB,<-AI Г];congr 2;push_cast;ring lemma ee(n:п)(m:n<=2^20):(lw n)а<=21/\(n:ℝ)+17<=2^(lw n)а/\(32:ℝ)<=2^(lw n)а:=by have d:((n+16)ж)а=n+16:=Θ (А:n+16<2^64) have h:(ao (n+16)ж)а=(n+16)з:=by rw[Y7,d] have j:(n+16)з<=20:=BF.1 ((lf А).2 А);have l:4<=(n+16)з:=(jA А).2 А;have e:(lw n)а=(n+16)з+1:=by unfold lw;rw[ξ,h];simp only[iE];omega rw[e];refine⟨А,?_,?_⟩ .have:=Ϝ (n:=n+16);have:(n+17:ℕ)<=2^((n+16)з+1):=А exact_mod_cast this .have:2^5<=2^((n+16)з+1):=Μ Г А exact_mod_cast this lemma ev{e n:п}{d:iJ}{x g:ZB}(h:iU e n d x g=Л):iG d≠255:=by simp only[iU,Β,ZH,A4]at h;have:=h.1.2;unfold kO at this;simpa using this lemma d4(d:iJ)(j:iG d≠255)(l:0rw[Az В]<;>exact Ah Г lemma f7(V T ρ:ℝ)(d:0norm_num have m:iK T<=2^53*U*(1+1/2^30):=Р have:=AE m (by positivity:(0:ℝ)<=((n:ℝ)+32)/2^54) linarith[AX e (iK V) (iK T),AA j d,AA l d,AA p d] lemma vP(n:ℕ)(q h j:с)(A S d l:ℝ)(z:1<=n)(W:n<=2^20)(x:0<=A)(I:A<=2^700)(y:0<=l)(Q:l<=1) (H:fv q) (w:fv h) (G:fv j) (hS:|S-A|<=4/2^53*A+l) (hq:|rv q-S|<=((n:ℝ)+3)/2*((1/2^53+1/2^73)*((1+4/2^53)*A+l))+((n:ℝ)+1)*(1/2^1074)) (D:|rv h-1/n|<=3/2^53/n) (M:|rv j-d|<=d/2^53+1/2^1075) (K:2^149<=d) (L:d<=2^700): fv (q*h+j)/\|rv (q*h+j)-(A/n+d)|<=((n:ℝ)+30)/2^54*(A/n+d):=by obtain⟨t1,t2,t3,t4⟩:=tS;have p:(1:ℝ)<=n:=by exact_mod_cast z have r:(n:ℝ)<=2^20:=by exact_mod_cast W have o:0>>63!=0 then-(((v.toBits&&&0xfffffffffffff)а+2^52:ℕ):ℝ)else((v.toBits&&&0xfffffffffffff)а+2^52:ℕ))|= (((v.toBits&&&0xfffffffffffff)а+2^52:ℕ):ℝ):=by split<;>(try rw[BM])<;>exact AS В rw[this] calc (2:ℝ)^(((eF v.toBits)а:р)-1023)=2^52*2^(((eF v.toBits)а:р)-1075):=by rw[<-AB,<-AI Г];congr 1;push_cast;ring _<=_:=by gcongr;push_cast;linarith[show(0:ℝ)<=((v.toBits&&&0xfffffffffffff)а:ℝ) by positivity] lemma bU(v:с)(d:fv v):|rv v|<2^53*(2:ℝ)^(((eF v.toBits)а:р)-1075):=by have:=bm v d;rwa[show(2:ℝ)^(((eF v.toBits)а:р)-1022)=2^53*2^(((eF v.toBits)а:р)-1075) by rw[<-AB,<-AI Г];congr 1;push_cast;ring]at this lemma d0(V:с)(p:Д)(k:Д->ф)(v:fv V)(o:0by rw[h]at l;simp at l have e:0ф)(v:ℚ)(ρ:ℝ)(l:n<=2^20)(w:fv V)(m:0pq B=iY v) (d:(dn V (lw n) k).1=true):(dn V (lw n) k).2=iY v:=by have⟨L,H,I⟩:=ee n l;have z:(0:ℝ)<(v:ℝ)*2^298:=mul_pos (by exact_mod_cast m) В have F:(n:ℝ)<=2^20:=by exact_mod_cast l have G:ρ<=1/2:=p.trans (by rw[AR В В];nlinarith) have e:0с)(x:ZB)(m l:х)(h:lб<=xв)(r:lб+1<2^32)(v:mб<=lб) (n e:ℕ) (p:mб=e) (o:lб=e+n) (A:n<=2^20) (d:ℕ->ℝ) (t:∀jℝ,∑k∈i9 mб lб,g k=∑j∈iD n,g (e+j):=λg=>by rw[kh,p,o,ϭ] have z:∀a:ℝ,∑j∈iD n,(a*d j^2+1/2^1000)=a*∑j∈iD n,d j^2+n/2^1000:=λa=>by rw[ϰ,<-jJ];simp;ring have D:∑j∈iD n,d j^2<=n*2^600:=by simpa using Finset.sum_le_card_nsmul _ _ _ λj u=>(t j (Κ.1 u)).2.2 have w:(n:ℝ)<=2^20:=by exact_mod_cast A have:(2:ℝ)^22*2^600<=2^960:=by rw[<-AK];exact AC Г Г have:=AA w (by positivity:(0:ℝ)<=2^600) have:(1:ℝ)<=2^600:=Ah Г;have:(n:ℝ)/2^1000<=n:=div_le_self В (Ah Г) obtain⟨B,y⟩:=ff f x l h r m v (λk=>(1+4/2^53)*d (k-e)^2+1/2^1000) (λk E F=>by obtain⟨j,rfl⟩:∃j,k=e+j:=⟨k-e,А⟩ obtain⟨a,b,-⟩:=t j А;simp only[ϭ];refine⟨a,?_⟩;have:=AD (rv (f x[e+j]!)) (d j^2);rw[AS (Aq (d j))]at this;linarith) (by simp only[q,ϭ,z];generalize (2:ℝ)^600=T at*;generalize (2:ℝ)^960=U at*;linarith) А rw[q,q]at y;simp only[o,p,ϭ,z]at y;refine⟨B,y,?_⟩;rw[<-ϙ,<-z];exact(ϣ _ _).trans (ϋ λj u=>(t j (Κ.1 u)).2.1) lemma dB(w:iJ)(d:iG w≠255):|rv (dw w)|<=2^278:=by rw[(au w d).2];exact(NE.wB w).trans (AC Г (by have:=bL w;omega)) lemma tR(w:iJ)(j:iG w≠255):fv (dw w*dw w)/\|rv (dw w*dw w)-rv (dw w)^2|<=4/2^53*rv (dw w)^2+1/2^1000/\rv (dw w)^2<=2^600:=by have h:=(au _ j).1;have d:=dB _ j have e:rv (dw w)^2<=2^556:=by have:=sq_le_sq' (AZ.1 d).1 (AZ.1 d).2;rw[<-BK]at this;exact this have l:|rv (dw w)*rv (dw w)|<=(2:ℝ)^(971:р):=by rw[BX,<-sq];exact e.trans (by rw[show(971:ℤ)=((971:ℕ):ℤ)fromН,AB];exact AC Г Г) have⟨m,o⟩:=NF.fM _ _ h h l;refine⟨m,?_,e.trans (AC Г Г)⟩;rw[BX,<-sq]at o;have:(1:ℝ)/2^1075<=1/2^1000:=AQ В (AC Г Г);have:rv (dw w)^2/2^53<=4/2^53*rv (dw w)^2:=by have:=Aq (rv (dw w));rw[A2 В];nlinarith linarith lemma sA(n:ℕ)(l:n<=2^20)(d:ℕ->ℝ)(h:∀jh j (Κ.1 e) _=n*2^600:=О _<=2^20*2^600:=by gcongr;exact_mod_cast l _<=2^700:=by rw[<-AK];exact AC Г Г lemma fw(d:iJ)(h:iG d≠255):(ZA d:ℝ)*2^298<=2^700:=by have:=dB d h;rw[(dZ d h).2]at this;have e:(ZA d:ℝ)*2^298=(ZA d:ℝ)*2^149*2^149:=by rw[Ad,<-AK] rw[e];calc(ZA d:ℝ)*2^149*2^149<=2^278*2^149:=by gcongr;exact Ae (A1 _) this _<=2^700:=by rw[<-AK];exact AC Г Г lemma nJ(n:ℕ)(e:n<=2^20):(n:ℝ)/2^1000<=1:=by have d:(n:ℝ)<=2^20:=by exact_mod_cast e rw[Az В];exact d.trans (AC Г Г) lemma g9(n:п)(e:iJ)(x:ZB)(r:п)(u l:х)(h:lб<=xв)(y:lб+1<2^32)(A:uб<=lб) (B:uб=r*n) (z:lб=r*n+n) (t:1<=n) (q:n<=2^20) (m:∀jlet d:=dw w;d*d) x l h y u A 0 0*(1/nж.toInt64.toFloat)+dw e*NR.pt 149)/\ |rv (PP (λw=>let d:=dw w;d*d) x l h y u A 0 0*(1/nж.toInt64.toFloat)+dw e*NR.pt 149)- ((iS n x r 0+ZA e:ℚ):ℝ)*2^298|<=((n:ℝ)+30)/2^54*(((iS n x r 0+ZA e:ℚ):ℝ)*2^298):=by have⟨K,L⟩:=eu n t q D;have⟨E,F,G⟩:=d4 e o v;have⟨H,I,J⟩:=pS (λw=>let d:=dw w;d*d) x u l h y A n (r*n) B z q (λj=>rv (dw x[r*n+j]!)) (λj p=>tR _ (m j p)) rw[show((iS n x r 0+ZA e:ℚ):ℝ)*2^298=(∑j∈iD n,rv (dw x[r*n+j]!)^2)/n+(ZA e:ℝ)*2^298 by rw[iS];rw[Yk];push_cast;rw[add_mul,AU,Ak,Ϲ];congr 2;refine Τ rfl λj p=>?_ rw[sub_zero,(dZ _ (m j (Κ.1 p))).2,mul_pow,show(2:ℝ)^298=(2^149)^2 by rw[<-BK]]] exact vP n _ _ _ _ _ _ _ t q (Ϩ λj _=>Aq _) (sA n q _ λj p=>(tR _ (m j p)).2.2) В (nJ n q) H K E J I L F G (fw e o) lemma fn(V:с)(d:Д)(k:Д->ф)(r:fv V)(l:0(zQ _ _ (by by_cases h:ZW x[r*n+j]! =0;exact lA h;exact ll (o j (Κ.1 z) h))).symm] unfold iS;rw[Yk,Ak];congr 1;simp only[sub_sq,ϰ,ϙ,<-Ϲ,<-jJ,jU,ϴ,BC];cases c<;>simp only[μ,AN,AV,<-A,p,kb,ϊ,sq_abs,kE]<;>ring have e:((2:ℚ)^((dа:ℤ)-149))^2=2^(2*(dа:ℤ)-298):=by rw[<-AB,<-zpow_mul];congr 1;push_cast;ring have u:(0:ℚ)<2^(2*(dа:ℤ)-298):=В;rw[w,e]at m⊢;generalize (2:ℚ)^(2*(dа:ℤ)-298)=K at u m⊢;generalize qZ x d (r*n) n 0=Q at m⊢;generalize (if c then((S.1:ℤ)-S.2)йelse 0)=s at m⊢;have v:((Q:ℚ)*K-n*(s:ℚ)^2*K/n^2)/n=(n*n*Q-n*s*s)*K/(n*n*n):=by field_simp rw[v]at m⊢;have:(0:ℚ)<=n*n*Q-n*s*s:=by by_contra t;push_neg at t;exact absurd m (not_le.2 (div_neg_of_neg_of_pos (mul_neg_of_neg_of_pos t u) В)) rw[kN (by exact_mod_cast sub_nonneg.1 this)];push_cast;ring lemma g7(m:Д)(k:Д->ф)(l q:с)(x:ZB)(j e:х)(h:eб<=xв)(o:eб+1<2^32)(p:jб<=eб): rR m k l q x j e h o p=⟨(dn (PP (λw=>let d:=dw w;d*d) x e h o j p 0 0*q+l) m k).1&& rq (dw (dn (PP (λw=>let d:=dw w;d*d) x e h o j p 0 0*q+l) m k).2) (1/dw (dn (PP (λw=>let d:=dw w;d*d) x e h o j p 0 0*q+l) m k).2), 0,1/dw (dn (PP (λw=>let d:=dw w;d*d) x e h o j p 0 0*q+l) m k).2,(dn (PP (λw=>let d:=dw w;d*d) x e h o j p 0 0*q+l) m k).2,0⟩:=Н lemma g5(n:ℕ)(V:с)(k:Д->ф)(v:ℚ)(d:n<=2^20)(h:fv V)(l:0pq B=iY v) (e:((dn V (lw n) k).1&&rq (dw (dn V (lw n) k).2) (1/dw (dn V (lw n) k).2))=Л): (dn V (lw n) k).2=iY v/\iG (dn V (lw n) k).2≠255/\jh (dn V (lw n) k).2=false/\1<=rv (dw (dn V (lw n) k).2)/\ fv (1/dw (dn V (lw n) k).2)/\|rv (1/dw (dn V (lw n) k).2)-1/rv (dw (dn V (lw n) k).2)|<=3/2^53/rv (dw (dn V (lw n) k).2):=by obtain⟨q,-,-⟩:=ee n d;have m:(0:ℝ)<(v:ℝ)*2^298:=mul_pos (by exact_mod_cast l) В rw[Β]at e;have p:0rename_i h .rw[AS h];field_simp .rw[abs_of_neg (by linarith)];field_simp;try ring have H:|G|/D<=2^278:=(div_le_self (AF _) y).trans z rw[e,AM,AM,AS (A7 (AF _) m.le)];have:|(if 0<=G then(1:ℝ)else-1)|=1:=by split<;>simp rw[this,mul_one] calc (|s-j|)*(|G|/D)<=(|j|/2^53+1/2^1075)*(|G|/D):=AA x (A7 (AF _) m.le) _=|j*G/D|/2^53+1/2^1075*(|G|/D):=by rw[BN,AM,AJ m];ring _<=_:=by gcongr have I:(1:ℝ)/2^1075*2^278<=1/2^797:=by rw[AU,Aj,AR В В,Aj,<-AK] have W:(1:ℝ)/2^1075<=1/2^797:=AQ В (AC Г Г) have X:(1:ℝ)/2^797*16<=1/2^700:=by rw[AU,Aj,AR В В,Aj,show(16:ℝ)=2^4 by norm_num,<-AK] exact AC Г Г have Y:(1:ℝ)/2^700*2=1/2^699:=by rw[AU,Aj,div_eq_div_iff В В,Aj,<-A3] have Z:(0:ℝ)<=1/2^797:=В;have tτ:(0:ℝ)<=1/2^1075:=В;have J:=AX v (q+l) (j*G/D+l) have E:|q+l-(j*G/D+l)|<=|q-s*G/D|+|s*G/D-j*G/D|:=by rw[show q+l-(j*G/D+l)=(q-s*G/D)+(s*G/D-j*G/D) by ring];exact AT _ _ have L:|q+l|<=|v|+|v-(q+l)|:=by have:=AD (q+l) v;rw[Au]at this;linarith have M:|q|<=|q+l|+|l|:=by have:=AD q (q+l);rw[show q-(q+l)=-l by ring,BM]at this;linarith have N:|j*G/D|<=|q|+|q-s*G/D|+|s*G/D-j*G/D|:=by have:=AD (j*G/D) q have:|j*G/D-q|<=|q-s*G/D|+|s*G/D-j*G/D|:=by rw[Au,show q-j*G/D=(q-s*G/D)+(s*G/D-j*G/D) by ring];exact AT _ _ linarith clear r A z p o B x;generalize (2:ℝ)^278=P at F I;generalize (1:ℝ)/2^1075=τ at*;generalize (1:ℝ)/2^797=σ at*;generalize (1:ℝ)/2^700=K at*;generalize (1:ℝ)/2^699=O at* have S:=AF v;have U:=AF l;generalize |v-(j*G/D+l)|=w at*;generalize |q+l-(j*G/D+l)|=w2 at*;generalize |v-(q+l)|=a at* generalize |q-s*G/D|=b at*;generalize |s*G/D-j*G/D|=c at*;generalize |q+l|=d at*;generalize |q|=e at* generalize |j*G/D|=f at*;generalize |v|=g at*;generalize |l|=h at* linarith lemma zW(w:iJ)(h:(w&&&0x7FFFFFFF==0)=Л):ZA w=0:=by have d:(w&&&0x7FFFFFFF)г=0:=by rw[Aa]at h;rw[h];rfl rw[Ρ]at d;simp only[iO]at d;rw[show(2147483647:ℕ)=2^31-1 by norm_num,γ]at d have e:=fx w;have j:=fz w have l:ZW w=0:=by rw[jd];have:(iG w)г=0:=by rw[e];omega have:iG w=0:=Ι.mp (by rw[this];rfl) rw[if_pos this,j];omega rw[Y1,show(sv w:ℚ)=0 from(YN w).2 l,zero_mul] lemma gG(l j d:iJ)(m:с)(b:ф)(D:iG l≠255)(B:iG j≠255)(y:iG d≠255)(p:1<=rv (dw d)) (u:fv m) (q:|rv m-1/rv (dw d)|<=3/2^53/rv (dw d)):eR ⟨b,0,m,d,0⟩ l j (dw j)=ZT (ZA l*ZA j/ZA d):=by unfold eR;dsimp only;split .rename_i x simp only[Β,AG]at x;obtain⟨N,O⟩:=dZ l D;obtain⟨J,L,M⟩:=gp j m B u (er _ _ p q);have z:=dB l D;obtain⟨F,I⟩:=NF.fM _ _ N J (NE.z9 _ _ (pB _ _ 278 280 z M) Г);obtain⟨r,G⟩:=te _ x.1 have A:16<(dw l*(dw j*m)).toBitsа%2^27/\(dw l*(dw j*m)).toBitsа%2^27+16<2^27:=by have:=ν.mp x.2;rw[Λ,Α]at this;simp only[iE]at this;rw[show(134217727:ℕ)=2^27-1 by norm_num,γ]at this have:=ϩ (dw l*(dw j*m)).toBitsа (show 0<2^27 by norm_num);omega apply eC _ F 4 _ r G (by simpa using A.1) (by simpa using A.2) have o:0by rw[h]at t;rw[t]at o;simp at o rw[show((ZA l*ZA j/ZA d:ℚ):ℝ)*2^149=rv (dw l)*rv (dw j)/rv (dw d) by rw[O,(dZ j B).2,t];push_cast;field_simp] have e:=fy _ _ _ _ _ _ p q L I (z.trans (AC Г Г));have w:=bU _ F;generalize dw l*(dw j*m)=v at e w r⊢;generalize (eF v.toBits)а=E at r w⊢;have:(1:ℝ)/2^700<=2^((E:р)-1075):=by rw[one_div,<-AB,<-zpow_neg];exact zpow_le_zpow_right₀ Г А generalize (2:ℝ)^((E:р)-1075)=U at*;generalize (1:ℝ)/2^700=K at* have:=AF (rv v);norm_num at e w⊢;nlinarith .split .rename_i _ H;rw[zW l H,zero_mul,zero_div];rfl .rfl lemma gf(h n:п)(e:iJ)(x g:ZB)(A:iU h n e x g=Л) (I:h*n+1<2^32) (m:n<=2^20) (y:rq nж.toInt64.toFloat (1/nж.toInt64.toFloat)=Л) (r:п) (J:rq _ А have⟨D,z⟩:=g9 n e x r _ _ h1 h2 h3 L M p m t u o y;have K:0< iS n x r 0+ZA e:=by have:=em n x r 0;linarith rw[g7]at l⊢;dsimp only at l⊢;generalize PP (λw=>let d:=dw w;d*d) x ((r*n)д+nд) h1 h2 (r*n)д h3 0 0*(1/nж.toInt64.toFloat)+dw e*NR.pt 149=V at D z l⊢ have⟨c,E,N,F,G,H⟩:=g5 n V _ _ m D K (by push_cast at z⊢;exact z) (ga n x r e М p o) l generalize (dn V (lw n) (xD n x r e М)).2=d at c E N F G H⊢;rw[<-c];exact gG _ _ d _ _ (q _ А) (v j B) E F G H lemma cf(b:Д):(eF b)а<=2047:=by rw[eF];rw[Α];exact Nat.and_le_right.trans (О) lemma f5(a b:ℝ)(j:|a|<=2^278)(l:|b|<=2^279):|a-b|<=2^280:=by have h:=AX a 0 b;rw[sub_zero,zero_sub,BM]at h;have d:(2:ℝ)^279=2*2^278:=by rw[<-A3] have e:(2:ℝ)^280=2*2^279:=by rw[<-A3] rw[d]at l;rw[e,d];clear d e;generalize (2:ℝ)^278=T at*;have:0<=T:=Ae (AF _) j;linarith lemma cS(n:ℕ)(m:1<=n)(d:ℕ->ℝ):∑j∈iD n,|d j|<=n*iK ((∑j∈iD n,d j^2)/n):=by have l:(0:ℝ)|d j|) simp only[ϴ,sq_abs]at h;have e:(n:ℝ)*∑j∈iD n,d j^2=(n:ℝ)^2*((∑j∈iD n,d j^2)/n):=by field_simp calc _<=iK ((n:ℝ)*∑j∈iD n,d j^2):=ld h _=_:=by rw[e,lx (Aq _),lM l.le] lemma mR(n:ℕ)(p:1<=n)(w:n<=2^20)(S h W d m:ℝ)(r:|h|<=W) (y:|S-h|<=((n:ℝ)+3)/2*((1/2^53+1/2^73)*W)+((n:ℝ)+1)*(1/2^1074)) (q:|d-1/n|<=3/2^53/n) (v:|m-S*d|<=|S*d|/2^53+1/2^1075): |m-h/n|<=((n:ℝ)+13)/2^54*(W/n)+1/2^1040:=by have o:(1:ℝ)<=n:=by exact_mod_cast p have j:(n:ℝ)<=2^20:=by exact_mod_cast w have l:(0:ℝ)norm_num have:(1:ℝ)/2^1074*2^25<=1/2^1040:=by rw[AU,Aj,AR В В,Aj,<-AK];exact AC Г Г refine Bf (e.trans ?_) l;rw[show n*(((n:ℝ)+13)/2^54*(W/n)+1/2^1040)=((n:ℝ)+13)/2^54*W+1/2^1040*n by field_simp] linarith lemma mE(n:ℕ)(P Q D R d δ W:ℝ)(w:(n:ℝ)+17<=P)(l:P<=2^21)(x:1<=Q)(v:1<=D) (B:δ<=((n:ℝ)+13)/2^54*(W/n)+1/2^1040) (z:W/n<=R+|d|) (y:R<=D*(1+1/2^22)) (A:|d|<=Q*D):δ<=P*Q/2^53*D:=by have h:W/n<=D*(1+1/2^22+Q):=Р have m:(0:ℝ)<=n:=kW n;have r:((n:ℝ)+13)/2^54*(W/n)<=((n:ℝ)+13)/2^54*(D*(1+1/2^22+Q)):=AE h В have j:((n:ℝ)+13)*(1+1/2^22+Q)<=2*P*Q-15/2:=by have o:((n:ℝ)+13)*(1+1/2^22+Q)<=(P-4)*(1+1/2^22+Q):=AA (Р) (Р) have p:0<=P*(Q-1):=AW (Р) (Р) nlinarith have t:((n:ℝ)+13)*(1+1/2^22+Q)*D<=(2*P*Q-15/2)*D:=AA j (Р) have u:(1:ℝ)/2^1040<=15/2*D/2^54:=by have a:(1:ℝ)/2^1040<=1/2^54:=AQ В (AC Г Г);have b:(1:ℝ)/2^54<=15/2*D/2^54:=by rw[BO В];linarith linarith have e:((n:ℝ)+13)/2^54*(D*(1+1/2^22+Q))=((n:ℝ)+13)*(1+1/2^22+Q)*D/2^54:=П have q:(2*P*Q-15/2)*D/2^54=P*Q/2^53*D-15/2*D/2^54:=П have:((n:ℝ)+13)*(1+1/2^22+Q)*D/2^54<=(2*P*Q-15/2)*D/2^54:=by gcongr linarith lemma gz(n:ℕ)(w:n<=2^20)(V d h D:ℝ)(e:2^149<=d)(v:|V-d|<=((n:ℝ)+30)/2^54*d)(l:0nlinarith[ύ V,ύ d] lemma bI(n:ℕ)(t:n<=2^20)(V T δ D:ℝ)(y:0ℝ)(a:ℝ):∑j∈iD n,(X j-a)^2= ∑j∈iD n,(X j-(∑k∈iD n,X k)/n)^2+n*((∑k∈iD n,X k)/n-a)^2:=by have l:(n:ℝ)≠0:=Nat.cast_ne_zero.2 А;generalize h:(∑k∈iD n,X k)/n=M have d:∑j∈iD n,(X j-M)=0:=by rw[ϙ,jU,ϴ,BC,<-h];field_simp;ring have e:∀j,(X j-a)^2=(X j-M)^2+2*(M-a)*(X j-M)+(M-a)^2:=λj=>П simp only[e,ϰ,<-jJ,d,jU,ϴ,BC];ring lemma ir(d s p τ:ℝ)(e:0<=τ)(q:τ+2^58*τ^2<=1/2^1000)(o:|s-d|<=|d|/2^53+τ)(m:|p-s^2|<=s^2/2^53+τ): |p-d^2|<=4/2^53*d^2+1/2^1000:=by have h:=AT (2*d*(s-d)) ((s-d)^2);rw[show 2*d*(s-d)+(s-d)^2=s^2-d^2 by ring,AM,AM,BL,BW]at h have l:=AF (s-d);have j:=AF d;have r:(|s-d|)^2<=2*(|d|/2^53)^2+2*τ^2:=by nlinarith[Aq (|d|/2^53-τ)] have t:2*(|d|)*(|s-d|)<=2*(|d|)*(|d|/2^53+τ):=by nlinarith have u:2*(|d|)*τ<=2^57*τ^2+(|d|)^2/2^57:=by nlinarith[Aq (2^57*τ-|d|)] have v:s^2<=d^2+|s^2-d^2|:=by have:=A1 (s^2-d^2);linarith have w:=AX p (s^2) (d^2);have x:=sq_abs d;generalize (1:ℝ)/2^1000=ζ at* nlinarith lemma tL(w:iJ)(m:с)(h:iG w≠255)(r:fv m)(t:|rv m|<=2^279): fv ((dw w-m)*(dw w-m))/\|rv ((dw w-m)*(dw w-m))-(rv (dw w)-rv m)^2|<=4/2^53*(rv (dw w)-rv m)^2+1/2^1000/\(rv (dw w)-rv m)^2<=2^600:=by have q:=(au _ h).1;have d:=f5 _ _ (dB _ h) t;have⟨o,p⟩:=NF.fS _ _ q r (NE.z9 _ 280 d Г);have j:|rv (dw w-m)|<=2^281:=rB _ _ 280 d p have e:=pB _ _ 281 281 j j;have⟨u,l⟩:=NF.fM _ _ o o (NE.z9 _ _ e Г);rw[BX,<-sq]at l;refine⟨u,ir _ _ _ (1/2^1075) В ?_ p l,?_⟩ .have:(2:ℝ)^58*(1/2^1075)<=1:=by rw[mul_one_div,Az В];exact AC Г Г have:(1:ℝ)/2^1075<=1/2^1000/2:=by rw[div_div,<-Ay];gcongr<;>norm_num have:(0:ℝ)<=1/2^1075:=В;generalize (1:ℝ)/2^1075=τ at*;nlinarith .have:=sq_le_sq' (AZ.1 d).1 (AZ.1 d).2;rw[<-BK]at this exact this.trans (AC Г Г) lemma gR(n:п)(x:ZB)(r o:х)(h:oб<=xв)(v:oб+1<2^32)(z:rб<=oб) (d:ℕ) (A:rб=d) (y:oб=d+n) (t:1<=n) (J:n<=2^20) (E:∀jℝ,∑k∈i9 rб oб,g k=∑j∈iD n,g (d+j):=by intro g;rw[kh,A,y,(А:d+n-d=n)] have m:∑j∈iD n,|rv (dw x[d+j]!)|<=n*2^278:=by calc _<=∑j∈iD n,(2:ℝ)^278:=ϋ λj Z=>dB _ (E j (Κ.1 Z)) _=n*2^278:=О have G:∑j∈iD n,|rv (dw x[d+j]!)|<=2^298:=m.trans (by calc (n:ℝ)*2^278<=2^20*2^278:=by gcongr _=2^298:=by rw[<-AK]) have⟨U,u⟩:=ff dw x o h v r z (λk=>|rv (dw x[k]!)|) (λk Q S=>by obtain⟨j,rfl⟩:∃j,k=d+j:=⟨k-d,А⟩ exact⟨(au _ (E j А)).1,AO⟩) (by rw[H];exact G.trans (AC Г Г)) А rw[H,H,y,A,(А:d+n-d=n)]at u have l:=ϣ (λj=>rv (dw x[d+j]!)) (iD n) generalize ∑j∈iD n,|rv (dw x[d+j]!)|=W at G m u l⊢ generalize ∑j∈iD n,rv (dw x[d+j]!)=F at u l⊢;generalize PP dw x o h v r z 0 0=q at U u⊢;have M:0<=W:=Ae (AF _) l;have D:=er _ _ K V have O:|rv q|<=2^299:=by have X:((n:ℝ)+3)/2*((1/2^53+1/2^73)*W)<=W/2:=by have:((n:ℝ)+3)/2*(1/2^53+1/2^73)<=1/2:=by rw[AU,AR Г Г];nlinarith nlinarith have Y:((n:ℝ)+1)*(1/2^1074)<=1:=by have:(1:ℝ)/2^1074<=1/2^21:=AQ В (AC Г Г);have:((n:ℝ)+1)*(1/2^1074)<=(2^20+1)*(1/2^21):=by gcongr linarith have:=AD (rv q) F;clear m;have e:(2:ℝ)^299=2*2^298:=by rw[<-A3] have I:(2:ℝ)<=2^298:=le_self_pow₀ Г Г;rw[e];clear e;generalize (2:ℝ)^298=T at*;generalize ((n:ℝ)+3)/2*((1/2^53+1/2^73)*W)=c at* generalize ((n:ℝ)+1)*(1/2^1074)=j at*;linarith only[this,u,X,Y,l,G,I] have B:=pB _ _ 299 1 O D;have⟨m1,m2⟩:=NF.fM _ _ U r1 (NE.z9 _ _ B Г);have N:=mR n t J (rv q) F W _ _ l u V m2;refine⟨m1,N,?_⟩ have Q:W/n<=2^278:=by rw[A2 p];calc W<=n*2^278:=m _=_:=mul_comm _ _ have S:|F/n|<=W/n:=by rw[BN,AJ p];exact BQ l p.le have k3:((n:ℝ)+13)/2^54*(W/n)<=W/n/2:=by have:((n:ℝ)+13)/2^54<=1/2:=by rw[AR В В];nlinarith have:=AA this (A7 M p.le);linarith have k4:(1:ℝ)/2^1040<=1:=by rw[Az В];exact Ah Г have:=AD (rv (q*(1/nж.toInt64.toFloat))) (F/n);have e:(2:ℝ)^279=2*2^278:=by rw[<-A3] have I:(2:ℝ)<=2^278:=le_self_pow₀ Г Г;clear G O B m;rw[e];clear e;generalize (2:ℝ)^278=T at*;generalize W/n=w at*;generalize (1:ℝ)/2^1040=ζ at* generalize ((n:ℝ)+13)/2^54*w=c at*;linarith only[this,N,Q,S,k3,k4,I] lemma g8(n:п)(l:iJ)(x:ZB)(u o:х)(h:oб<=xв)(z:oб+1<2^32)(D:uб<=oб) (e:ℕ) (E:uб=e) (A:oб=e+n) (r:1<=n) (q:n<=2^20) (t:∀jlet d:=dw w-m;d*d) x o h z u D 0 0*(1/nж.toInt64.toFloat)+dw l*NR.pt 149)/\ |rv (PP (λw=>let d:=dw w-m;d*d) x o h z u D 0 0*(1/nж.toInt64.toFloat)+dw l*NR.pt 149)- ((∑j∈iD n,(rv (dw x[e+j]!)-rv m)^2)/n+(ZA l:ℝ)*2^298)|<= ((n:ℝ)+30)/2^54*((∑j∈iD n,(rv (dw x[e+j]!)-rv m)^2)/n+(ZA l:ℝ)*2^298):=by have⟨O,Q⟩:=eu n r q F;have⟨I,J,K⟩:=d4 l p y have⟨L,M,N⟩:=pS (λw=>let d:=dw w-m;d*d) x u o h z D n e E A q (λj=>rv (dw x[e+j]!)-rv m) (λj B=>tL _ m (t j B) G H) have v:0<=∑j∈iD n,(rv (dw x[e+j]!)-rv m)^2:=Ϩ λj _=>Aq _ exact vP n _ _ _ _ _ ((ZA l:ℝ)*2^298) _ r q v (sA n q _ λj B=>(tL _ m (t j B) G H).2.2) В (nJ n q) L O I N M Q J K (fw l p) lemma gP(m D:с)(p:Д)(v:fv m)(q:fv D)(y:1<=rv D)(h:p=if eF D.toBits<=eF m.toBits then eF m.toBits-eF D.toBits+1 else 0): |rv m|<=2^pа*rv D/\pа<=2048:=by subst h;have t:=bm m v;have z:=cf m.toBits;have x:=cf D.toBits have o:¬eF D.toBits=0:=by intro w;have k:=bm D q;rw[w]at k;rw[ϓ,kE,zero_sub]at k;have:(2:ℝ)^(-1022:ℤ)<=1:=Ai Г Г;have:=A1 (rv D);linarith have r:=di D q o;rw[AJ (Р)]at r split .rename_i d have j:=κ.1 d have e:(eF m.toBits-eF D.toBits+1)а=(eF m.toBits)а-(eF D.toBits)а+1:=by rw[ξ,υ _ _ d];simp only[iE];omega rw[e];refine⟨?_,А⟩ calc |rv m|<=(2:ℝ)^(((eF m.toBits)а:р)-1022):=t.le _=2^((eF m.toBits)а-(eF D.toBits)а+1)*2^(((eF D.toBits)а:р)-1023):=by rw[<-AB,<-AI Г];congr 1;rw[Nat.cast_add,kN j];push_cast;ring _<=_:=by gcongr .rename_i l have u:(eF m.toBits)а<(eF D.toBits)а:=by have:=UInt64.le_iff_toNat_le.not.1 l;omega refine⟨?_,О⟩ rw[ϓ,pow_zero,Aj] calc |rv m|<=(2:ℝ)^(((eF m.toBits)а:р)-1022):=t.le _<=(2:ℝ)^(((eF D.toBits)а:р)-1023):=zpow_le_zpow_right₀ Г А _<=_:=r lemma g6(e:Д)(k:Д->ф)(t r:с)(x:ZB)(l j:х)(h:jб<=xв)(o:jб+1<2^32)(p:lб<=jб): ∃m V q,m=PP dw x j h o l p 0 0*r/\V=PP (λw=>let d:=dw w-m;d*d) x j h o l p 0 0*r+t/\ q=(if eF (dw (dn V e k).2).toBits<=eF m.toBits then eF m.toBits-eF (dw (dn V e k).2).toBits+1 else 0)/\ rL e k t r x l j h o p=⟨(dn V e k).1&&e+q<=25&&rq (dw (dn V e k).2) (1/dw (dn V e k).2),m,1/dw (dn V e k).2,(dn V e k).2,e+q+1047⟩:= ⟨_,_,_,Н,Н,Н,Н⟩ lemma fJ(n:п)(x:ZB)(r:п)(d:∀j?_ rw[(dZ _ (d j (Κ.1 e))).2] lemma iv(n:п)(x:ZB)(r:п)(d:iJ)(e:∀j?_ rw[(dZ _ (e j (Κ.1 h))).2,show(2:ℝ)^298=(2^149)^2 by rw[<-BK]] ring lemma cE(E d e A:Д)(k:ℕ)(r:Eа<=2047)(p:dа<=254)(q:eа<=254)(o:Aа=k+1047)(t:k<=25): (NE.mx (NE.mx (E+5) (d+1051)) (e+A)-E)а=lX (lX (Eа+5) (dа+1051)) (eа+k+1047)-Eа:=by have j:(E+5)а=Eа+5:=by rw[ξ];simp only[iE];omega have l:(d+1051)а=dа+1051:=by rw[ξ];simp only[iE];omega have m:(e+A)а=eа+k+1047:=by rw[ξ,o];omega have h:(NE.mx (NE.mx (E+5) (d+1051)) (e+A))а=lX (lX (Eа+5) (dа+1051)) (eа+k+1047):=by rw[NE.cO,NE.cO,j,l,m] rw[υ _ _ (κ.2 (by rw[h];omega)),h] lemma gF(n:п)(x:ZB)(r j:п)(hj:jby rw[h]at H;rw[H]at p;simp at p rw[show(rv (dw z)-rv m)*rv (dw l)/rv (dw d)+rv (dw o)-(((ZA z-i7 n x r)*ZA l/ZA d+ZA o:ℚ):ℝ)*2^149= (((i7 n x r:ℚ):ℝ)*2^149-rv m)*(rv (dw l)/rv (dw d)) by rw[x2,(dZ l F).2,H,b2];push_cast;field_simp;ring, AM,Au,BN,AJ p] calc _<=2^k/2^53*rv (dw d)*(|rv (dw l)|/rv (dw d)):=AA hδ (A7 (AF _) p.le) _=_:=by have:=p.ne';field_simp .exact ik n x r j l o d hj L lemma vp(n:ℕ)(d:n<=2^20)(V A E:ℝ)(j:0<=A)(l:2^149<=E)(h:|V-(A+E)|<=((n:ℝ)+30)/2^54*(A+E)):0ℝ)(m d V r D P Q:ℝ)(M:2^149<=d) (t:|V-((∑j∈iD n,(X j-m)^2)/n+d)|<=((n:ℝ)+30)/2^54*((∑j∈iD n,(X j-m)^2)/n+d)) (x:0X j-m);beta_reduce at y have:∑j∈iD n,|X j|<=∑j∈iD n,|X j-m|+n*|m|:=by simpa[ϰ]using ϋ λj (_:j∈iD n)=>AT (X j-m) m have K:=AE (Real.sqrt_le_sqrt (by linarith:(∑j∈BJ n,(X j-m)^2)/n<=q)) o.le have l:=mE n P Q D (iK q) m _ _ F w H u A (by rw[A2 o];nlinarith) (by nlinarith[(AZ.1 h).1,ύ q]) J refine⟨l,?_⟩;have e:=il n p X m;generalize ∑k∈iD n,X k=z at e l A⊢;rw[show q=((∑j∈iD n,(X j-z/n)^2)/n+d)+(m-z/n)^2 by rw[<-I,e,add_div,mul_div_cancel_left₀ _ o.ne'];ring]at t h exact bI n B V _ _ D В t (l.trans (by nlinarith)) h lemma cq{d n:п}{e:iJ}{x g:ZB}(h:bF d n e x g=Л): iU d n e x g=Л/\d*n+1<2^32/\n<=2^20/\rq nж.toInt64.toFloat (1/nж.toInt64.toFloat)=Л:=by simp only[bF,Β,AG]at h;obtain⟨⟨⟨j,m⟩,o⟩,l⟩:=h;exact⟨by rw[<-eJ];exact j,А,А,l⟩ lemma dA{d n:п}{e:iJ}{x g:ZB}(h:iU d n e x g=Л):xв=d*n/\gв=n:=by simp only[iU,Β,ZH,A4]at h;exact⟨by simpa using h.1.1.1.1.1.2,by simpa using h.1.1.1.1.2⟩ lemma gc(o n:п)(h:iJ)(x g b:ZB)(K:iU o n h x g=Л)(L:∀jQ _ А obtain⟨l1,l2,-⟩:=ee n l;obtain⟨G,V,F,O,hV,A,e⟩:=g6 (lw n) _ (dw h*NR.pt 149) (1/nж.toInt64.toFloat) x _ _ h1 h2 h3;rw[e]at v⊢;simp only[Β,AG]at v;obtain⟨⟨S,o2⟩,o3⟩:=v;obtain⟨E,W,J⟩:=gR n x _ _ h1 h2 h3 (r*n) Z u4 q l m D;rw[<-O]at E W J;obtain⟨H,U⟩:=g8 n h x _ _ h1 h2 h3 (r*n) Z u4 q l m (ev K) t D G E J;rw[<-hV]at H U;have X:=(d4 h (ev K) t).2.2;have u:=vp n l (rv V) _ _ В X U;obtain⟨-,-,-,q2,-,-,Y,-,-,w3⟩:=d0 V (lw n) _ H u S;obtain⟨I,w2,p,w,B⟩:=fn V (lw n) _ H u S o3;generalize M:(dn V (lw n) (xD n x r h true)).2=d at Y I w2 p w B A⊢;rw[<-Y]at w3;obtain⟨hm,as⟩:=gP G (dw d) F E (au d I).1 p A;have y:(lw n)а+Fа<=25:=by have:=κ.1 o2;rw[ξ]at this;simp only[iE]at this;omega have⟨k1,k2⟩:=gO n q l (λj=>rv (dw x[r*n+j]!)) (rv G) _ (rv V) _ (rv (dw d)) (2^(lw n)а) (2^Fа) X U u q2 (by rw[(au d I).2];exact w3) p hm W l2 (AC Г l1) (Ah Г) (by rw[<-AK];exact AC Г y) have c:=fo V n _ (iS n x r (i7 n x r)+ZA h) (((n:ℝ)+31)/2^54) l H (by have:=em n x r (i7 n x r);linarith) (by rw[iv n x r h m];exact k2) (by gcongr;norm_num) (ga n x r h Л q t) S rw[M]at c;rw[<-c] exact gF n x r j z g[j]! b[j]! d G (1/dw d) _ ((lw n)а+Fа) _ (m j z) (N j z) (L j z) I w2 p w B E J (by rw[ξ,ξ];simp only[iE];omega) y (by rw[fJ n x r m,AK];exact k1) lemma fg(d n:п)(p:Д)(o v:с)(h:iJ)(x g b:ZB)(u t:Ж)(z:d*n+1<2^32) (J:d*n<=xв) (G:n<=gв) (B:n<=bв) (m:n<=uе) (l:n<=tе) (F:п->iJ) (H:∀j∀M A y,(rL p (xD n x r h Л) o v x (r*n)д ((r*n)д+nд) M A y).ok=Л->∀j (RL d n p o v h x g b u t z J G B m l (r+1) w L)в=eв/\ ∀q,(RL d n p o v h x g b u t z J G B m l (r+1) w L)[q]! =if r*n<=q/\q?_⟩;rw[V,X,A,y,ϝ,ώ];split_ifs<;>first|rfl|omega split .rename_i O;exact K _ _ (cC _ _ _ F _ (λj N=>by have:=β.mp N;rw[y]at this;rw[bH,bH,bH,ey,ey,Dense.af (a:=(r*n)д) (b:=j) (by have:=ς;omega),(А:(r*n)дб+jб=r*n+jб),H _ this,D _ this] exact E r I _ _ _ O _ this) _ _ _) .exact K _ _ (cC _ _ _ F _ (λj N=>by have:=β.mp N;rw[y]at this;rw[A,Q r I _ this]) _ _ _) .rename_i I refine⟨Н,λq=>?_⟩;rw[AP] intro⟨Z,k2⟩;have:=ψ n (Nat.le_of_not_lt I);omega termination_by d-r lemma fh(d n:п)(o:Д)(m t:с)(h:iJ)(x g:ZB)(p:Ж)(v:d*n+1<2^32) (E:d*n<=xв) (A:n<=gв) (l:n<=pе) (F:п->iJ) (B:∀j∀H y u,(rR o (xD n x r h М) m t x (r*n)д ((r*n)д+nд) H y u).ok=Л->∀j (RR d n o m t h x g p v E A l (r+1) w G)в=eв/\ ∀q,(RR d n o m t h x g p v E A l (r+1) w G)[q]! =if r*n<=q/\q?_⟩;rw[O,S,y,u,ϝ,ώ];split_ifs<;>first|rfl|omega split .rename_i J;exact K _ _ (cC _ _ _ F _ (λj I=>by have:=β.mp I;rw[u]at this;rw[bH,bH,ey,Dense.af (a:=(r*n)д) (b:=j) (by have:=ς;omega),(А:(r*n)дб+jб=r*n+jб),B _ this] exact z r D _ _ _ J _ this) _ _ _) .exact K _ _ (cC _ _ _ F _ (λj I=>by have:=β.mp I;rw[u]at this;rw[y,L r D _ this]) _ _ _) .rename_i D refine⟨Н,λq=>?_⟩;rw[AP] intro⟨V,W⟩;have:=ψ n (Nat.le_of_not_lt D);omega termination_by d-r def aW(rows n:п)(eps:т)(x g:ZB):ZB:= if h:bF rows n eps x g then have d:=cq h;have z:=dA d.1 let gd:=ba g RR rows n (lw n) (dw eps*NR.pt 149) (1/nж.toInt64.toFloat) eps x g gd d.2.1 А А (by rw[(ax g).1];omega) 0 (AY (rows*n) 0) (О) else rmsnormSpec rows n eps x g lemma aX(a b:ZB)(e:aв=bв)(h:∀q(jZ e n l x g)[q]!) (r*n+j)=ZT (ZA x[r*n+j]!*ZA g[j]!/ZA (iY (iS n x r 0+ZA l))):= (λr o j m=>by have⟨p,w,y⟩:=fC o m;rw[jZ];dsimp only;rw[Qg _ p];rw[w,y];rw[Qg _ o]) have⟨E,F⟩:=fh e n (lw n) (dw l*NR.pt 149) (1/nж.toInt64.toFloat) l x g (ba g) d.2.1 А А (by rw[(ax g).1];omega) (λq=>(jZ e n l x g)[q]!) (λj m=>(ax g).2 j А) u (λr o A B D t j m=>(gf e n l x g d.1 d.2.1 d.2.2.1 d.2.2.2 r o A B D t j m).trans (u r o j m).symm) 0 (ka (e*n) 0) (О) apply aX _ _ (by rw[E,v,ϧ]) (λq p=>?_) rw[F q,if_pos ⟨А,by rw[v]at p;exact p⟩] .rw[aW,Ax h] lemma fG{d n:п}{e:iJ}{x g b:ZB}(h:(bF d n e x g&&bв==n&&b.all kO)=Л): bF d n e x g=Л/\bв=n/\∀jNR.d5 b (by simpa[kC]using o) j А⟩ def ay(rows n:п)(eps:т)(x g b:ZB):ZB:= if h:bF rows n eps x g&&bв==n&&b.all finiteWord then have l:=fG h;have d:=cq l.1;have z:=dA d.1 RL rows n (lw n) (dw eps*NR.pt 149) (1/nж.toInt64.toFloat) eps x g b (ba g) (ba b) d.2.1 А А А (by rw[(ax g).1];omega) (by rw[(ax b).1];omega) 0 (AY (rows*n) 0) (О) else layernormSpec rows n eps x g b lemma bJ:ay=layernormSpec:=by funext e n m x g b;by_cases h:(bF e n m x g&&bв==n&&b.all kO)=true .rw[ay,As h] have l:=fG h;have d:=cq l.1;have z:=dA d.1;unfold layernormSpec layernormWith;rw[if_pos (by have v:=h;simp only[Β,Aa]at v⊢;exact⟨⟨d.1,l.2.1⟩,v.2⟩)] have y:(jt e n m x g b)в=e*n:=by simp[jt] have w:∀r(jt e n m x g b)[q]!) (r*n+j)=ZT ((ZA x[r*n+j]!-i7 n x r)*ZA g[j]!/ZA (iY (iS n x r (i7 n x r)+ZA m))+ZA b[j]!):= (λr p j o=>by obtain⟨t,A,B⟩:=fC p o;unfold jt;dsimp only;rw[Qg _ t];simp only[A,B];simp only[Qg _ p,Fin.val_mk]) obtain⟨G,H⟩:=fg e n (lw n) (dw m*NR.pt 149) (1/nж.toInt64.toFloat) m x g b (ba g) (ba b) d.2.1 А А А (by rw[(ax g).1];omega) (by rw[(ax b).1];omega) (λq=>(jt e n m x g b)[q]!) (λj o=>(ax g).2 j А) (λj o=>(ax b).2 j А) w (λr p D E F u j o=>(gc e n m x g b d.1 l.2.2 d.2.1 d.2.2.1 d.2.2.2 r p D E F u j o).trans (w r p j o).symm) 0 (ka (e*n) 0) (by simp) apply aX _ _ (by rw[G,y,ϧ]) (λq t=>?_) rw[H q,if_pos ⟨А,by rw[y]at t;exact t⟩] .rw[ay,Ax h] end Norm end def kernels:Kernels where core:=⟨sumSpec,dotSpec⟩ dense:=⟨Dense.bQ,Dense.da⟩ conv:=specConv elem:=⟨avgpoolSpec,maxpoolSpec,Bn.bA,scaleShiftSpec⟩ norm:=⟨Norm.aW,Norm.ay⟩ theorem correct:Obligation kernels:=by simp only[Obligation,kernels,specKernels,specCore,specDense,specElem,specNorm, Dense.cJ,Dense.dK,Bn.co,Norm.b9,Norm.bJ] end Submission