import ContractExact namespace Submission open ExactRuntime FloatLib.Floats.Formats.BinaryInterchange FloatLib.Floats open ExactRuntime renaming idxOf->γ,Word->δ,mantOf->ε,oneW->ζ,signOf->η,expOf->θ,ofW->ι,Fmt->κ,ConvShape->ο,toWord->π,finishWord->ρ,rationalWord->ς,dotOf->Γ,windowAt->Μ,decodeD->Ν,limbVal->ϋ,sqrtLower->Ϗ,decodeD_toRat->ϙ,mantOf_lt_24->Ϛ,addLimbs64->ϛ,toDyadic_ofUInt32->Ϡ,rowVariance->ϫ,finishWord_scale->Aa,sqrtRational->Ac,decodeD_negative->Ad,ConvShape.ho->Es,ConvShape.wo->Et open Nat renaming mod_eq_of_lt->ν,shiftRight_eq_div_pow->ψ,mul_le_mul_right->ω,shiftLeft_eq->Α,zero_add->Β,two_pow_pos->Δ,mod_lt->Ε,mul_comm->Θ,pow_le_pow_right->Ι,pow_add->Κ,pos_of_ne_zero->Ο,lt_of_le_of_lt->Ρ,div_eq_of_lt->Υ,mul_pos->ϊ,le_add_right->ώ,add_zero->ϑ,add_mul_div_right->ϔ,div_lt_of_lt_mul->ϕ,cast_sub->ϗ,one_mul->Ϙ,add_comm->Ϟ,add_mul->ϟ,and_two_pow_sub_one_eq_mod->ϡ,mul_assoc->ϣ,le_mul_of_pos_right->Ϧ,div_div_eq_div_mul->ϧ,add_le_add_left->Ϯ,log2_self_le->ϰ,add_mul_mod_self_right->ϲ,le_mul_of_pos_left->ϳ,add_lt_add_left->ϴ,div_add_mod'->϶,zero_mul->ϸ,lt_trans->Ϲ,log2_lt->Ϻ,eq_zero_or_pos->Ae,log2_eq_iff->Af,lt_of_lt_of_le->Ag,succ_mul->Ah,sub_zero->Ai,mul_lt_mul_of_pos_right->Aj,lt_log2_self->Ak,lt_of_sub_eq_succ->Al,le_div_iff_mul_le->Am,div_lt_iff_lt_mul->An,lt_succ_iff->Ao,lt_or_eq_of_le->Ap,div_add_mod->Aq,mul_le_mul->Ar,mul_lt_mul_of_lt_of_le->As,le_sub_of_add_le->Au,div_mul_le_self->Av,sub_add_cancel->Aw,mul_eq_zero->Ax,le_one_iff_eq_zero_or_eq_one->Ay,shiftLeft_add_eq_or_of_lt->Bq,and_two_pow_sub_one_of_lt_two_pow->Bx,sub_lt_left_of_lt_add->Bz,one_le_two_pow->BE,testBit_eq_decide_div_mod_eq->BJ,sub_le_iff_le_add'->BK,mul_lt_mul''->BP,add_assoc->BU,reduceMod->BY,sub_le_sub_right->BZ,toUInt32_eq->Cd,mul_add_mod->Ce,mul_add_div->Cf,le_add_left->Cg,mul_le_mul_left->Ci,mul_zero->Co,le_trans->Cp,sub_right_comm->Cu,add_right_comm->Cv,mod_mul_right_div_self->Cw,sub_add_eq->Cx,add_le_add->Cy,add_sub_cancel->Cz,add_mul_mod_self_left->CF,le_log2->CH,le_of_lt_succ->CI,cast_zero->CP,pos_of_mul_pos_right->CQ,add_sub_cancel_left->CT,pos_of_mul_pos_left->CU,one_le_iff_ne_zero->Dd,sub_eq_zero_iff_le->De,toUInt64_eq->Do,add_one_mul->Dp,div_le_self->Dq,le_of_sub_eq_zero->Dw,cast_ofNat->DF,add_mul_div_left->DG,mod_mul->DH,pow_lt_pow_right->DJ,mul_ne_zero_iff->DR,reducePow->DU,mod_le->DY,not_lt->DZ,cast_pow->Ei,add_sub_of_le->Ej,zero_lt_of_lt->Ek,add_div_right->Em,le_of_not_le->Ev,zero_le->Ey,mod_add_div->Ez,cast_natAbs->EA,sub_le->EI,lt_irrefl->EN,cast_add->ER,cast_mul->ES,lt_asymm->ET,cast_one->EU,succ_pos->EV,mod_one->Fb open UInt64 renaming toNat_add->ξ,toNat_inj->σ,toNat_sub_of_le->Η,toNat_shiftRight->Ξ,toNat_sub->Τ,lt_iff_toNat_lt->Ψ,toNat_shiftLeft->ό,le_iff_toNat_le->ϐ,toNat_zero->Ϝ,toNat_mul->ϯ,toNat_lt->Az,toNat_toUInt32->AA,reduceToNat->Bc,toNat_and->BR,zero_xor->Ch,toNat_ofNat_of_lt'->CG,add_assoc->CY,toNat_not->CZ,toNat_one->Da,zero_shiftRight->Dm,toNat_or->Du,or_eq_zero_iff->DA,zero_shiftLeft->DB,toNat->Er,not_lt->EO,size->Fd open USize renaming le_size->τ,lt_iff_toNat_lt->υ,size->Λ,toNat_one->Φ,toNat_lt_size->ϝ,le_iff_toNat_le->Bs,toNat_sub_of_le->BN,toNat_mul->Dv,toNat_inj->EF,toNat_add->EG open Bool renaming false_eq_true->φ,xor->Ζ,and_eq_true->Ω,not_eq_true'->ϵ,or_eq_true->Ϸ,eq_iff_iff->AB,false_ne_true->AC,and_self->DW,and_true->DX,and_assoc->EK,and_false->EL,xor_false->EM open Array renaming replicate->Χ,ext'->ϻ,getElem_ofFn->AD,size_ofFn->AE,ofFn->AF,mkEmpty->AY,emptyWithCapacity->Ba,emptyWithCapacity_eq->Bw,size_map->CC,getElem_map->CN,getElem_replicate->CW,size_push->Dt,getElem_push_lt->Dy,getElem_push_eq->Dz,getElem_toList->DL,range->DM,size_replicate->DN,toList_push->Eo,all_eq_true->Ep,ext->EP open UInt32 renaming toNat_inj->ύ,toNat_shiftRight->Ϣ,ofNat->Ϥ,toNat_toUInt64->AG,toNat_and->AH,toNat_toUSize->AI,le_iff_toNat_le->AJ,toNat_lt_size->AK,toNat_ofNat'->AL,reduceToNat->CD,toNat_sub->CX,toNat_sub_of_le->Dj,toNat_shiftLeft->Dk,lt_iff_toNat_lt->Dl,ofNat_toNat->Ee,xor_zero->EE,size->Fc open List renaming range->ϒ,range'_succ->Ϩ,ext_getElem->ϩ,length_ofFn->AM,getElem_ofFn->AN,foldl_cons->AO,range'->Bd,drop_of_length_le->BL,mem_range->BM,range_eq_range'->Ca,map_congr_left->Ck,size_toArray->CK,append_assoc->CL,length_range->CM,map_cons->CR,map_map->Df,sum_map_mul_right->Dg,getElem_cons_zero->Dh,length_nil->Dr,length_map->Ds,length_singleton->Dx,ofFn->DP,map_add_range'->DS,sum_cons->DV,length_cons->Ex,nil_append->EB,mem_map->EZ open FloatFormat renaming toModel->ϓ,binary32->AZ,subnormalAlignExp->Cb,ieeeMinNormalExponent->Ef,ieeeMaxNormalExponent->Eg open Model.NativeBinary32 renaming mkBits->ϥ,roundRatScaled->AW,ofUInt32_roundRatScaled->Bf,ofUInt32->Bj,ofUInt32_mkBits->BB open Int renaming add_emod->Ϫ,emod_eq_emod_iff_emod_sub_eq_zero->By,ofNat->BG,toNat_of_nonneg->Cj,add_mul_emod_self_left->CA,negSucc->CJ,shiftLeft_eq->CV,ofNat_eq_natCast->DK,ModEq->DO,ModEq.add_right->DT,zero_add->EW,sub_emod->EX,toNat->Fe open Int64 renaming ofInt->ϱ open FloatLib.Numerics renaming roundQuotientEven->AP,roundShiftRightEven->AQ,shiftRightJam->AR,FixedWord.roundShiftRightEven_toNat->Bg,roundShiftRightEven_shiftRightJam->Bh,FixedWord.roundShiftRightEven->Bm,roundShiftRightEven_le_succ->Bn,or_one_eq->Bu,Dyadic->BD,roundShiftRightEven_eq_roundQuotientEven->BQ,roundShiftRightEven_mul_two_pow_of_le->Cc,roundShiftRightEven_eq_guard_sticky->Cl,div_two_pow_le_roundShiftRightEven->Cq,roundShiftRightEven_mul_two_pow->CE,shiftRightJam_ne_zero->DC,Radix.toReal->Fa open Model renaming toReal->AS,roundDyadicGeneral->AT,addDyadic->AU,roundDyadicGeneral_eq_roundDyadic->AV,isNaN_eq_false_of_toDyadic?_some->AX,isInf_eq_false_of_toDyadic?_some->Be,ofModel_finite_normalized_eq_ofFields->Bo,roundDyadic->Bt,packRoundedSubnormal->Bv,isFinite->BI,div->BO,signBit->BS,ofModel->BT,isZero->Cm,finishRoundedMantissa->Cn,add->Cr,zero->Cs,pow2->Ct,maximum->CO,packRoundedNormal->CS,toNatBits->Dn,ofUInt32->DD,nativeOverflow->DE,fma->Eu,ofFields->EH,ofBits->EQ open Or renaming inl->Ea,inr->EY open FloatLib.Numerics.Dyadic renaming cast_toRat->BC,add_toRat->BF,toRat_eq_zero_iff->Di,addFields->Eb,mul_toRat->Ec,mulFields->Ed,add->EC,mul->ED open Float.Model renaming totalExponent->Bb open Real renaming sqrt->Db open Float.Model.UnpackedFloat renaming roundWithAccuracy->Bp,accuracyOfFraction->Dc open Float.Model.Format renaming targetExponent->BH open FloatLib.Numerics.RationalBinary renaming lessThanPowerOfTwo->Bi,atLeastPowerOfTwo->Bk,scaleByPowerOfTwo->Bl,floorLog2->Br local notation:max x:max "˧"=>UInt64.toNat (x :) local notation:max x:max "؛"=>USize.toNat (x :) local notation:max x:max "؎"=>UInt32.toNat (x :) local notation:max x:max "۞"=>Nat.toUSize (x :) local notation:max x:max "܀"=>Nat.log2 (x :) local notation:max x:max "܂"=>Fin.val (x :) local notation:max x:max "܃"=>Array.size (x :) local notation:max x:max "܅"=>UInt32.toUInt64 (x :) local notation:max x:max "܉"=>UInt64.toNat_lt (x :) local notation:max x:max "܊"=>ExactRuntime.ConvShape.stride (x :) local notation:max x:max "܍"=>Array.toList (x :) local notation:max x:max "߷"=>FloatLib.Floats.Formats.BinaryInterchange.FloatFormat.fracWidth (x :) local notation:max x:max "߸"=>Nat.toUInt64 (x :) local notation:max x:max "՜"=>UInt64.toUInt32 (x :) local notation:max x:max "׆"=>Int.toNat (x :) local notation"א"=>by omega local notation"ב"=>by norm_num local notation"ג"=>by simp local notation"ד"=>by decide local notation"ה"=>by positivity local notation"ו"=>by simp;omega local notation"ז"=>by grind local notation"ח"=>by simp_all local notation"߾"=>0x80000000 local notation"߿"=>0x100000000 local notation"ק"=>0x7FFFFFFF local notation"ר"=>ite_true local notation"ש"=>ite_false local notation"ת"=>decide_eq_true_eq local notation"ؠ"=>zpow_natCast local notation"ة"=>decide_eq_true_iff local notation"ح"=>getElem!_pos local notation"ض"=>Fmt.minSubnormalExponent local notation"ػ"=>UInt64 local notation"ؼ"=>UInt32 local notation"ؽ"=>Array local notation"ؾ"=>USize local notation"ف"=>Bool local notation"ٳ"=>Nat local notation"ٴ"=>Int local postfix:max"ٽ"=>Array.size local postfix:max"پ"=>UInt64.toNat local postfix:max"پ"=>USize.toNat local postfix:max"پ"=>UInt32.toNat local postfix:max"پ"=>Int.toNat local postfix:max"ٿ"=>Nat.toUSize local postfix:max"ٿ"=>UInt64.toUSize local postfix:max"ٿ"=>UInt32.toUSize local notation:max"ڀ"k:max=>Array.ofFn (n:=k) local notation"ހ"=>4294967295 local notation"ށ"=>1048576 local notation"ނ"=>16777216 local notation"ރ"=>8388608 local notation"ބ"=>4611686018427387904 local notation"ޅ"=>0xFFFF structure Acc where pos:ؽ ٳ neg:ؽ ٳ special:ف negZero:ف def Acc.empty:Acc:=⟨Χ 18 0,Χ 18 0,false,true⟩ def Acc.total (acc:Acc):ٴ:=(ϋ acc.pos.toList:ٴ)-ϋ 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,ϛ ng m.toUInt64 idx,sp,false⟩ else ⟨ϛ pos m.toUInt64 idx,ng,sp,false⟩ @[inline] def Acc.markSpecial (acc:Acc):Acc:= match acc with | ⟨pos,ng,_,nz⟩=>⟨pos,ng,true,nz⟩ lemma Acc.add_spec (a:Acc) (m d:ٳ) (b:ف) (e:a.posٽ=18) (f:a.negٽ=18) (g:m<2^64) (h:d/32+1<18) : (a.add m d b).posٽ=18/\(a.add m d b).negٽ=18 /\ (a.add m d b).special=a.special /\ (a.add m d b).negZero=(a.negZero&&(decide (m=0)&&b)) /\ (a.add m d b).total=a.total+(if b then -(m:ٴ) else m)*2^d:=by obtain⟨pos,k,l,n⟩:=a;simp only at e f;by_cases j:m=0 . simp[add,total,j,e,f] . cases b<;>refine⟨by simp[add,j,addLimbs64_size,e],by simp[add,j,addLimbs64_size,f],by simp[add,j],by simp[add,j],?_⟩<;>simp only[add,j,ש,φ,ר,addLimbs64_eq _ _ _ g,total]<;>rw[addLimbs_val _ _ _ א]<;>push_cast<;>ring lemma Acc.total_empty:Acc.empty.total=0:=ד section open FloatLib.Numerics lemma ZbF (s:ف) (m:ٳ) (e:ٴ) (j:ٳ) (h:j+25<=m܀):Bt κ ⟨s,shiftRightJam m j,e+j⟩=Bt κ ⟨s,m,e⟩:=by obtain⟨l,b,d⟩:j<=m܀/\23<=m܀-j/\23<=m܀:=א;have f:m≠0:=by rintro rfl;simp at h have n:=ϰ f;have g:2^(j+1)<=m:=Cp (Ι ב ((ώ (j+1) 24).trans h)) n;have o:=log2_shiftRightJam m j g;have k:AR m j≠0:=DC m j (Cp (Ι ב (ώ j 1)) g);rw[<-AV,<-AV];unfold AT;have p:κ߷=23:=rfl;have q:ض=-149:=rfl;have r:κ.minNormalExponent=-126:=rfl;simp only[beq_iff_eq,o,k,f,ϗ l,sub_add_add_cancel,p,q,r,b,d,↓reduceIte];clear f n g o k l b d p q r;split_ifs;rfl;congr 1;obtain⟨a,b⟩:=Int.eq_negSucc_of_lt_zero (א:e+j- -149<0);obtain⟨d,k⟩:e- -149=CJ (j+a)/\0 ٳ | 0=>0 | k+1=>a[i]! + 2^32*Yg a (i+1) k lemma Zv (a:ؽ ٳ) (i k m:ٳ):Yg a i (k+m)=Yg a i k+2^(32*k)*Yg a (i+k) m:=by induction k generalizing i;simp[Yg];next k b=>rw[Cv _ 1,Yg,Yg,b,BU i 1 k,Ϟ 1 k];ring lemma ZbG (a b:ؽ ٳ) (i j k:ٳ) (h:∀ t,t a[i+t]! = b[j+t]!):Yg a i k=Yg b j k:=by induction k generalizing i j with |zero=>rfl |succ k d=>rw[Yg,Yg,d (i+1) (j+1) (λ t e=>by rw[(א:i+1+t=i+(t+1)),(א:j+1+t=j+(t+1))];exact h (t+1) א),show a[i]! =b[j]! by simpa using h 0 א] lemma Zw (a:ؽ ٳ) (i k:ٳ):Yg a i k=0↔∀ t,t a[i+t]! = 0:=by induction k generalizing i with |zero=>simp[Yg] |succ k d=>rw[Yg,Nat.add_eq_zero_iff,Ax,d (i+1)];have e:(2:ٳ)^32≠0:=ג;constructor;rintro⟨f,b|b⟩ t g;exact absurd b e;rcases t with _|t;simpa using f;rw[(א:i+(t+1)=i+1+t)];exact b t א;intro h;refine⟨by simpa using h 0 א,EY λ t g=>?_⟩;rw[(א:i+1+t=i+(t+1))];exact h (t+1) א lemma ZbH (a:ؽ ٳ) (i k:ٳ) (h:∀ t,t a[i+t]! < 2^32):Yg a i k<2^(32*k):=by induction k generalizing i with |zero=>simp[Yg] |succ k b=>have d:=h 0 א;have e:=b (i+1) (λ t f=>by rw[(א:i+1+t=i+(t+1))];exact h (t+1) א);simp at d;rw[Yg,show 32*(k+1)=32+32*k by ring,pow_add];linarith lemma O0 (a:ؽ ٳ) (t:ٳ) (h:a܃<=t):a[t]! = 0:=ח lemma ZbI (a:ؽ ٳ) (i k:ٳ) (h:a܃<=i+k):Yg a i k=ϋ (a܍.drop i):=by induction k generalizing i;simp[Yg,BL (by simpa using h:a܍.length<=i),ϋ];rename_i b;rw[Yg,b (i+1) א];by_cases d:i a[t]! = 0) (e:∀ t,b+n<=t -> a[t]! = 0) : ϋ a܍=2^(32*b)*Yg a b n:=by rw[<-List.drop_zero (l:=a܍),<-ZbI a 0 (b+(n+a܃)) א,Zv,Zv,(Zw a 0 b).2 (λ t f=>by simpa using d t f),(Zw a (0+b+n) a܃).2 (λ t _=>e _ א)];simp def YP (a b:ؽ ٳ) (i ca cb br:ٳ) (out:ؽ ٳ) : ٳ -> ؽ ٳ × ٳ × ٳ × ٳ | 0=>(out,ca,cb,br) | k+1 => let ta:=a[i]! + ca;let tb:=b[i]! + cb;let t:=ta%߿+߿-tb%߿-br;YP a b (i+1) (ta/߿) (tb/߿) (1-t/߿) (out.push (t%߿)) k lemma N9 (a b:ؽ ٳ) (i f g e:ٳ) (d:ؽ ٳ) (k:ٳ) (j:e<=1) (h:∀ t,t d[t]! < 2^32) : let r:=YP a b i f g e d k r.1ٽ=d܃+k/\(∀t,tr.1[t]! <2^32)/\(Yg r.1 0 r.1ٽ:ٴ)+2^(32*(d܃+k))*(r.2.1-r.2.2.1-r.2.2.2:ٴ)=Yg d 0 d܃+2^(32*d܃)*((Yg a i k:ٴ)-Yg b i k+f-g-e):=by induction k generalizing i f g e d with |zero=>exact⟨by simp[YP],by simpa[YP]using h,by simp[YP,Yg]⟩ |succ k q=>simp only[YP];set n:=a[i]!+f;set o:=b[i]!+g;set t:=n%߿+߿-o%߿-e;obtain⟨w,x,p⟩:=q (i+1) (n/߿) (o/߿) (1-t/߿) (d.push (t%߿)) א (by intro s l;simp only[Dt]at l;rcases Ap (Ao.mp l)with l|rfl;rw[ح _ s ו,Dy l,<-ح d s l];exact h s l;rw[ح _ _ ג,Dz];omega);refine⟨by simp[w];omega,x,?_⟩;simp only[Dt]at p⊢;rw[(א:d܃+(k+1)=d܃+1+k),p,(by rw[Zv,ZbG _ d 0 0 d܃ (λ s l=>by rw[ح _ _ ו,Dy א,<-ح d _ א])];simp only[Yg,Β,Co,ϑ];rw[ح _ _ ג,Dz]:Yg (d.push (t%߿)) 0 (d܃+1)=Yg d 0 d܃+2^(32*d܃)*(t%߿)),Yg,Yg];simp only[ER,ES,Ei,DF];linear_combination (2:ٴ)^(32*d܃)*(א:((t%߿:ٳ):ٴ)+߿*((n/߿:ٳ)-(o/߿:ٳ)-(1-t/߿:ٳ))=(a[i]!:ٴ)-b[i]!+f-g-e) def YW (r:ؽ ٳ):ٳ -> Option ٳ | 0=>none | k+1=>if r[k]! != 0 then some k else YW r k def YX (r:ؽ ٳ):ٳ -> ف | 0=>false | k+1=>r[k]! != 0||YX r k lemma ZbK (r:ؽ ٳ) (k:ٳ) (h:YW r k=none):∀ t,t r[t]! = 0:=by induction k with |zero=>intro t a;omega |succ k b=> simp only[YW]at h;split at h . cases h . rename_i d;intro t a;rcases Ap (Ao.mp a)with a|rfl . exact b h t a . simpa using d lemma N8 (r:ؽ ٳ) (k h:ٳ) (d:YW r k=some h):h t r[t]! = 0:=by induction k;simp[YW]at d;rename_i j;simp only[YW]at d;split at d<;>rename_i f;cases d;exact⟨א,by simpa using f,λt g e=>א⟩;obtain⟨a,b,c⟩:=j d;refine⟨א,b,λt g e=>?_⟩;rcases Ap (Ao.mp e)with e|rfl;exact c t g e;simpa using f lemma N7 (r:ؽ ٳ) (k:ٳ):YX r k=false↔∀ t,t r[t]! = 0:=by induction k with |zero=>simp[YX] |succ k b=> simp only[YX,Bool.or_eq_false_iff,bne_eq_false_iff_eq,b];constructor . rintro⟨d,e⟩ t a;rcases Ap (Ao.mp a)with a|rfl . exact e t a . exact d . intro h;exact⟨h k א,λ t a=>h t א⟩ lemma ZbL (r:ؽ ٳ) (k:ٳ):YX r k=(Yg r 0 k != 0):=by have a:=Zw r 0 k;simp at a;cases h:YX r k;rw[a.2 ((N7 r k).1 h)];rfl;simp;exact λ b=>by have:=(N7 r k).2 (a.1 b);simp_all lemma ZbM (a x y h:ٳ) (b:a<2^(32*h)):shiftRightJam (a+2^(32*h)*(x+2^32*y)) (32*h+2)=if x%4 != 0||a != 0 then (y*1073741824+x/4)|||1 else y*1073741824+x/4:=by have k:2^(32*h+2)=4*2^(32*h):=ז;have q:x%4<4:=Ε x ב;have f:a+2^(32*h)*(x%4)<4*2^(32*h):=by nlinarith have l:a+2^(32*h)*(x+2^32*y)=(a+2^(32*h)*(x%4))+4*2^(32*h)*(y*1073741824+x/4):=by conv_lhs=>rw[<-Ez x 4] ring have g:a+2^(32*h)*(x%4)=0↔¬(x%4≠0\/a≠0):=by constructor;intro d;have o:=Nat.eq_zero_of_add_eq_zero d;obtain p|p:=Ax.mp o.2<;>omega;intro d;simp at d;simp[d.1,d.2] unfold AR;dsimp only;rw[k,l,DG _ _ א,Υ f,Β,CF,ν f];by_cases j:x%4≠0\/a≠0 . have:¬(a+2^(32*h)*(x%4)=0):=λ d=>g.mp d j;have e:(x%4 !=0||a !=0)=true:=ז;simp only[beq_iff_eq,this,ש,e,ר] . have:=g.mpr j;have e:(x%4 !=0||a !=0)=false:=ז;simp only[beq_iff_eq,this,ר,e];rfl def Yas (neg:ف) (r:ؽ ٳ) (e:ٴ) (negZero:ف):ؼ:= match YW r rٽ with | none=>ρ 0 e negZero | some 0=>ρ (if neg then -(r[0]! : ٴ) else r[0]!) e negZero | some (h+1) => let x:=r[h]!;let v:=r[h+1]! * 1073741824+x/4;let m:=if x%4 != 0||YX r h then v|||1 else v;π (Bt κ ⟨neg,m,e+((32*h+2:ٳ):ٴ)⟩) lemma F9 (b:ف) (R:ٳ) (e:ٴ) (a:ف) (d:R≠0):ρ (if b then -(R:ٴ) else R) e a=π (Bt κ ⟨b,R,e⟩):=by have f:(0:ٴ)simp[ρ,ofIntDyadic,d,not_lt.2 f.le,Ο d] lemma N6 (b:ف) (r:ؽ ٳ) (e:ٴ) (a:ف) (d:∀ t,t r[t]! < 2^32) : Yas b r e a=ρ (if b then -(Yg r 0 r܃:ٴ) else Yg r 0 r܃) e a:=by unfold Yas;split;rename_i o;rw[(Zw r 0 r܃).2 (λ t f=>by simpa using ZbK r _ o t f)];simp;rename_i g;obtain⟨p,j,k⟩:=N8 r _ 0 g;rw[(א:r܃=1+(r܃-1)),Zv,(Zw r (0+1) (r܃-1)).2 (λ t f=>k _ א א)];simp[Yg] rename_i h g;obtain⟨p,j,k⟩:=N8 r _ (h+1) g;have l:Yg r 0 r܃=Yg r 0 h+2^(32*h)*(r[h]!+2^32*r[h+1]!):=by rw[(א:r܃=h+(2+(r܃-h-2))),Zv,Zv,(Zw r (0+h+2) _).2 (λ t f=>k _ א א)];simp[Yg] have q:Yg r 0 h<2^(32*h):=ZbH r 0 h (λ t f=>d _ א);have n:Yg r 0 r܃≠0:=by rw[l];have:0<2^(32*h)*(r[h]!+2^32*r[h+1]!):=(by have:=Ο j;positivity);omega have s:32*h+2+25<=(Yg r 0 r܃)܀:=by rw[CH n,l];have:=Ο j;calc 2^(32*h+2+25)<=2^(32*h)*2^32:=by rw[<-pow_add];exact Ι ב א _<=2^(32*h)*(r[h]!+2^32*r[h+1]!):=by gcongr;linarith _<=_:=א rw[F9 b _ e a n,<-ZbF b _ e _ s,l,ZbM _ _ _ h q,ZbL] def Yab (pos neg:ؽ ٳ):ٳ -> ٳ | 0=>0 | k+1=>if pos[k]! != 0||neg[k]! != 0 then k+1 else Yab pos neg k lemma ZbO (a b:ؽ ٳ) (k:ٳ):∀ t,Yab a b k<=t -> t a[t]! = 0/\b[t]! = 0:=by induction k<;>intro t d e ·omega rename_i f;simp only[Yab]at d;split at d . omega . rename_i g;rcases Ap (Ao.mp e)with e|rfl . exact f t d e . simpa[Ϸ,bne_iff_ne,not_or]using g def YaL (pos neg:ؽ ٳ) (e:ٴ) (negZero:ف):ؼ:= let lo:=lowLimb pos neg posٽ 0;let n:=Yab pos neg (max posٽ negٽ)+1-lo;let e':=e+((32*lo:ٳ):ٴ);let d:=YP pos neg lo 0 0 0 (Ba n) n;if d.2.1=0/\d.2.2.1=0/\d.2.2.2=0 then Yas false d.1 e' negZero else let d':=YP neg pos lo 0 0 0 (Ba n) n;if d'.2.1=0/\d'.2.2.1=0/\d'.2.2.2=0 then Yas true d'.1 e' negZero else finishLimbs pos neg e negZero lemma Q2 (b d:ؽ ٳ) (e:ٴ) (f:ف):YaL b d e f=ρ ((ϋ b܍:ٴ)-ϋ d܍) e f:=by unfold YaL;dsimp only;set g:=lowLimb b d b܃ 0;set n:=Yab b d (max b܃ d܃)+1-g;have o:=lowLimb_zero b d b܃ 0;have p:=ZbO b d (max b܃ d܃);have q (a:ؽ ٳ) (h:a=b\/a=d):ϋ a܍=2^(32*g)*Yg a g n:=by apply ZbJ a g n;intro t j;rcases h with rfl|rfl;exact(o t א j).1;exact(o t א j).2;intro t j;by_cases r:t< max b܃ d܃;rcases h with rfl|rfl;exact(p t א r).1;exact(p t א r).2;rcases h with rfl|rfl<;>exact O0 _ t א have s:=q b (Ea rfl);have u:=q d (EY rfl);rw[show(Ba n:ؽ ٳ)=#[] from rfl];have v:=N9 b d g 0 0 0 #[] n א ג;have w:=N9 d b g 0 0 0 #[] n א ג;have z:Yg (#[]:ؽ ٳ) 0 0=0:=rfl;simp only[CK,Dr,Co,pow_zero,one_mul,z,CP,zero_add]at v w;obtain⟨-,A,x⟩:=v;obtain⟨-,B,y⟩:=w;split_ifs with k l;rw[N6 false _ _ _ A,Aa,s,u];simp;congr 1;rw[k.1,k.2.1,k.2.2]at x;linear_combination (2:ٴ)^(32*g)*x;rw[N6 true _ _ _ B,Aa,s,u];simp;congr 1;rw[l.1,l.2.1,l.2.2]at y;linear_combination (-(2:ٴ)^(32*g))*y;exact finishLimbs_eq b d e f end @[inline] def Yy (acc:Acc) (wa wb:ؼ):Acc:= if θ wa=255\/θ wb=255 then acc.markSpecial else acc.add (ε wa*ε wb) (γ wa+γ wb) (Ζ (η wa) (η wb)) @[specialize] def Yw (fa fb:ٳ -> ؼ) (pos neg:ؽ ٳ) (sp nz:ف) (index:ٳ):ٳ -> Acc | 0=>⟨pos,neg,sp,nz⟩ | count+1 => match Yy ⟨pos,neg,sp,nz⟩ (fa index) (fb index) with | ⟨p,n,s,z⟩=>Yw fa fb p n s z (index+1) count @[inline] def Yn (n:ٳ) (fa fb:ٳ -> ؼ):ؼ:= let acc:=Yw fa fb (Χ 18 0) (Χ 18 0) false true 0 n;if acc.special then dotSpec (ڀ n λ i=>fa i) (ڀ n λ i=>fb i) else YaL acc.pos acc.neg (-298) (n≠0&&acc.negZero) lemma Zn (a b:ؼ):(if Ζ (η a) (η b) then -((ε a*ε b:ٳ):ٴ) else ((ε a*ε b:ٳ):ٴ))=sv a*sv b:=by unfold sv;cases η a<;>cases η b<;>simp lemma ZbP (g h:ٳ -> ؼ) (d e:ؽ ٳ) (f:ف) (a b:ٳ):(Yw g h d e true f a b).special=true:=by induction b generalizing d e f a ·rfl rename_i k;rw[Yw];have j:(Yy ⟨d,e,true,f⟩ (g a) (h a)).special=true:=by unfold Yy Acc.markSpecial Acc.add;split_ifs<;>rfl generalize Yy ⟨d,e,true,f⟩ (g a) (h a)=r at j⊢;obtain⟨p,q,s,z⟩:=r;subst j;exact k .. lemma Q1 (g j:ٳ -> ؼ) (A B:ؽ ؼ) (n:ٳ) (o:∀ k,k A[k]! = g k) (r:∀ k,k B[k]! = j k) (f:Acc) (e d:ٳ) (h:e+d<=n) (t:f.posٽ=18) (u:f.negٽ=18) (l:(Yw g j f.pos f.neg f.special f.negZero e d).special =false) : f.special=false /\ (∀ k,e<=k -> k < e+d -> θ A[k]! ≠ 255/\θ B[k]! ≠ 255) /\ (Yw g j f.pos f.neg f.special f.negZero e d).total=f.total+dsum A B e d /\ (Yw g j f.pos f.neg f.special f.negZero e d).negZero=(f.negZero&&dallNZ A B e d):=by induction d generalizing f e with |zero=>cases f;simp_all[Yw,dsum,dallNZ] |succ count C=>obtain⟨p,q,s,z⟩:=f;have v:=o e א;have w:=r e א;rw[Yw,Yy]at l⊢;generalize g e=a,j e=b at*;by_cases x:θ a=255\/θ b=255;simp only[if_pos x,Acc.markSpecial,ZbP,Bool.true_eq_false]at l;have y:=not_or.mp x;obtain⟨D,E,F,G,H⟩:=Acc.add_spec ⟨p,q,s,z⟩ (ε a*ε b) (γ a+γ b) (Ζ (η a) (η b)) t u (mul_mant_lt _ _) (by have:=idxOf_le _ y.1;have:=idxOf_le _ y.2;omega);rw[if_neg x]at l⊢;obtain⟨I,J,K,L⟩:=C _ (e+1) א D E l;refine⟨F▸I,?_,?_,?_⟩;intro k N O;by_cases M:k=e;subst M;rw[v,w];exact y;exact J k א א;rw[K,H,dsum,v,w,Zn];ring;rw[L,G,dallNZ,v,w];simp[EK] lemma Ze (n:ٳ) (f:ٳ -> ؼ) (k:ٳ) (a:kf i܂)[k]! = f k:=ח lemma Z5 (n:ٳ) (a b:ٳ -> ؼ):Yn n a b=dotSpec (ڀ n λ i=>a i) (ڀ n λ i=>b i):=by unfold Yn;set A:=ڀ n λ i=>a i with y;set B:=ڀ n λ i=>b i with z;set d:=Yw a b (Χ 18 0) (Χ 18 0) false true 0 n;cases l:d.special . obtain⟨-,f,g,o⟩:=Q1 a b A B n (Ze n a) (Ze n b) Acc.empty 0 n א rfl rfl l;have g:d.total=dsum A B 0 n:=by rwa[Acc.total_empty,EW]at g have o:d.negZero=dallNZ A B 0 n:=o;simp only[l,φ,ש];rw[Q2,<-Acc.total];obtain⟨p,u⟩:Aٽ=n∧Bٽ=n:=by simp[y,z] obtain⟨C,D⟩:=dotStateLoop_flags A B {} 0 n (by simp[p]) (by simp[u]) f;set L:=A.map (DD (fmt:=κ)) with h;set R:=B.map (DD (fmt:=κ)) with v;obtain⟨e,w⟩:Lٽ=Rٽ∧Lٽ=n:=ז;have q:∀ k (r:kf k E א)).trans (by rw[w,g]);have x:=Model.Reduction.Internal.dotState_exact_toRat (destination:=κ) L R e q s;unfold dotSpec Model.dot;by_cases j:d.total=0 . rw[Model.Reduction.dotWithStatus_eq_zero_of_finite κ L R .nearestEven e q s (by rw[<-Di,x,t,j];simp),j,finishWord_zero];simp[Model.Reduction.Internal.dotState,Except.map,h,v,p,C,D,o] . rw[Model.Reduction.dotWithStatus_eq_round_of_finite_nonzero κ L R .nearestEven e q s (by rw[Model.Reduction.Semantics.finiteDot_toList_eq_slice L R e,t];simpa using j)];exact finishWord_of_ne _ _ _ _ j (by rw[x,t]) . simp[l] lemma Z6 (a:ؽ ؼ) (n:ٳ) (h:n=a܃):(ڀ n λ i=>a[i܂]!)=a:=by subst h;apply EP ג;intro i d b;rw[AD,ح a i b] lemma ZbQ (n:ٳ) (c:ؼ):(ڀ n λ _=>c)=Χ n c:=by apply EP ג;simp def YaM (a b:ؽ ؼ):ؼ:= if aٽ=bٽ then Yn aٽ (λ i=>a[i]!) (λ i=>b[i]!) else dotSpec a b def YaN (x:ؽ ؼ):ؼ:=Yn xٽ (λ i=>x[i]!) (λ _=>ζ) lemma ZbR (a b:ؽ ؼ):YaM a b=dotSpec a b:=by unfold YaM;split;next h=>rw[Z5,Z6 a _ rfl,Z6 b _ h] rfl lemma ZbS (x:ؽ ؼ):YaN x=sumSpec x:=by rw[YaN,Z5,Z6 x _ rfl,ZbQ,sumSpec] lemma Zi:Yn=Γ:=funext λ n=>funext λ a=>funext λ b=>Z5 n a b lemma Q0 (w:δ):π (ι w)=w:=by apply ύ.1;simp only[π,ι,Dn,ofUInt32_bits];exact ν w.toBitVec.isLt lemma P9 (z:Model κ):ι (π z)=z:=by have h:Dn z<2^32:=Model.toNatBits_lt_two_pow z;simp only[ι,π,DD,AL,ν h];exact Model.ofNatBits_toNatBits z @[inline] def Yz (w:δ):ٴ:= if η w then -((ε w<<<γ w:ٳ):ٴ) else ((ε w<<<γ w:ٳ):ٴ) lemma ZbT (w:δ):Yz w=sv w*2^γ w:=by unfold Yz sv;split<;>simp[Α] lemma Zx (w:δ):(Ν w).toReal=(Yz w:ℝ)*2^(-149:ٴ):=by rw[<-BC,ϙ,ZbT];push_cast;rw[zpow_sub₀ two_ne_zero,ؠ];ring lemma ZH (w:ؼ):(θ w)؎=w؎/2^23%256:=by simp only[θ,AH,Ϣ,ψ];exact ϡ _ 8 lemma ZR (w:ؼ):(fracOf w)؎=w؎%2^23:=ϡ _ 23 @[inline] def Yac (w:δ):ٴ:=let m:ٴ:=(wپ%2147483648:ٳ);if η w then -m else m def mg (n:ٳ):ٳ:=if n/2^23%256=0 then n%2^23 else (2^23+n%2^23)*2^(n/2^23%256-1) lemma K1 (w:δ):ε w<<<γ w=mg w؎:=by unfold ε γ mg;simp only[<-ύ,UInt32.toNat_zero,ZH,ZR,Α];split<;>simp lemma ZS (a b:ٳ) (h:a%2^31nlinarith[BE (n:=A-1)] lemma ZbU (a b:δ):compare (Yac a) (Yac b)=compare (Yz a) (Yz b):=by have e:∀a b:ٳ,a%2^31=b%2^31->mg a=mg b:=λ a b h=>by unfold mg;rw[show a/2^23%256=b/2^23%256 by omega,show a%2^23=b%2^23 by omega] have:=ZS a؎ b؎;have:=ZS b؎ a؎;have:=e a؎ b؎;have:=ZS 0 b؎;have:=e b؎ 0;have:mg 0=0:=rfl;unfold Yac Yz;rw[K1,K1];simp only[compare,compareOfLessAndEq,DU]at*;generalize a؎%2147483648=A at*;generalize b؎%2147483648=B at*;split_ifs<;>first|rfl|omega lemma ZbV (a:δ) (b:θ a≠255):ι a=(if Cm (ι a)&&Cm (ι a) then Cs κ (BS (ι a)&&BS (ι a)) else ι a):=by simp only[DW];split . rename_i d;obtain⟨e,f⟩:=(Model.isZero_iff_fields_of_isFinite (by simp[ι,isFinite_ofUInt32,b])).1 d;conv_lhs=>rw[<-Model.ofFields_signBit_expField_fracField (ι a),e,f] cases BS (ι a)<;>decide . rfl @[inline] def YQ (a b:δ):δ:= if θ a=255\/θ b=255 then π (CO (ι a) (ι b)) else match compare (Yac a) (Yac b) with | .lt=>b | .gt=>a | .eq=>if a=b then a else π (if Cm (ι a)&&Cm (ι b) then Cs κ (BS (ι a)&&BS (ι b)) else ι a) lemma ZbW (a b:δ):Model.cmpDyadic (Ν a) (Ν b)=compare (Yz a) (Yz b):=by have d:(0:ℝ)<2^(-149:ٴ):=zpow_pos two_pos _;cases h:compare (Yz a) (Yz b);rw[Model.cmpDyadic_lt_iff,Zx,Zx];exact mul_lt_mul_of_pos_right (by exact_mod_cast compare_lt_iff_lt.mp h) d;rw[Model.cmpDyadic_eq_iff,Zx,Zx,compare_eq_iff_eq.mp h];rw[Model.cmpDyadic_gt_iff,Zx,Zx];exact mul_lt_mul_of_pos_right (by exact_mod_cast compare_gt_iff_gt.mp h) d lemma ZbX (a b:δ):ι (YQ a b)=CO (ι a) (ι b):=by unfold YQ;split;exact P9 _;rename_i d;rw[ZbU];have e:=Ϡ a (d∘Ea);have f:=Ϡ b (d∘EY);have g:Model.compare (ι a) (ι b)=some _:=Model.compare_eq_some_cmpDyadic_of_toDyadic? _ _ e f;rw[ZbW]at g;unfold CO;rw[Model.withNaNSelection_of_none _ _ ((Model.chooseNaN2_eq_none_iff _ _).2 ⟨AX e,AX f⟩:Model.chooseNaN2 (ι a) (ι b)=none),Model.compareNonNaN_eq_of_compare_eq_some _ _ _ _ g];cases compare (Yz a) (Yz b)<;>simp only[P9,apply_ite ofW];by_cases h:a=b;subst h;rw[if_pos rfl];exact ZbV a (d∘Ea);rw[if_neg h] def Yad (c h w k:ٳ) (inp:ؽ δ):ؽ δ:= AF (n:=c*(h/k*(w/k))) λ q => let ch:=q.val/(h/k*(w/k));let y:=q.val/(w/k)%(h/k);let x:=q.val%(w/k);(ϒ (k*k)).foldl (λ acc t=>YQ acc (poolAt h w k inp ch y x t)) (poolAt h w k inp ch y x 0) lemma ZbY (p:ٳ -> δ) (l:List ٳ) (b:δ):l.foldl (λ m t=>CO m (ι (p t))) (ι b)=ι (l.foldl (λ a t=>YQ a (p t)) b):=by induction l generalizing b;rfl;next t l d=>simp only[AO,<-ZbX,d] lemma P8:Yad=maxpoolSpec:=by funext c h w k a;simp only[Yad,maxpoolSpec,ZbY,Q0] def kernels0:Kernels where core:=⟨YaN,YaM⟩ dense:=⟨linearWith Yn,gemmWith Yn⟩ conv:=⟨conv2dWith Yn,depthwiseWith Yn⟩ elem:=⟨avgpoolWith Yn,Yad,addReluSpec,scaleShiftSpec⟩ norm:=⟨rmsnormWith Yn,layernormWith Yn⟩ lemma ZbZ:Obligation kernels0:=by simp only[Obligation,kernels0,specKernels,specCore,specDense,specConv,specElem,specNorm,linearSpec,gemmSpec,conv2dSpec,depthwiseSpec,avgpoolSpec,rmsnormSpec,layernormSpec,P8,Zi,funext ZbS,funext λ a=>funext (ZbR a)] def Yo (fa fb:ٳ -> ؼ) (i:ٳ):ٳ -> ٴ | 0=>0 | r+1=>sv (fa i)*sv (fb i)*2^(γ (fa i)+γ (fb i))+Yo fa fb (i+1) r def Yq (fa fb:ٳ -> ؼ) (i:ٳ):ٳ -> ف | 0=>true | r+1=>(decide (ε (fa i)*ε (fb i)=0)&&Ζ (η (fa i)) (η (fb i))) && Yq fa fb (i+1) r lemma Zb0 (n:ٳ) (a b:ٳ -> ؼ) (i r:ٳ) (h:i+r<=n):dsum (ڀ n λ k=>a k܂) (ڀ n λ k=>b k܂) i r=Yo a b i r:=by induction r generalizing i;rfl;next r d=>rw[dsum,Yo,Ze n a i א,Ze n b i א,d (i+1) א] lemma Zb1 (n:ٳ) (a b:ٳ -> ؼ) (i r:ٳ) (h:i+r<=n):dallNZ (ڀ n λ k=>a k܂) (ڀ n λ k=>b k܂) i r=Yq a b i r:=by induction r generalizing i;rfl;next r d=>rw[dallNZ,Yq,Ze n a i א,Ze n b i א,d (i+1) א] lemma Zb2 (f g:ٳ -> ؼ) (d e:ؽ ٳ) (j:ف) (a b:ٳ) (l:∀ k,a<=k -> k < a+b -> θ (f k)≠255/\θ (g k)≠255) : (Yw f g d e false j a b).special=false:=by induction b generalizing d e j a ·rfl rename_i t;rw[Yw];have n:=l a le_rfl א;have o:(Yy ⟨d,e,false,j⟩ (f a) (g a)).special=false:=by have u:¬(θ (f a)=255\/θ (g a)=255):=not_or.2 n;unfold Yy Acc.add;split_ifs<;>rfl generalize Yy ⟨d,e,false,j⟩ (f a) (g a)=r at o⊢;obtain⟨p,q,s,z⟩:=r;subst o;exact t _ _ _ _ (λ k v w=>l k א א) lemma Zy (n:ٳ) (a b:ٳ -> ؼ) (d:∀ k,k θ (a k)≠255/\θ (b k)≠255) : Γ n a b=ρ (Yo a b 0 n) (-298) (decide (n≠0)&&Yq a b 0 n):=by rw[<-Zi];unfold Yn;set A:=ڀ n λ i=>a i܂;set B:=ڀ n λ i=>b i܂;set e:=Yw a b (Χ 18 0) (Χ 18 0) false true 0 n;have f:e.special=false:=Zb2 a b _ _ true 0 n (λ k _ r=>d k א) obtain⟨-,-,g,h⟩:=Q1 a b A B n (Ze n a) (Ze n b) Acc.empty 0 n א rfl rfl f;have j:e.total=Yo a b 0 n:=by simp only[Acc.total_empty,EW]at g;rwa[<-Zb0 n a b 0 n א] have l:e.negZero=Yq a b 0 n:=by rwa[<-Zb1 n a b 0 n א] simp only[f,φ,ש];rw[Q2,show((ϋ e.pos܍:ٴ)-ϋ e.neg܍)=e.total from rfl,j,l] def YC (w2 w1 w0:ػ):ٴ:= ((w2پ*2^128+w1پ*2^64+w0پ:ٳ):ٴ) - (if w2پ<2^63 then 0 else 2^192) lemma Zb3 (s:ف) (E F:ٳ) (b:E<256) (a:F<2^23):(EH κ s E F).toNatBits=(if s then 2^31 else 0)+E*2^23+F:=by rw[Model.ofFields_eq_ofFieldsImpl];simp only[Model.ofFieldsImpl,Model.mkBitsImpl,EQ,Dn,BitVec.toNat_ofNatLT];have d:E&&&κ.expAllOnesNat=E:=Bx (n:=8) b;have e:F&&&κ.fracMaskNat=F:=Bx (n:=23) a;rw[d,e,show E.shiftLeft κ߷=E<<<23 from rfl,Nat.or_assoc,<-Bq a];have f:E<<<23+F<2^31:=א;cases s . simp[Α] . simp only[ר];rw[show Nat.shiftLeft 1 (κ.expWidth+κ߷)=1<<<31 from rfl,<-Bq f];simp;omega @[inline] def Yv (neg:ف) (E F:ؼ):ؼ:=(if neg then (߾:ؼ) else 0)+(E<<<23)+F lemma ZT (a:ف) (E F:ؼ) (b:E؎<256) (d:F؎<2^23):Yv a E F=π (EH κ a E؎ F؎):=by unfold π;rw[Zb3 a _ _ b d];apply ύ.1;unfold Yv;cases a<;>simp<;>omega lemma P7 (a:ف):Yv a 255 0=π (DE κ a):=by rw[Model.nativeOverflow_eq_signedInf_of_isIEEE Fmt ד];cases a<;>decide lemma Zb4 (a:ف):Yv a 0 0=π (Cs κ a):=by cases a<;>decide @[inline] def YH (x r d:ػ):ػ:=if x>>>(r+d) != 0 then r+d else r @[inline] def Yj (x:ػ):ػ:= YH x (YH x (YH x (YH x (YH x (YH x 0 32) 16) 8) 4) 2) 1 lemma Zz (x r d:ػ) (D:ٳ) (a:d˧=D) (f:1<=D) (g:r˧+2*D<=64) (b:2^r˧<=x˧) (e:x˧<2^(r˧+2*D)) : (YH x r d)˧+D<=64/\2^(YH x r d)˧<=x˧ /\ x˧<2^((YH x r d)˧+D):=by subst a;have k:(r+d)˧=r˧+d˧:=by rw[ξ];omega have l:(x>>>(r+d))˧=x˧/2^(r˧+d˧):=by rw[Ξ,k,ν א,ψ] unfold YH;by_cases j:x>>>(r+d) !=0;simp only[j,ר,k];have:x˧/2^(r˧+d˧)≠0:=(by intro h;apply(bne_iff_ne.mp j);apply σ.mp;rw[l,h];rfl);exact⟨א,(Am (Δ _)).mp (Dd.mpr this)|>.trans' ג,by rwa[(א:r˧+d˧+d˧=r˧+2*d˧)]⟩;simp only[j,ש,φ];have n:x>>>(r+d)=0:=ז;have:x˧/2^(r˧+d˧)=0:=by rw[<-l,n];rfl exact⟨א,b,(Nat.div_eq_zero_iff_lt (Δ _)).mp this⟩ lemma Zj (x:ػ) (a:x≠0):(Yj x)˧=x˧܀:=by have b:1<=x˧:=Dd.mpr λh=>a (σ.mp (by simpa using h));have d:=x܉;obtain⟨t,e,f⟩:=Zz x 0 32 32 rfl ד ד (by simpa using b) (by simpa using d);obtain⟨u,g,j⟩:=Zz x _ 16 16 rfl ד א e (by simpa using f);obtain⟨v,k,l⟩:=Zz x _ 8 8 rfl ד א g (by simpa using j);obtain⟨w,n,o⟩:=Zz x _ 4 4 rfl ד א k (by simpa using l);obtain⟨y,p,q⟩:=Zz x _ 2 2 rfl ד א n (by simpa using o);obtain⟨z,r,s⟩:=Zz x _ 1 1 rfl ד א p (by simpa using q);exact((Af א).mpr ⟨r,s⟩).symm @[inline] def Ybm (m:ػ) (e:ٴ):ػ:= match e+149 with | .ofNat k=>m<<Bm m (k+1) @[inline] def YaO (neg:ف) (m:ػ) (e:ٴ):ؼ:= let fr:=Ybm m e;if fr==0 then Yv neg 0 0 else if (0x800000:ػ)<=fr then Yv neg 1 0 else Yv neg 0 fr.toUInt32 lemma Zb5 (a:ف) (m:ػ) (e:ٴ) (b:m˧≠0) (h:(m˧܀:ٴ)+e < -126) : YaO a m e=π (Bv κ a (Cs κ a) (match e-ض with | BG shift=>m˧<<AQ m˧ (shift+1))):=by rw[show ض= -149 from rfl,Int.sub_neg];unfold YaO Ybm;generalize l:e+149=s;suffices H:∀(d:ػ) F,d˧=F→F<=2^23→(if d==0 then Yv a 0 0 else if 0x800000<=d then Yv a 1 0 else Yv a 0 d՜)=π (Bv κ a (Cs κ a) F) by rcases s with k|k ·simp at l;have o:m˧*2^k<2^23:=(Aj (Ak (n:=m˧)) (Δ k)).trans_le (by rw[<-Κ];exact Ι א א);exact H _ (m˧<<g (σ.mp h),ש];by_cases f:0x800000<=d . simp only[f,ר,show d˧>=Ct Fmt߷from f];exact ZT a 1 0 ד ד . simp only[f,ש,show¬d˧>=Ct Fmt߷from f];have j:d՜؎=d˧:=ν א;exact j▸ZT a 0 _ ד (by rw[j];exact Nat.lt_of_not_le f) @[inline] def YK (m L:ػ):ػ:= if 23<=L then Bm m (L-23).toNat else m<<<(23-L) @[inline] def Yae (neg:ف) (m L:ػ) (t:ٴ):ؼ:= let rm:=YK m L;if rm==0x1000000 then (if t+1>127 then Yv neg 255 0 else Yv neg (t+128).toNat.toUInt32 0) else Yv neg (t+127).toNat.toUInt32 (rm.toUInt32-0x800000) lemma Z7 (m:ػ) (a:m≠0):(YK m (Yj m))˧=(if κ߷<=m˧܀ then AQ m˧ (m˧܀-κ߷) else m˧<<<(κ߷-m˧܀)) /\ 2^23<=(YK m (Yj m))˧/\(YK m (Yj m))˧<=2^24:=by have k:m˧≠0:=λh=>a (σ.mp (by simpa using h));have b:=Zj m a;have f:=ϰ k;have g:m˧<2^(m˧܀+1):=Ak;rw[show κ߷=23 from rfl];unfold YK;generalize Yj m=L at b⊢;generalize q:m˧܀=N at*;by_cases h:23<=N have d:(23:ػ)<=L:=by rw[ϐ,b];exact h simp only[d,ר,h,(ח:(L-23)˧=N-23),Bg];exact⟨trivial,(by rw[Am (Δ _),<-Κ,Ej h];exact f:2^23<=m˧/2^(N-23)).trans (Cq _ _),(Bn _ _).trans (by rw[An (Δ _),<-Κ,(by clear*-h;omega:24+(N-23)=N+1)];exact g:m˧/2^(N-23)<2^24)⟩;simp only[(by rw[ϐ,b];exact h:¬(23:ػ)<=L),ש,h];have j:m˧*2^(23-N)<2^24:=(Aj g (Δ _)).trans_eq (by rw[<-Κ];congr 1;clear*-h;omega) rw[(by rw[ό,(by rw[Η _ _ (by rw[ϐ,b];exact Ev h),b];rfl:(23-L)˧=23-N),ν (Ρ (EI 23 N) ד),Α];exact ν (j.trans ד):(m<<<(23-L))˧=m˧*2^(23-N)),Α];exact⟨rfl,(by rw[<-Κ,Ej (Ev h)]:2^23=2^N*2^(23-N)).trans_le (ω _ f),j.le⟩ lemma K3 (n:ٳ) (h:n<2^32):n.toUInt32؎=n:=by rw[Cd,AL,ν h] lemma Zb6 (a:ف) (m:ػ) (e:ٴ) (b:m≠0) (d:¬ ((m˧܀:ٴ)+e>127)) (f:¬ ((m˧܀:ٴ)+e < -126)) : Yae a m (Yj m) ((m˧܀:ٴ)+e)=π (CS κ a (DE κ a) (↑m˧܀+e) (if κ߷<=m˧܀ then AQ m˧ (m˧܀-κ߷) else m˧<<<(κ߷-m˧܀))):=by obtain⟨q,r,s⟩:=Z7 m b;rw[<-q];unfold Yae CS;generalize YK m (Yj m)=g at r s⊢;generalize (m˧܀:ٴ)+e=t at d f⊢;simp only[Model.pow2_eq_two_pow,show κ߷=23 from rfl,show κ.maxNormalExponent=127 from rfl,show κ.exponentBias=127 from rfl,show κ.maxFiniteExpField=254 from rfl,show κ.maxFiniteFracField=8388607 from rfl,DU,Nat.reduceAdd,DK,DF];by_cases k:g˧=ނ . have l:(g==0x1000000)=true:=beq_iff_eq.2 (σ.1 k);simp only[l,ר,k,BEq.rfl];by_cases o:t+1>127 . simp only[o];exact P7 a . simp only[o,ש];have j:((t+128)׆.toUInt32)؎=(t+1+127)׆:=by rw[K3 (t+128)׆ א];omega rw[if_neg ז];rw[ZT a _ 0 (by rw[j];omega) ד,j];rfl . have l:(g==0x1000000)=false:=beq_eq_false_iff_ne.2 λ h=>k (by rw[h];rfl) have u:(g˧==ނ)=false:=ז;simp only[l,u,φ,ש,(א:¬t>127)];have j:=K3 (t+127)׆ א;have p:(g՜-0x800000)؎=g˧-ރ:=by rw[Dj _ _ (by rw[AJ];simp;omega)];simp;omega rw[if_neg ז];rw[ZT a _ _ (by rw[j];omega) (by rw[p];omega),j,p] @[inline] def YA (neg:ف) (m:ػ) (e:ٴ):ؼ:= let L:=Yj m;let t:ٴ:=(Lپ:ٴ)+e;if t>127 then Yv neg 255 0 else if t < -126 then YaO neg m e else Yae neg m L t lemma ZU (a:ف) (m:ػ) (e:ٴ) (b:m≠0):YA a m e=π (AT κ ⟨a,m˧,e⟩):=by have g:m˧≠0:=λh=>b (σ.mp (by simpa using h));have j:=Zj m b;unfold YA AT;simp only[show(m˧==0)=false by simpa using g,φ,ש,j,show κ.maxNormalExponent=127 from rfl,show κ.minNormalExponent= -126 from rfl];by_cases f:(m˧܀:ٴ)+e>127;simp only[f,ר];exact P7 a;simp only[f,ש];by_cases d:(m˧܀:ٴ)+e< -126;simp only[d,ר];exact Zb5 a m e g d;simp only[d,ש];exact Zb6 a m e b f d @[noinline] def Ybn (neg:ف) (m:ػ) (e:ٴ):ؼ:=YA neg m e @[noinline] def Yat (neg:ف) (m:ػ) (e:ٴ) (L c:ػ):ؼ:= YA neg m (e+((Lپ+cپ:ٳ):ٴ)) @[inline] def YY (n:ػ):ػ:= let q:=n>>>40;q+(((n&&&0xFFFFFFFFFF)+0x7FFFFFFFFF+(q&&&1))>>>40) lemma Zb7 (n:ػ):(YY n)˧=AQ n˧ 40:=by rw[Cl _ _ ד];have b:(n>>>40)˧=n˧/2^40:=by rw[Ξ,ψ];rfl have d:(n&&&0xFFFFFFFFFF)˧=n˧%2^40:=by rw[BR,show(0xFFFFFFFFFF:ػ)˧=2^40-1 from rfl,ϡ] have e:((n>>>40)&&&1)˧=n˧/2^40%2:=ח;have f:n˧/2^(40-1)%2=n˧%2^40/2^39:=by rw[(ב:(2:ٳ)^40=2^39*2),Cw] have g:n˧%2^(40-1)=n˧%2^40%2^39:=by rw[(ב:(2:ٳ)^40=2^39*2),Nat.mod_mul_right_mod] have k:=Ε n˧ (Δ 40);have l:n˧/2^40<2^24:=(An ד).2 n܉ unfold YY;simp only[ξ,Ξ,d,e,BJ,f,g];clear b d e f g;generalize n˧%2^40=R at*;simp only[Bc,ψ]at*;split<;>rename_i h<;>simp at h<;>generalize n˧/1099511627776=Q at*<;>rw[ν (a:=R+549755813887) א,ν (a:=R+549755813887+Q%2) א]<;>[rw[(א:(R+549755813887+Q%2)/1099511627776=1)];rw[(א:(R+549755813887+Q%2)/1099511627776=0)]]<;>exact ν א lemma Z8 (a:ف) (E F:ؼ) (h:E؎*2^23+F؎<2^31):(Yv a E F)؎=(if a then 2^31 else 0)+E؎*2^23+F؎:=by unfold Yv;cases a<;>simp<;>omega @[inline] def YZ (neg:ف) (u n:ػ):ؼ:= (if neg then (߾:ؼ) else 0)+((u<<<23)+YY n).toUInt32 lemma Zb8 (a:ف) (u n:ػ) (b:u˧<=253) (d:(YY n)˧<=2^24):(YZ a u n)؎=(if a then 2^31 else 0)+u˧*2^23+(YY n)˧:=by have e:(u<<<23)˧=u˧*2^23:=by rw[ό];simp;omega unfold YZ;cases a<;>simp<;>omega lemma P6 (a:ف) (m:ػ) (e:ٴ) (u:ػ) (b:m≠0) (d:(u˧:ٴ)=(m˧܀:ٴ)+e+126) (f:u˧<=253) : YZ a u (m<<<(63-Yj m))=YA a m e:=by have k:=Zj m b;obtain⟨o,p,q⟩:=Z7 m b;have j:m˧܀<64:=(Ϻ λh=>b (σ.mp h)).mpr m܉;have l:(YY (m<<<(63-Yj m)))˧=(YK m (Yj m))˧:=by rw[Zb7,o,(by rw[ό,(by rw[Τ,k];simp;clear*-j;omega:(63-Yj m)˧=63-m˧܀),ν (by clear*-;omega:63-m˧܀<64),Α];exact ν ((Aj Ak (Δ _)).trans_eq (by rw[<-Κ,(by clear*-j;omega:m˧܀+1+(63-m˧܀)=64)])):(m<<<(63-Yj m))˧=m˧*2^(63-m˧܀)),show κ߷=23 from rfl];split<;>rename_i g;rw[(by clear*-g j;omega:(40:ٳ)=m˧܀-23+(63-m˧܀)),CE];rw[Cc _ _ _ (by clear*-g j;omega),Α,(by clear*-;omega:63-m˧܀-40=23-m˧܀)] simp only[YA,k,show¬(m˧܀+e>127)by clear*-d f;omega,show¬(m˧܀+e< -126)by clear*-d f;omega,ש];apply ύ.mp;rw[Zb8 a u _ f (by clear*-l p q;omega),l];unfold Yae;generalize YK m (Yj m)=n at l p q⊢;generalize (m˧܀:ٴ)+e=t at d⊢;clear b k o j;by_cases g:n˧=ނ;simp only[show(n==0x1000000)=true by simp[<-σ,g],ר];by_cases v:t+1>127<;>simp only[v,ר,ש]<;>rw[Z8 a _ _ (by simp<;>omega)]<;>simp<;>omega;simp only[show(n==0x1000000)=false by simp[<-σ,g],φ,ש];rw[Z8 a _ _ (by simp[CX];omega)];simp[CX];omega lemma P5 (a:ف) (n:ػ) (E:ٴ) (u:ػ) (b:2^63<=n˧) (e:(u˧:ٴ)=E+189) (d:u˧<=253) : YZ a u n=YA a n E:=by have f:=Nat.pos_iff_ne_zero.mp (Ag (Δ 63) b);have g:n≠0:=λ h=>f (by rw[h];rfl);have j:n˧܀=63:=(Af f).mpr ⟨b,n܉⟩;have k:Yj n=63:=σ.mp (by rw[Zj n g,j];rfl);have:=P6 a n E u g (by rw[j];push_cast;omega) d;rw[k,show n<<<(63-63:ػ)=n from σ.mp (by rw[ό];simp only[UInt64.reduceSub];exact ν n܉)]at this exact this lemma Zb9 (e:ٴ) (c:ػ) (b:c˧<2^62) (h:(ϱ e).toInt=e) (a:((ϱ e).toUInt64+c)˧<=253) : (((ϱ e).toUInt64+c)˧:ٴ)=e+c˧:=by have d:=Int64.toInt_lt (ϱ e);have f:=Int64.le_toInt (ϱ e);have g:((ϱ e).toUInt64˧:ٴ)=e%2^64:=by simp;exact Cj (Int.emod_nonneg _ ד) rw[ξ]at a⊢;omega def Y0 (e:ٴ) (ok:ف) (B:ػ):Prop:= ∀ c:ػ,cپ<2^62 -> ok=true -> (B+c).toNat<=253 -> ((B+c).toNat:ٴ)=e+cپ lemma P4 (e:ٴ):Y0 e ((ϱ e).toInt==e) (ϱ e).toUInt64:=λ c a b d=>Zb9 e c a (beq_iff_eq.1 b) d @[inline] def Yau (neg:ف) (m:ػ) (e:ٴ) (ok:ف) (b:ػ):ؼ:= let L:=Yj m;let u:=b+L+126;if ok&&u<=253 then YZ neg u (m<<<(63-L)) else Ybn neg m e lemma P3 (a:ف) (m:ػ) (e:ٴ) (d:ف) (B:ػ) (b:m≠0) (f:Y0 e d B):Yau a m e d B=YA a m e:=by have k:m˧≠0:=λ h=>b (σ.mp (by simpa using h));have l:=Zj m b;have q:=(Ϻ k).mpr m܉;unfold Yau Ybn;dsimp only;split;swap;rfl rename_i h;simp at h;obtain⟨n,g⟩:=h;have o:(Yj m+126)˧=m˧܀+126:=by rw[ξ,l];simp;omega rw[CY]at g⊢;have j:(B+(Yj m+126))˧<=253:=by simpa using ϐ.mp g have p:=f _ (by rw[o];omega) n j;exact P6 a m e _ b (by rw[p];omega) j lemma Zcb (V s:ٳ) (h:s+25<=V܀):(AR V s)܀=V܀-s:=by have d:V≠0:=by intro e;subst e;simp at h have f:=ϰ d;have g:V<2^(V܀+1):=Ak;have a:2^(V܀-s)<=V/2^s:=by rw[Am (Δ _),<-Κ,(א:V܀-s+s=V܀)];exact f have b:V/2^s<2^(V܀-s+1):=by rw[An (Δ _),<-Κ,(א:V܀-s+1+s=V܀+1)];exact g unfold AR;simp only;split . exact(Af א).mpr ⟨a,b⟩ . rw[Bu];split . rename_i _ j;apply(Af א).mpr;omega . exact(Af א).mpr ⟨a,b⟩ lemma P0 (b:ف) (V s:ٳ) (e:ٴ) (h:s+25<=V܀):AT κ ⟨b,AR V s,e+s⟩=AT κ ⟨b,V,e⟩:=by have d:V≠0:=by intro j;subst j;simp at h have k:2^s<=V:=Cp (Ι ב א) (ϰ d);have l:=DC V s k;have n:=Zcb V s h;unfold AT;simp only[show(AR V s==0)=false by simpa using l,show(V==0)=false by simpa using d,φ,ש,n];rw[(א:((V܀-s:ٳ):ٴ)+(e+s)=V܀+e)];split;rfl;split;rename_i _ f;have t:ض= -149:=rfl;have u:(V܀:ٴ)+e< -126:=lt_of_lt_of_eq f rfl;obtain⟨a,g⟩:∃a:ٳ,e-ض=CJ a/\s+2<=a+1:=by refine⟨(-(e+149)-1)׆,?_,א⟩;omega rw[g.1,(א:e+(s:ٴ)-ض=CJ (a-s))];simp only;rw[(א:a-s+1=a+1-s),Bh V s (a+1) g.2];rename_i _ f;have q:κ߷<=V܀-s:=by rw[show κ߷=23 from rfl];omega simp only[q,(א:κ߷<=V܀),ר];rw[show κ߷=23 from rfl,(א:V܀-s-23=V܀-23-s),Bh V s (V܀-23) א] lemma Z9 (b a d:ػ) (L:ٳ) (e:d˧=L) (g:L<=63) (f:b˧<2^(L+1)):((b<<<(63-d))|||((a>>>d)>>>1))˧=(b˧*2^64+a˧)/2^(L+1) /\ ((a<<<(63-d)) != 0)=decide ((b˧*2^64+a˧)%2^(L+1)≠0):=by have j:(63-d)˧=63-L:=by rw[Η _ _ (by rw[ϐ,e];simp;omega),e];rfl have h:(2:ٳ)^64=2^(63-L)*2^(L+1):=by rw[<-Κ];congr 1;omega refine⟨by rw[Du,(by rw[ό,j,ν (א:63-L<64),Α,ν];rw[h,Θ (2^_)];exact Aj f (Δ _):(b<<<(63-d))˧=b˧*2^(63-L)),(by rw[Ξ,Ξ,e,ν (א:L<64)];simp only[Bc,BY,ψ,ϧ,<-Nat.pow_succ]:((a>>>d)>>>1)˧=a˧/2^(L+1)),(by rw[h,<-ϣ,Ϟ,ϔ _ _ (Δ _),Ϟ]:(b˧*2^64+a˧)/2^(L+1)=b˧*2^(63-L)+a˧/2^(L+1)),<-Α,<-Bq (by rw[An (Δ _),<-h];exact a܉:a˧/2^(L+1)<2^(63-L))],?_⟩;rw[h,<-ϣ,Nat.mul_add_mod_self_right,AB];simp[<-σ,(by rw[ό,j,ν (א:63-L<64),Α,h,Θ (2^(63-L)),Nat.mul_mod_mul_right]:(a<<<(63-d))˧=a˧%2^(L+1)*2^(63-L))] @[inline] def Yav (w0:ػ):ػ:= ~~~w0+1 @[inline] def Yaw (w1 w0:ػ):ػ:= ~~~w1+(if w0==0 then 1 else 0) @[inline] def Yax (w2 w1 w0:ػ):ػ:= ~~~w2+(if w1==0&&w0==0 then 1 else 0) lemma Zcc (d b a:ػ) (h:d˧*2^128+b˧*2^64+a˧≠0):(Yax d b a)˧*2^128+(Yaw b a)˧*2^64+(Yav a)˧=2^192-(d˧*2^128+b˧*2^64+a˧):=by have n:=d܉;have o:=b܉;have p:=a܉;unfold Yax Yaw Yav;by_cases e:a=0;have f:a˧=0:=ח;by_cases l:b=0;have g:b˧=0:=ז;simp only[e,l,DW]at*;simp at*;omega;have j:(b==0)=false:=ז;have g:b˧≠0:=λh=>l (σ.mp (by rw[h];rfl));simp only[e,j,beq_self_eq_true,Bool.false_and,φ,ש,ר,ξ,CZ]at*;simp at*;omega;have k:(a==0)=false:=ז;have f:a˧≠0:=λh=>e (σ.mp (by rw[h];rfl));simp only[k,EL,φ,ש,ξ,CZ]at*;simp at*;omega @[inline] def Yaf (neg:ف) (m2 m1 m0:ػ) (e:ٴ):ؼ:= let L:=Yj m2;let x:=(m2<<<(63-L))|||((m1>>>L)>>>1);let st:=(m1<<<(63-L)) != 0||m0 != 0;YA neg (if st then x|||1 else x) (e+((Lپ+65:ٳ):ٴ)) @[inline] def Yag (neg:ف) (m1 m0:ػ) (e:ٴ):ؼ:= let L:=Yj m1;let x:=(m1<<<(63-L))|||((m0>>>L)>>>1);let st:=(m0<<<(63-L)) != 0;YA neg (if st then x|||1 else x) (e+((Lپ+1:ٳ):ٴ)) @[inline] def Yay (neg:ف) (m2 m1 m0:ػ) (e:ٴ):ؼ:= if m2 != 0 then Yaf neg m2 m1 m0 e else if m1 != 0 then Yag neg m1 m0 e else YA neg m0 e lemma O9 (x:ػ) (a:ف) (Q R:ٳ) (b:x˧=Q) (d:a=decide (R≠0)) (e:2<=Q):(if a then x|||1 else x)˧=(if R==0 then Q else Q|||1):=by subst b d;by_cases f:R=0;simp[f];simp[f] lemma QF (m:ػ) (h:m≠0):m˧܀<=63/\m˧<2^(m˧܀+1)/\2^m˧܀<=m˧:=by have a:m˧≠0:=λ b=>h (σ.1 b);exact⟨CI ((Ϻ a).2 m܉),Ak,ϰ a⟩ lemma QH (m r K:ٳ) (a:2^K<=m):2<=(m*2^64+r)/2^(K+1):=by rw[Am (Δ _)];calc 2*2^(K+1)=2^K*2^2:=by rw[<-Κ,<-Nat.pow_succ'] _<=m*2^64:=Ar a (Ι ב ב) _<=_:=ώ _ _ lemma QL (m:ػ) (s r:ٳ) (h:m≠0) (a:r<2^s):(m˧*2^s+r)܀=s+m˧܀:=by have b:m˧≠0:=λ d=>h (σ.mp (by rw[d];rfl)) have e:=@Ak m˧;apply(Af (Nat.ne_of_gt (Ag (ϊ (Ο b) (Δ s)) (ώ _ _)))).mpr;constructor . rw[Κ,Θ];exact(ω _ (ϰ b)).trans (ώ _ _) . calc m˧*2^s+r<(m˧+1)*2^s:=by rw[Dp];omega _<=2^(m˧܀+1)*2^s:=ω _ e _=2^(s+m˧܀+1):=by rw[<-Κ];ring_nf lemma QN (x:ػ) (a:ف) (Q R:ٳ) (b:(if a then x|||1 else x)˧=(if R==0 then Q else Q|||1)) (d:2<=Q):(if a then x|||1 else x)≠0:=by intro h;have e:=congrArg Er h;rw[b,Ϝ]at e;split at e;omega;rw[Bu]at e;split at e<;>omega lemma Zcd (b:ف) (a d:ػ) (e:ٴ) (f:a≠0):Yag b a d e=π (AT κ ⟨b,a˧*2^64+d˧,e⟩):=by have s:=a܉;have p:=d܉;unfold Yag;have c:=Zj a f;obtain⟨g,h,j⟩:=QF a f;generalize q:a˧܀=K at c g h j;obtain⟨k,l⟩:=Z9 a d (Yj a) K c g h;generalize Yj a=L at c k l⊢;have n:=QH _ d˧ K j;have o:=O9 _ _ _ _ k l n;rw[ZU _ _ _ (QN _ _ _ _ o n),o,c];have r:=QL a 64 _ f p;rw[q]at r;have:=P0 b (a˧*2^64+d˧) (K+1) e א;unfold AR at this;rw[this] lemma Zce (f:ف) (a d b:ػ) (e:ٴ) (g:a≠0):Yaf f a d b e=π (AT κ ⟨f,a˧*2^128+d˧*2^64+b˧,e⟩):=by have u:=d܉;have v:=b܉;unfold Yaf;have c:=Zj a g;obtain⟨n,o,p⟩:=QF a g;generalize w:a˧܀=K at c n o p;obtain⟨h,k⟩:=Z9 a d (Yj a) K c n o;generalize Yj a=L at c h k ⊢;obtain⟨A,l⟩:∃ A,a˧*2^64+d˧=A:=⟨_,rfl⟩;rw[l]at h k;have x:=(϶ A (2^(K+1))).symm;have y:A%2^(K+1)<2^(K+1):=Ε _ (Δ _);have q:(2:ٳ)^(K+65)=2^(K+1)*2^64:=ז;have r:a˧*2^128+d˧*2^64+b˧=(A%2^(K+1)*2^64+b˧)+A/2^(K+1)*2^(K+65):=by have:a˧*2^128+d˧*2^64=A*2^64:=by rw[<- l];ring rw[this,q];conv_lhs=>rw[x] ring have s:A%2^(K+1)*2^64+b˧<2^(K+65):=by rw[q];exact Ag א (ω _ y) have z:(a˧*2^128+d˧*2^64+b˧)/2^(K+65)=A/2^(K+1):=by rw[r,ϔ _ _ (Δ _),Υ s,Β] have B:(a˧*2^128+d˧*2^64+b˧)%2^(K+65)=A%2^(K+1)*2^64+b˧:=by rw[r,ϲ,ν s] have C:((d<<<(63-L) != 0)||(b != 0))=decide ((a˧*2^128+d˧*2^64+b˧)%2^(K+65)≠0):=by rw[k,B,show(b != 0)=decide (b˧≠0) from AB.2 (by simp[← σ])];simp have j:=QH _ d˧ K p;rw[l]at j;rw[<- z]at h j;have t:=O9 _ _ _ _ h C j;rw[ZU _ _ _ (QN _ _ _ _ t j),t,c];have D:=QL a 128 (d˧*2^64+b˧) g (by clear * - v u;omega);rw[<- BU,w]at D;have:=P0 f (a˧*2^128+d˧*2^64+b˧) (K+65) e א;unfold AR at this;rw[this] lemma O8 (a:ف) (d b f:ػ) (e:ٴ) (g:d˧*2^128+b˧*2^64+f˧≠0) : Yay a d b f e=π (AT κ ⟨a,d˧*2^128+b˧*2^64+f˧,e⟩):=by unfold Yay;by_cases j:d=0 . subst j;simp only[Ϝ,ϸ,Β]at g⊢;by_cases k:b=0 . subst k;simp at g⊢;exact ZU a f e (λ h=>g (by rw[h];rfl)) . simp only[show(b !=0)=true by simpa using k,ר];exact Zcd a b f e k . simp only[show(d !=0)=true by simpa using j,ר];exact Zce a d b f e j lemma ZaP (a d b:ػ) (L:ٳ) (f:b˧=L) (g:L<=63) (h:a˧<2^(L+1)) (j:2^L<=a˧) (e:ف) : 2^63<=(if e then ((a<<<(63-b))|||((d>>>b)>>>1))|||1 else (a<<<(63-b))|||((d>>>b)>>>1))˧:=by obtain⟨k,-⟩:=Z9 a d b L f g h;have l:2^63<=(a˧*2^64+d˧)/2^(L+1):=by rw[Am (Δ _)];calc 2^63*2^(L+1)=2^L*2^64:=by rw[<-Κ,<-Κ,(א:63+(L+1)=L+64)] _<=a˧*2^64:=ω _ j _<=_:=ώ _ _ cases e . simp only[φ,ש];rw[k];exact l . simp only[ר];rw[Du,k,show(1:ػ)˧=1 from rfl,Bu];split<;>omega @[inline] def YaR (neg:ف) (m1 m0:ػ) (e:ٴ) (ok:ف) (b:ػ):ؼ:= let L:=Yj m1;let x:=(m1<<<(63-L))|||((m0>>>L)>>>1);let st:=(m0<<<(63-L)) != 0;let x':=if st then x|||1 else x;let u:=b+L+190;if ok&&u<=253 then YZ neg u x' else Yat neg x' e L 1 lemma K5 (a b:ػ) (h:a≠0):(Yj a)˧=a˧܀/\a˧܀<=63/\∀ g:ف,2^63<=(if g then ((a<<<(63-Yj a))|||((b>>>Yj a)>>>1))|||1 else (a<<<(63-Yj a))|||((b>>>Yj a)>>>1))˧:=by have d:a˧≠0:=λ e=>h (σ.1 e);have f:a˧܀<=63:=CI ((Ϻ d).2 a܉);exact⟨Zj a h,f,ZaP a b (Yj a) _ (Zj a h) f Ak (ϰ d)⟩ lemma X9 (a:ف) (b d:ػ) (e:ٴ) (f:ف) (B:ػ) (g:b≠0) (j:Y0 e f B):YaR a b d e f B=Yag a b d e:=by obtain⟨c,o,k⟩:=K5 b d g;generalize b˧܀=K at c o;unfold YaR Yag Yat;dsimp only;generalize Yj b=L at c k⊢;split;rename_i h;simp at h;obtain⟨p,l⟩:=h;have q:(L+190)˧=K+190:=by rw[ξ,c];simp;omega rw[CY]at l⊢;have n:(B+(L+190))˧<=253:=by simpa using ϐ.mp l exact P5 a _ _ _ (k _) (by rw[j _ (by rw[q];omega) p n];push_cast;omega) n;rfl @[inline] def YaS (neg:ف) (m2 m1 m0:ػ) (e:ٴ) (ok:ف) (b:ػ):ؼ:= let L:=Yj m2;let x:=(m2<<<(63-L))|||((m1>>>L)>>>1);let st:=(m1<<<(63-L)) != 0||m0 != 0;let x':=if st then x|||1 else x;let u:=b+L+254;if ok&&u<=253 then YZ neg u x' else Yat neg x' e L 65 lemma X8 (a:ف) (b d f:ػ) (e:ٴ) (g:ف) (B:ػ) (j:b≠0) (k:Y0 e g B):YaS a b d f e g B=Yaf a b d f e:=by obtain⟨c,p,l⟩:=K5 b d j;generalize b˧܀=K at c p;unfold YaS Yaf Yat;dsimp only;generalize Yj b=L at c l⊢;split . rename_i h;simp at h;obtain⟨q,n⟩:=h;have r:(L+254)˧=K+254:=by rw[ξ,c];simp;omega rw[CY]at n⊢;have o:(B+(L+254))˧<=253:=by simpa using ϐ.mp n have s:=k _ (by rw[r];omega) q o;exact P5 a _ _ _ (l _) (by rw[s];push_cast;omega) o . rfl @[inline] def Yaz (neg:ف) (m2 m1 m0:ػ) (e:ٴ) (ok:ف) (b:ػ):ؼ:= if m2 != 0 then YaS neg m2 m1 m0 e ok b else if m1 != 0 then YaR neg m1 m0 e ok b else Yau neg m0 e ok b lemma O7 (a:ف) (d b f:ػ) (e:ٴ) (g:ف) (B:ػ) (k:d˧*2^128+b˧*2^64+f˧≠0) (j:Y0 e g B) : Yaz a d b f e g B=Yay a d b f e:=by unfold Yaz Yay;by_cases l:d=0;subst l;by_cases n:b=0;subst n;exact P3 a f e g B (λh=>k (by rw[h];rfl)) j;simp only[show(b !=0)=true by simpa using n,ר];exact X9 a b f e g B n j;simp only[show(d !=0)=true by simpa using l,ר];exact X8 a d b f e g B l j @[inline] def YaT (w2 w1 w0:ػ) (e:ٴ) (negZero ok:ف) (B:ػ):ؼ:= if w2=0/\w1=0/\w0=0 then (if negZero then ߾ else 0) else if w2>>>63 != 0 then Yaz true (Yax w2 w1 w0) (Yaw w1 w0) (Yav w0) e ok B else Yaz false w2 w1 w0 e ok B lemma L5 (b d f:ػ) (e:ٴ) (a g:ف) (B:ػ) (j:Y0 e g B):YaT b d f e a g B=ρ (YC b d f) e a:=by have o:b˧*2^128+d˧*2^64+f˧<2^192:=by have:=b܉;have:=d܉;have:=f܉;omega unfold YaT;by_cases l:b=0/\d=0/\f=0 . obtain⟨rfl,rfl,rfl⟩:=l;simp[YC,ρ] have k:b˧*2^128+d˧*2^64+f˧≠0:=λ h=>l (by simp only[<-σ,Ϝ];omega) rw[ite_eq_right l];by_cases p:b˧<2^63 . rw[ite_eq_right (by simp[<-σ];omega:¬(b>>>63 !=0)=true),O7 _ _ _ _ _ _ _ k j,O8 _ _ _ _ _ k,AV,<-F9 _ _ _ a k,YC,ite_eq_left p,Int.sub_zero];rfl . generalize q:b˧*2^128+d˧*2^64+f˧=N at o;have n:=Zcc b d f k;rw[q]at n;have r:=n▸Nat.sub_ne_zero_of_lt o;rw[ite_eq_left (by simp[<-σ];omega:(b>>>63 !=0)=true),O7 _ _ _ _ _ _ _ r j,O8 _ _ _ _ _ r,n,AV,<-F9 _ _ _ a א,YC,q,ite_eq_right p,(א:(N:ٴ)-2^192=-((2^192-N:ٳ):ٴ)),ite_eq_left rfl] def Ybo (w2 w1 w0:ػ) (e:ٴ) (negZero:ف):ؼ:= YaT w2 w1 w0 e negZero ((ϱ e).toInt==e) (ϱ e).toUInt64 lemma X7 (b d f:ػ) (e:ٴ) (a:ف):Ybo b d f e a=ρ (YC b d f) e a:= L5 b d f e a _ _ (P4 e) @[inline] def Yf (w:ؼ):ػ:= if θ w=0 then (fracOf w).toUInt64 else (fracOf w).toUInt64+0x800000 @[inline] def Yd (w:ؼ):ػ:= if θ w=0 then 0 else (θ w).toUInt64-1 lemma Zk (w:ؼ):(Yf w)˧=ε w:=by have:=fracOf_toNat_lt w;unfold Yf ε;split_ifs;simp;simp only[ξ];show((fracOf w)؎+ރ)%2^64=2^23+(fracOf w)؎;omega lemma Zf (w:ؼ):(Yd w)˧=γ w:=by unfold Yd γ;split_ifs with h . rfl . have b:1<=(θ w)؎:=by rcases Ae (θ w)؎with a|a . exact absurd (ύ.mp (by simpa using a)) h . exact a rw[Η _ _ (by rw[ϐ];simp;omega)];simp lemma Zc (a b:ؾ) (h:a؛+b؛<Λ):(a+b)؛=a؛+b؛:=ν h lemma A4 (A:ؽ δ) (a n k:ؾ) (b:a؛+n؛<=Aٽ) (d:a؛+n؛<Λ) (h:k>>1)>>>(63-r))˧=m˧/2^(64-r˧):=by rw[Ξ,Ξ,X6 r a,ψ,ψ,ν (Nat.sub_lt_succ 63 _),show(1:ػ)˧%64=1 from rfl,ϧ,<-Κ];congr 2;omega lemma G8 (m r:ٳ) (a:r<64):m*2^r%2^64+m/2^(64-r)*2^64=m*2^r:=by rw[<-show m*2^r/2^64=m/2^(64-r) by rw[show(2:ٳ)^64=2^r*2^(64-r) by rw[<-Κ,Ej a.le],<-ϧ,Nat.mul_div_cancel _ (Δ r)]];exact Nat.mod_add_div' _ _ lemma X5 (m s:ػ) (a:s˧<64):((m>>>1)>>>(63-(s&&&63)))˧*2^64+(m<<<(s&&&63))˧ =m˧*2^s˧:=by have b:(s&&&63)˧=s˧:=by rw[H0];exact ν a rw[C0 _ _ א,G9 _ _ א,b];have:=G8 m˧ s˧ a;omega lemma X4 (m s:ػ) (a:64<=s˧) (b:s˧<128):((m>>>1)>>>(63-(s&&&63)))˧*2^128+(m<<<(s&&&63))˧*2^64 =m˧*2^s˧:=by have d:(s&&&63)˧=s˧-64:=by rw[H0];omega rw[C0 _ _ א,G9 _ _ א,d];have:=G8 m˧ (s˧-64) א;have:m˧*2^s˧=m˧*2^(s˧-64)*2^64:=by rw[ϣ,<-Κ,Aw a] omega lemma X3 (m s:ػ) (a:s˧<128):(if s<64 then (0:ػ) else (m>>>1)>>>(63-(s&&&63)))˧*2^128 + (if s<64 then (m>>>1)>>>(63-(s&&&63)) else m<<<(s&&&63))˧*2^64 + (if s<64 then m<<<(s&&&63) else 0)˧=m˧*2^s˧:=by by_cases h:s<64;rw[if_pos h,if_pos h,if_pos h,Ϝ,ϸ,Β];exact X5 m s (Ψ.1 h);rw[if_neg h,if_neg h,if_neg h,Ϝ,ϑ];exact X4 m s (DZ.1 (Ψ.not.1 h)) a lemma G7 (y a:ػ) (h:a˧<=1):(y^^^(0-a))˧=if a˧=1 then 2^64-1-y˧ else y˧:=by rcases Ay.mp h with b|d;obtain rfl:a=0:=σ.mp (by simpa using b);simp;obtain rfl:a=1:=σ.mp (by simpa using d);show(y.toBitVec^^^BitVec.allOnes 64).toNat=_;rw[BitVec.xor_allOnes,BitVec.toNat_not];simp lemma ZJ (a b:ػ):(a+b)˧=(a˧+b˧)%2^64 /\ (if a+brw[Ψ,d]at h;show 1=_;omega;show 0=_;omega lemma X2 (f a d g b e:ػ):(f+g+((if a+bomega lemma L3 (a b d:ػ):((a|||b|||d)==0)=decide (d˧*2^128+b˧*2^64+a˧=0):=by rw[AB,beq_iff_eq,ة,DA,DA,<-σ,<-σ,<-σ,Ϝ];omega lemma D4 (a b:ؼ):((a^^^b)>>>31)܅˧=if Ζ (η a) (η b) then 1 else 0:=by have d:∀a:ؼ,η a=decide (a؎/2^31=1):=λa=>by have:=a.toNat_lt;unfold η;have j:(a؎&&&2^31)%2^31=0:=by rw[Nat.and_mod_two_pow,Nat.mod_self,Nat.and_zero] have k:(a؎&&&2^31)/2^31=a؎/2^31%2:=by rw[Nat.and_div_two_pow,Nat.div_self (Δ 31),Nat.and_one_is_mod] rw[(by rw[AB,bne_iff_ne,ة,ne_eq,ne_eq,<-ύ];simp:(a&&&߾!=0)=decide ((a&&&߾)؎≠0)),(ג:(a&&&߾)؎=a؎&&&2^31),AB,ة,ة];omega rw[AG,Ϣ,UInt32.toNat_xor,show(31:ؼ)؎%32=31 from rfl,Nat.shiftRight_xor_distrib,ψ,ψ,d,d];have:=a.toNat_lt;have:=b.toNat_lt;rcases Ay.mp (א:aپ/2^31<=1)with h|h<;>rcases Ay.mp (א:bپ/2^31<=1)with e|e<;>rw[h,e]<;>decide @[inline] def YL {β:Type} (lo:ػ) (a b:ؼ) (w2 w1 w0 c:ػ) (kont:ػ -> ػ -> ػ -> ػ -> β):β:= let m:=Yf a*Yf b;let s:=Yd a+Yd b-lo;let rr:=s&&&63;let x0:=m<<>>1)>>>(63-rr);let lowq:=s<64;let y0:=if lowq then x0 else 0;let y1:=if lowq then x1 else x0;let y2:=if lowq then 0 else x1;let ng:=((a^^^b)>>>31).toUInt64;let mk:ػ:=0-ng;let s0:=w0+(y0^^^mk);let k0:ػ:=if s0>>1)>>>(63-(s&&&63)))˧*2^128 + (if s<64 then (m>>>1)>>>(63-(s&&&63)) else m<<<(s&&&63))˧*2^64 + (if s<64 then m<<<(s&&&63) else 0)˧=0:=by have b:m=0:=σ.mp (by simpa using a);subst b;split_ifs<;>simp lemma Zg (w:ؼ):γ w<=254:=by have:=expOf_toNat_lt w;unfold γ;split_ifs<;>omega lemma ZK (a b:ؼ):ε a*ε b<2^48:=calc ε a*ε b<2^24*2^24:=BP (Ϛ a) (Ϛ b) lemma K4 (a b:δ):(Yf a*Yf b)˧=ε a*ε b:=by rw[ϯ,Zk,Zk];exact ν (by have:=ZK a b;omega) lemma B6 (a b:δ):(Yd a+Yd b)˧=γ a+γ b:=by have:=Zg a;have:=Zg b;rw[ξ,Zf,Zf,ν א] lemma E7 (w:δ):(Yf w==0)=decide (ε w=0):=by rw[AB,beq_iff_eq,ة,<-Zk,<-σ];rfl lemma Zr {β:Type} (d:ػ) (a b:ؼ) (f g h c:ػ) (e:ػ -> ػ -> ػ -> ػ -> β) (j:c˧+1<2^64) (k:ε a*ε b≠0 -> d˧<=γ a+γ b/\γ a+γ b>>31)܅˧<=1:=by rw[p];split<;>decide refine⟨_,_,_,_,rfl,?_,?_⟩;all_goals generalize Yf a*Yf b=m,F:Yd a+Yd b-d=s,((a^^^b)>>>31)܅=l at r p n⊢ . rw[ξ];exact(DY _ _).trans (Ϯ n _) have o:(if s<64 then (0:ػ)else (m>>>1)>>>(63-(s&&&63)))˧*2^128+(if s<64 then (m>>>1)>>>(63-(s&&&63))else m<<<(s&&&63))˧*2^64+(if s<64 then m<<<(s&&&63)else 0)˧=ε a*ε b*2^(γ a+γ b-d˧):=by by_cases t:ε a*ε b=0;rw[t,ϸ];exact X0 m s (by rw[r,t]);obtain⟨A,G⟩:=k t;have B:s˧=γ a+γ b-d˧:=(by rw[<-F,Η _ _ (by rwa[ϐ,B6]),B6]);rw[<-r,<-B];exact X3 m s (B▸Bz A G) generalize (if s<64 then (0:ػ)else (m>>>1)>>>(63-(s&&&63)))=u,(if s<64 then (m>>>1)>>>(63-(s&&&63))else m<<<(s&&&63))=v,(if s<64 then m<<<(s&&&63)else 0)=w at o⊢;unfold Yx;rw[X2,ξ,ν (a:=c˧+l˧) ((Ϯ n _).trans_lt j),<-Zn];generalize K:ε a*ε b*2^(γ a+γ b-d˧)=P at o;rw[(by rw[<-K];split_ifs<;>push_cast<;>ring:(if Ζ (η a) (η b)then-((ε a*ε b:ٳ):ٴ)else ((ε a*ε b:ٳ):ٴ))*2^(γ a+γ b-d˧)=if Ζ (η a) (η b)then-(P:ٴ)else P)];clear* -p n o;have C:=G7 u l n;have D:=G7 v l n;have E:=G7 w l n;have H:=u܉;have I:=v܉;have J:=w܉;push_cast;rw[Int.emod_add_emod];conv_rhs=>rw[<-CA _ _ (l˧:ٴ)] exact congrArg (·%_) (by linear_combination (by subst o;split_ifs at p C D E⊢<;>omega:((u^^^(0-l))˧*2^128+(v^^^(0-l))˧*2^64+(w^^^(0-l))˧+l˧:ٴ)=(if Ζ (η a) (η b)then-(P:ٴ)else P)+2^192*l˧)) @[inline] def YD (w2 w1 w0 c:ػ) (e:ٴ):ػ:= let t0:=w0+c;let k0:ػ:=if t0>>23).toNat def YM (a:ؼ):ٳ:=((a&&&ק)>>>23).toNat lemma W9 (a:ؼ):(a&&&ק)؎=(θ a)؎*2^23+(fracOf a)؎:=by simp only[AH,θ,fracOf,Ϣ];rw[show(ק:ؼ)؎=2^31-1 from rfl,show(0xFF:ؼ)؎=2^8-1 from rfl,show(0x7FFFFF:ؼ)؎=2^23-1 from rfl,show(23:ؼ)؎%32=23 from rfl,ϡ,ϡ,ϡ,ψ];omega lemma Zb (a:ؼ):YR a<=511/\YM a<=255/\(YM a<255 -> θ a≠255) /\ (ε a≠0 -> YR a<=γ a+1/\γ a+1<=max (YM a) 1):=by have e:=expOf_toNat_lt a;have f:=fracOf_toNat_lt a;unfold YR YM ε γ;simp only[Ϣ,CX,CD,BY,ψ,W9,ne_eq,<-ύ];rw[Ϟ _ (fracOf a)؎,ϔ _ _ (Δ _),Υ f,Β];generalize (θ a)؎=E at*;generalize (fracOf a)؎=F at*;have K:(2^32-1+(F+E*2^23))%2^32/2^23<=E∨E=0∧F=0:=א;refine⟨CI (ϕ (Ε _ ד)),CI e,Nat.ne_of_lt,λ d=>?_⟩;by_cases b:E=0 . rw[if_pos b]at d⊢;exact⟨(K.resolve_right λ h=>d h.2).trans (Nat.le_succ_of_le b.le),Nat.le_max_right _ _⟩ . rw[if_neg b]at d⊢;rw[Aw (Ο b)];exact⟨K.resolve_right λ h=>b h.1,Nat.le_max_left _ _⟩ def Yah (A:ؽ δ) (base n:ؾ) (hA:baseپ+nپ<=Aٽ) (hs:baseپ+nپ<Λ) (lo hi:ؼ) (k:ؾ):ؼ:= if h:k>>23)<<<16)+(hi>>>23) termination_by nپ-kپ decreasing_by exact ZI n k h lemma W8 (A:ؽ δ) (a n:ؾ) (h:a؛+n؛<=Aٽ) (f:a؛+n؛<Λ) (b e:ؼ) (k:ؾ) (j:k؛<=n؛) (g:e؎<2^31) : ∃ L H:ٳ,(Yah A a n h f b e k)؎=L*2^16+H/\L<=511/\H<=255 /\ L<=b؎/2^23/\e؎/2^23<=H /\ ∀ t,k؛<=t -> t L<=YR A[a؛+t]! /\ YM A[a؛+t]! <= H:=by generalize E:n؛-k؛=d;induction d generalizing k b e with |zero=> rw[Yah,dif_neg (mt υ.1 א)];have:=b.toNat_lt;refine⟨b؎/2^23,e؎/2^23,?_,א,א,le_rfl,le_rfl,λ t o p=>א⟩;simp only[UInt32.toNat_add,Dk,Ϣ,CD,BY];omega |succ d u=> have q:komega) א;have r:L<=b؎/2^23∧L<=YR w:=by split_ifs at y with l<;>rw[Dl]at l<;>omega have s:e؎/2^23<=H∧YM w<=H:=by split_ifs at z with l<;>rw[Dl]at l<;>omega refine⟨L,H,o,p,x,r.1,s.1,λ t K C=>?_⟩;obtain rfl|D:t=kپ∨(k+1)؛<=t:=א;rw[v];exact⟨r.2,s.2⟩;exact B t D C def YS (X W:ؽ δ) (xa wa n:ؾ) (hX:xaپ+nپ<=Xٽ) (hW:waپ+nپ<=Wٽ) (hx:xaپ+nپ<Λ) (hw:waپ+nپ<Λ) (lo:ػ) (e:ٴ) (bw:ؼ) (w2 w1 w0 c:ػ) (k:ؾ):ػ:= if h:kYS X W xa wa n hX hW hx hw lo e bw v2 v1 v0 c' (k+1) else YL lo ζ bw w2 w1 w0 c λ v2 v1 v0 c'=>YD v2 v1 v0 c' e termination_by nپ-kپ decreasing_by exact ZI n k h def YB (X W:ؽ δ) (xa wa lo k:ٳ):ٳ -> ٴ | 0=>0 | r+1=>sv X[xa+k]! * sv W[wa+k]! * 2^(γ X[xa+k]! + γ W[wa+k]! - lo) + YB X W xa wa lo (k+1) r lemma ZL (a b:ؼ) (d:ٳ) (h:ε a*ε b≠0 -> d<=γ a+γ b/\γ a+γ b<=d+122) : -(2^170:ٴ)<=sv a*sv b*2^(γ a+γ b-d) /\ sv a*sv b*2^(γ a+γ b-d)<=2^170:=by rw[<-Zn];have g:=ZK a b;by_cases e:ε a*ε b=0 . rw[e];split_ifs<;>simp . obtain⟨j,k⟩:=h e;have f:2^(γ a+γ b-d)<=2^122:=Ι ב א;have l:ε a*ε b*2^(γ a+γ b-d)<=2^170:=calc ε a*ε b*2^(γ a+γ b-d)<=2^48*2^122:=Ar א f _=2^170:=ב have c:((ε a*ε b:ٳ):ٴ)*2^(γ a+γ b-d)=((ε a*ε b*2^(γ a+γ b-d):ٳ):ٴ):=by push_cast;ring split_ifs . rw[neg_mul,c];omega . rw[c];omega lemma ZW (a b:ٳ -> ؼ):∀ r k,Yo a b k (r+1)=Yo a b k r+sv (a (k+r))*sv (b (k+r))*2^(γ (a (k+r))+γ (b (k+r))):=by intro r;induction r;simp[Yo];next r d=>intro k;rw[Yo,d (k+1),Yo,BU k 1 r,Ϟ 1 r];ring lemma ZA (a b:ؼ) (d:ٳ) (h:ε a*ε b≠0 -> d<=γ a+γ b):sv a*sv b*2^(γ a+γ b)=2^d*(sv a*sv b*2^(γ a+γ b-d)):=by by_cases e:ε a*ε b=0 . have:sv a*sv b=0:=by rw[<-Zn,e];split_ifs<;>simp rw[this];ring rw[(א:idxOf a+idxOf b=d+(idxOf a+idxOf b-d)),pow_add];rw[(א:d+(idxOf a+idxOf b-d)-d=idxOf a+idxOf b-d)];ring @[inline] def Yc (A:ؽ δ) (inW i:ٳ):ؼ:= if h:i*inW+inW<=Aٽ/\i*inW+inW<=ހ then Yah A (i*inW).toUSize inWٿ (by rw [Za _ א,Za _ א];exact h.1) (by rw [Za _ א,Za _ א];have:=τ;omega) 0xFFFFFFFF 0 0 else 0x01FF00FF @[inline] def Yk (k:ؼ):ػ:=(if k=0 then 0 else k-1).toUInt64 @[inline] def Yp (bx bv bw:ؼ):ػ:= let lo0:=Yk (bx>>>16)+Yk (bv>>>16);let xb:=Yd ζ+Yd bw;if !(Yf bw==0)&&xbif t < inW then X[i*inW+t]! else ζ) (λ t=>if t < inW then W[j*inW+t]! else b[j]!) @[inline] def YL6 {β:Type} (lo:ػ) (a b:ؼ) (w2 w1 w0 c:ػ) (kont:ػ -> ػ -> ػ -> ػ -> β):β:= let m:=Yf a*Yf b;let s:=Yd a+Yd b-lo;let rr:=s&&&63;let y0:=m<<>>1)>>>(63-rr);let ng:=((a^^^b)>>>31).toUInt64;let mk:ػ:=0-ng;let s0:=w0+(y0^^^mk);let k0:ػ:=if s0 ػ -> ػ -> ػ -> β) (h:ε a*ε b=0\/(e˧<=γ a+γ b/\γ a+γ b<=e˧+63)) : YL6 e a b f g j c d=YL e a b f g j c d:=by unfold YL6 YL;by_cases k:Yd a+Yd b-e<64 ·simp only[k,ר,Ch] · have o:Yf a*Yf b=0:=by rcases h with h|⟨p,q⟩ · rcases Ax.mp h with h|h ·have:Yf a=0:=σ.mp (by rw[Zk,h];rfl);rw[this];simp ·have:Yf b=0:=σ.mp (by rw[Zk,h];rfl);rw[this];simp ·exfalso;apply k;have l:=Zf a;have n:=Zf b;have r:=Zg a;have s:=Zg b;rw[Ψ,Η _ _ (ϐ.mpr (by rw[ξ,l,n];norm_num;omega)),ξ,l,n];norm_num;omega simp only[k,ש,o,DB,Dm,Ch] @[inline] def YL16 {β:Type} (lo:ػ) (a b:ؼ) (_w2 h w0 c:ػ) (kont:ػ -> ػ -> ػ -> ػ -> β):β:= let m:=Yf a*Yf b;let s:=Yd a+Yd b-lo;let y0:=m<<<(s&&&63);let ng:=((a^^^b)>>>31).toUInt64;let mk:ػ:=0-ng;let s0:=w0+(y0^^^mk);let k0:ػ:=if s0>>63)) (h+mk+k0) s0 (c+ng) lemma J3 (h a b:ػ) (d:a=0\/a=0-1) (f:b=0\/b=1) (g:h˧≠2^63-1/\h˧≠2^63) : (0:ػ)-(h>>>63)+a+((if h+a>>63):=by have e:∀x:ػ,((0:ػ)-(x>>>63))˧=if x˧<2^63 then 0 else 2^64-1:=by intro x;have:=x܉;rw[Τ,Ξ,ψ];simp only[Ϝ,show(63:ػ)˧%64=63 from rfl];split_ifs<;>omega have j:=h܉;replace g:h˧<2^63-1\/2^63rcases f with rfl|rfl<;>split_ifs with k l<;> simp only[Ψ,ξ,e,Du,show(0-1:ػ)˧=2^64-1 from rfl,Ϝ,Da,Nat.zero_or,Nat.or_zero,Nat.or_self]at*<;> split_ifs at*<;>omega lemma S5 (h a b:ػ) (k:ٳ) (d:a=0\/a=0-1) (e:b=0\/b=1) (g:h˧<=k\/2^64-k<=h˧) (f:k<2^62) : (h+a+b)˧<=k+1\/2^64-(k+1)<=(h+a+b)˧:=by have j:=h܉;rcases d with rfl|rfl<;>rcases e with rfl|rfl<;>simp only[ξ,show(0-1:ػ)˧=2^64-1 from rfl,Ϝ,Da]<;>omega lemma S6 (m r:ػ) (a:m˧<2^48) (b:r˧<=16):(m>>>1)>>>(63-r)=0:=by apply σ.mp;rw[Ξ,Ξ,Η _ _ (ϐ.mpr (by show r˧<=63;omega)),ψ,ψ,show(63:ػ)˧=63 from rfl,show(1:ػ)˧%64=1 from rfl,Ϝ,ν (show 63-r˧<64 by omega),ϧ];exact Υ (a.trans_le (by rw[<-Κ];exact Ι ב א)) lemma E1 (a b:ؼ):(0:ػ)-((a^^^b)>>>31)܅=0\/(0:ػ)-((a^^^b)>>>31)܅=0-1:=by have:=D4 a b;split at this;right;rw[σ.1 (show((a^^^b)>>>31)܅˧=(1:ػ)˧from this)];left;rw[σ.1 (show((a^^^b)>>>31)܅˧=(0:ػ)˧from this)];rfl lemma C5 {β:Type} (e:ػ) (a b:ؼ) (h f c:ػ) (d:ػ -> ػ -> ػ -> ػ -> β) (g:ε a*ε b=0\/(e˧<=γ a+γ b/\γ a+γ b<=e˧+16)) (j:h˧≠2^63-1/\h˧≠2^63) : YL e a b ((0:ػ)-(h>>>63)) h f c d=YL16 e a b ((0:ػ)-(h>>>63)) h f c d:=by have n:=Zf a;have o:=Zf b;have u:=Zg a;have v:=Zg b;have k:ε a*ε b=0->Yf a*Yf b=0:=λ l=>σ.mp (by rw[ϯ,Zk,Zk,l];rfl);have p:((Yf a*Yf b)>>>1)>>>(63-((Yd a+Yd b-e)&&&63))=0:=by rcases g with l|⟨r,s⟩;rw[k l];simp;apply S6;rw[ϯ,Zk,Zk];have:=ZK a b;omega;rw[H0,Η _ _ (ϐ.mpr (by rw[ξ,n,o];omega)),ξ,n,o];omega unfold YL YL16;dsimp only;by_cases q:Yd a+Yd b-e<64;simp only[q,ר,p,Ch];rw[J3 h _ _ (E1 a b) ?_ j];split<;>simp;have t:Yf a*Yf b=0:=by rcases g with l|⟨r,s⟩;exact k l;exfalso;apply q;rw[Ψ,Η _ _ (ϐ.mpr (by rw[ξ,n,o];omega)),ξ,n,o];norm_num;omega simp only[q,ש,t,DB,Dm,Ch];rw[J3 h _ _ (E1 a b) ?_ j];split<;>simp def YS6 (q:ف) (X W:ؽ δ) (xa wa n:ؾ) (hX:xaپ+nپ<=Xٽ) (hW:waپ+nپ<=Wٽ) (hx:xaپ+nپ<Λ) (hw:waپ+nپ<Λ) (lo:ػ) (e:ٴ) (bw:ؼ) (w2 w1 w0 c:ػ) (k:ؾ):ػ:= if h:kYS6 q X W xa wa n hX hW hx hw lo e bw v2 v1 v0 c' (k+1) else YL6 lo (X.uget (xa+k) (A4 X xa n k hX hx h)) (W.uget (wa+k) (A4 W wa n k hW hw h)) w2 w1 w0 c λ v2 v1 v0 c'=>YS6 q X W xa wa n hX hW hx hw lo e bw v2 v1 v0 c' (k+1) else YL lo ζ bw w2 w1 w0 c λ v2 v1 v0 c'=>YD v2 v1 v0 c' e termination_by nپ-kپ decreasing_by all_goals exact ZI n k h lemma I6 (q:ف) (X W:ؽ δ) (a b n:ؾ) (j:a؛+n؛<=Xٽ) (l:b؛+n؛<=Wٽ) (g:a؛+n؛<Λ) (h:b؛+n؛<Λ) (f:ػ) (e:ٴ) (o:ؼ) (p:n؛<2^62) (D:ٳ) (r:q -> D<=16) (s:D<=63) (u:∀ t,t ε X[a؛+t]! * ε W[b؛+t]! ≠ 0 -> f˧<=γ X[a؛+t]! + γ W[b؛+t]! /\ γ X[a؛+t]! + γ W[b؛+t]! <= f˧+D) : ∀ (d:ٳ) (k:ؾ) (w v x c:ػ),n؛-k؛=d -> (q -> w=(0:ػ)-(v>>>63)/\(v˧<=k؛\/2^64-k؛<=v˧)) -> YS6 q X W a b n j l g h f e o w v x c k=YS X W a b n j l g h f e o w v x c k:=by intro d;induction d<;>intro k w v x c B J ·have y:=υ.not.2 (Dw B).not_gt;rw[YS6,YS,dif_neg y,dif_neg y] rename_i d E;have z:=Al B;have y:=υ.2 z;have F:=QK n k y;have G:n؛-(k+1)؛=d:=by rw[F,Cx,B];rfl rw[YS6,YS,dif_pos y,dif_pos y,B3 X a k _ ((ϴ z _).trans g),B3 W b k _ ((ϴ z _).trans h)];have C:=u k؛ z;cases q . rw[if_neg AC,I7 f _ _ w v x c _ (or_iff_not_imp_left.2 λ A=>⟨(C A).1,(C A).2.trans (by gcongr)⟩)];apply congrArg;funext K L M N;exact E (k+1) K L M N G ג . obtain⟨rfl,H⟩:=J rfl;have I:=z.trans p;rw[if_pos rfl,C5 f _ _ v x c _ (or_iff_not_imp_left.2 λ A=>⟨(C A).1,(C A).2.trans (by gcongr;exact r rfl)⟩) (by clear* -H I;omega)];unfold YL16;dsimp only;apply E (k+1) _ _ _ _ G (λ _=>⟨rfl,?_⟩);rw[F];apply S5 v _ _ k؛ (E1 _ _) ?_ H I;split<;>simp @[inline] def YaU (X W b:ؽ δ) (inW i j:ٳ) (bx bv:ؼ):δ:= if h:i*inW+inW<=Xٽ/\j*inW+inW<=Wٽ/\i*inW+inW<=ހ /\ j*inW+inW<=ހ/\inW<ށ then let bw:=b[j]!;let lo:=Yp bx bv bw;let hi:=Yu bx bv bw;if (bx&&&ޅ)=255||(bv&&&ޅ)=255||θ bw=255||hi122 then Yai X W b inW i j else have p1:(i*inW).toUSizeپ+inW.toUSizeپ<=Xٽ:=by rw [Za _ א,Za _ א];exact h.1 have p2:(j*inW).toUSizeپ+inW.toUSizeپ<=Wٽ:=by rw [Za _ א,Za _ א];exact h.2.1 have p3:(i*inW).toUSizeپ+inW.toUSizeپ<Λ:=by rw [Za _ א,Za _ א];have:=τ;omega have p4:(j*inW).toUSizeپ+inW.toUSizeپ<Λ:=by rw [Za _ א,Za _ א];have:=τ;omega let r:=if hi-lo<=63 then YS6 (hi-lo<=16) X W (i*inW).toUSize (j*inW).toUSize inWٿ p1 p2 p3 p4 lo ((loپ:ٴ)-298) bw 0 0 0 0 0 else YS X W (i*inW).toUSize (j*inW).toUSize inWٿ p1 p2 p3 p4 lo ((loپ:ٴ)-298) bw 0 0 0 0 0 if r<߿ then r.toUInt32 else Yai X W b inW i j else Yai X W b inW i j @[specialize] def Yaj (hw:ٳ) (f:ٳ -> ٳ -> δ) (ch j:ٳ) (acc:ؽ δ):ؽ δ:= if j ٳ -> δ) (ch:ٳ) (acc:ؽ δ):ؽ δ:= if ch ٳ -> δ):ؽ δ:=Yak c hw f 0 (AY (c*hw)) lemma D3 (a:ٳ) (f:ٳ -> ٳ -> δ) (b:ٳ):∀ k j (d:ؽ δ),a-j=k -> (Yaj a f b j d)܍=d܍++(Bd j (a-j)).map (f b):=by intro k;induction k<;>intro j d h<;>unfold Yaj;rw[if_neg א];simp[h];next k e=>rw[if_pos א,e (j+1) _ א,Cx,h,Ϩ];simp lemma W5 (c a:ٳ) (f:ٳ -> ٳ -> δ):∀ k b (d:ؽ δ),c-b=k -> (Yak c a f b d)܍=d܍++(Bd (b*a) ((c-b)*a)).map (λ i=>f (i/a) (i%a)):=by intro k;induction k<;>intro b d h<;>unfold Yak ·rw[if_neg א];simp[h] rename_i e;rw[if_pos א,e (b+1) _ א,D3 a f b _ 0 _ rfl,show(c-b)*a=a+(c-(b+1))*a by rw[show c-b=(c-(b+1))+1 by omega,Dp,Ϟ],<-List.range'_append,List.map_append,Ah];simp only[CL,Ai];congr 2 . rw[show Bd (b*a) a=(Bd 0 a).map (b*a+·) by rw[DS];simp,Df];apply Ck;intro j g;rw[List.mem_range'_1]at g;have q:j ٳ -> δ):YT c a f=ڀ N λ i=>f (i܂/a) (i܂%a):=by subst b;apply ϻ;rw[YT,W5 c a f _ 0 _ rfl];apply ϩ<;>simp @[inline] def QhiS (hi lo q:ػ):ػ:= hi+((0:ػ)-(q>>>63))+(if lo+q>>16) @[specialize] def QY6G (n:ؾ) (f:(k:ؾ) -> k ػ) (B0:ػ) (bw:ؼ) (hi lo:ػ) (k:ؾ):ػ:= if h:k>>63)) hi lo 0 λ v2 v1 v0 c' => YD v2 v1 v0 c' ((B0پ:ٴ)-298) termination_by nپ-kپ decreasing_by exact ZI n k h @[inline] def QPb (x:ؼ) (m:ػ) (s:ف):ٳ:= let M:=Yf x<<<(Yd x-m);(if η x != s then ބ-M else ބ+M).toNat @[specialize] def QPD (n:ٳ) (f:ٳ -> ؼ) (m:ػ) (t:ٳ) (P:ؽ ٳ):ؽ ٳ:= if t ؼ) (t:ٳ) (I:ؽ ؼ):ؽ ؼ:= if t>>31).toUSize)؛=2*k؛+(w>>>31)؎/\(w>>>31)؎<2:=by have e:(w>>>31)؎<2:=by rw[Ϣ,ψ];exact ϕ w.toNat_lt have:=τ;exact⟨by rw[Zc _ _ (by rw[Zc _ _ א,AI];omega),Zc _ _ א,AI];omega,e⟩ @[inline] def QPS (inW:ٳ) (BX BV:ؽ ؼ):ف:= 16<=inW&&BX.all (λ bx=>bx&&&ޅ != 255)&&BV.all (λ bv=>bv&&&ޅ != 255) && (BX.foldl (λ (m:ػ) (bx:ؼ)=>min m (QYF bx)) 99).toNat+(BV.foldl (λ (m:ػ) (bv:ؼ)=>max m (QYF bv)) 0).toNat<=15 lemma R8 (u:ؼ) (n:ٳ) (h:n<ށ):(min u (n-1).toUInt32)؎<=n-1 /\ (u؎<=n-1 -> min u (n-1).toUInt32=u):=by have e:(n-1).toUInt32؎=n-1:=ו;rw[UInt32.min_def];split<;>rename_i c<;>rw[AJ,e]at c;exact⟨c,λ _=>rfl⟩;exact⟨by omega,(absurd · c)⟩ @[inline] def QPa (X:ؽ δ) (P:ؽ ٳ) (I:ؽ ؼ) (W b:ؽ δ) (inW i j:ٳ) (bx bv:ؼ):δ:= let xm:=Yk (bx>>>16) let wm:=Yk (bv>>>16) let bw:=b[j]! let xb:=Yd ζ+Yd bw if h:Pٽ=2*(if Iٽ=0 then inW else Iٽ)/\Iٽ<=inW/\i*inW+inW<=Xٽ/\j*inW+inW<=Wٽ/\i*inW+inW<=ހ /\ j*inW+inW<=ހ/\inW<ށ/\(bx&&&ޅ)≠255/\(bv&&&ޅ)≠255 /\ xm<=Yk (bx&&&ޅ)/\wm<=Yk (bv&&&ޅ)/\(QYF bx).toNat+(QYF bv).toNat<=15 /\ θ bw≠255/\(Yf bw=0\/(xm+wm<=xb/\xb-(xm+wm)<80))/\1<=wm then let wa:=(j*inW).toUSize let iw:=(inW-1).toUInt32 let r:=if c:Iٽ=0 then QY6G inWٿ (λ k hk=> let w:=W.uget (wa+k) (by have:=υ.mp hk;rw [Za _ א] at this;simp only [wa];rw [Zc _ _ (by rw [Za _ א];have:=τ;omega),Za _ א];omega) ((P.uget (k+k+(w>>>31).toUSize) (by have:=υ.mp hk;rw [Za _ א] at this;have:=D0 k w א;rw [if_pos c] at h;omega)).toUInt64-ބ)*(Yf w<<<((θ w).toUInt64-(wm+1)))) (xm+wm) bw 0 0 0 else QY6G Iٽٿ (λ k hk=> let u:=I.uget k (by have:=υ.mp hk;rw [Za _ א] at this;omega) let w:=W.uget (wa+(min u iw).toUSize) (by have:=υ.mp hk;rw [Za _ א] at this;have:=(R8 u inW א).1;simp only [wa,iw] at *;rw [Zc _ _ (by rw [Za _ א,AI];have:=τ;omega),Za _ א,AI];omega) ((P.uget (k+k+(w>>>31).toUSize) (by have:=υ.mp hk;rw [Za _ א] at this;have:=D0 k w א;rw [if_neg c] at h;omega)).toUInt64-ބ)*(Yf w<<<((θ w).toUInt64-(wm+1)))) (xm+wm) bw 0 0 0 if r<߿ then r.toUInt32 else Yai X W b inW i j else YaU X W b inW i j bx bv @[specialize] def QY6G2 {β:Type} (kont:ػ -> ػ -> β) (n:ؾ) (f:(k:ؾ) -> k ػ × ػ) (B1 B2:ػ) (bw:ؼ) (h1 l1 h2 l2:ػ) (k:ؾ):β:= if h:k>>63)) h1 l1 0 λ v2 v1 v0 c'=>YD v2 v1 v0 c' ((B1پ:ٴ)-298)) (YL B2 ζ bw ((0:ػ)-(h2>>>63)) h2 l2 0 λ v2 v1 v0 c'=>YD v2 v1 v0 c' ((B2پ:ٴ)-298)) termination_by nپ-kپ decreasing_by exact ZI n k h @[inline] def QPg2 (X:ؽ δ) (P1 P2:ؽ ٳ) (I1 I2:ؽ ؼ) (W b:ؽ δ) (inW i j:ٳ) (bx1 bx2 bv:ؼ):ف:= let G:=λ (P:ؽ ٳ) (I:ؽ ؼ) (i:ٳ) (bx:ؼ)=>decide (Pٽ=2*(if Iٽ=0 then inW else Iٽ)/\Iٽ<=inW/\i*inW+inW<=Xٽ/\j*inW+inW<=Wٽ/\i*inW+inW<=ހ /\ j*inW+inW<=ހ/\inW<ށ/\(bx&&&ޅ)≠255/\(bv&&&ޅ)≠255 /\ Yk (bx>>>16)<=Yk (bx&&&ޅ)/\Yk (bv>>>16)<=Yk (bv&&&ޅ)/\(QYF bx).toNat+(QYF bv).toNat<=15 /\ θ (b[j]!)≠255/\(Yf (b[j]!)=0\/(Yk (bx>>>16)+Yk (bv>>>16)<=Yd ζ+Yd (b[j]!)/\Yd ζ+Yd (b[j]!)-(Yk (bx>>>16)+Yk (bv>>>16))<80))/\(1:ػ)<=Yk (bv>>>16)) G P1 I1 i bx1&&G P2 I2 (i+1) bx2&&I1ٽ==0&&I2ٽ==0 @[inline] def QPa2 (X:ؽ δ) (P1 P2:ؽ ٳ) (I1 I2:ؽ ؼ) (W b:ؽ δ) (inW i j:ٳ) (bx1 bx2 bv:ؼ):δ × δ:= if h:QPg2 X P1 P2 I1 I2 W b inW i j bx1 bx2 bv=true then have q:j*inW+inW<=Wٽ/\j*inW+inW<=ހ/\inW<ށ/\P1ٽ=2*inW/\P2ٽ=2*inW:=by simp only [QPg2,Ω,ת,beq_iff_eq] at h;obtain ⟨⟨⟨g1,g2⟩,c1⟩,c2⟩:=h;simp only [c1,c2,↓reduceIte] at g1 g2;omega let wm:=Yk (bv>>>16);let wa:=(j*inW).toUSize;QY6G2 (λ r1 r2=>(if r1<߿ then r1.toUInt32 else Yai X W b inW i j,if r2<߿ then r2.toUInt32 else Yai X W b inW (i+1) j)) inWٿ (λ k hk=> let w:=W.uget (wa+k) (by have:=υ.mp hk;rw [Za _ א] at this;simp only [wa];rw [Zc _ _ (by rw [Za _ א];have:=τ;omega),Za _ א];omega) let v:=Yf w<<<((θ w).toUInt64-(wm+1));(((P1.uget (k+k+(w>>>31).toUSize) (by have:=υ.mp hk;rw [Za _ א] at this;have:=D0 k w א;omega)).toUInt64-ބ)*v, ((P2.uget (k+k+(w>>>31).toUSize) (by have:=υ.mp hk;rw [Za _ א] at this;have:=D0 k w א;omega)).toUInt64-ބ)*v)) (Yk (bx1>>>16)+wm) (Yk (bx2>>>16)+wm) b[j]! 0 0 0 0 0 else (QPa X P1 I1 W b inW i j bx1 bv,QPa X P2 I2 W b inW (i+1) j bx2 bv) @[specialize] def Yr2 (hw:ٳ) (f:ٳ -> δ × δ) (j:ٳ) (A B:ؽ δ):ؽ δ × ؽ δ:= if j ػ -> ػ -> ػ -> β) (n:ؾ) (f:(k:ؾ) -> k (ػ × ػ) × (ػ × ػ)) (B1 B2 B3 B4:ػ) (bw:ؼ) (h1 l1 h2 l2 h3 l3 h4 l4:ػ) (k:ؾ):β:= if h:k>>63)) h1 l1 0 λ v2 v1 v0 c'=>YD v2 v1 v0 c' ((B1پ:ٴ)-298)) (YL B2 ζ bw ((0:ػ)-(h2>>>63)) h2 l2 0 λ v2 v1 v0 c'=>YD v2 v1 v0 c' ((B2پ:ٴ)-298)) (YL B3 ζ bw ((0:ػ)-(h3>>>63)) h3 l3 0 λ v2 v1 v0 c'=>YD v2 v1 v0 c' ((B3پ:ٴ)-298)) (YL B4 ζ bw ((0:ػ)-(h4>>>63)) h4 l4 0 λ v2 v1 v0 c'=>YD v2 v1 v0 c' ((B4پ:ٴ)-298)) termination_by nپ-kپ decreasing_by exact ZI n k h @[inline] def QPa4 (X:ؽ δ) (P1 P2 P3 P4:ؽ ٳ) (I1 I2 I3 I4:ؽ ؼ) (W b:ؽ δ) (inW i j:ٳ) (bx1 bx2 bx3 bx4 bv:ؼ):(δ × δ) × (δ × δ):= if h:QPg2 X P1 P2 I1 I2 W b inW i j bx1 bx2 bv=true/\QPg2 X P3 P4 I3 I4 W b inW (i+2) j bx3 bx4 bv=true then have q:j*inW+inW<=Wٽ/\j*inW+inW<=ހ/\inW<ށ/\P1ٽ=2*inW/\P2ٽ=2*inW/\P3ٽ=2*inW/\P4ٽ=2*inW:=by obtain⟨h,h'⟩:=h;simp only [QPg2,Ω,ת,beq_iff_eq] at h h';obtain ⟨⟨⟨g1,g2⟩,c1⟩,c2⟩:=h;obtain ⟨⟨⟨g3,g4⟩,c3⟩,c4⟩:=h';simp only [c1,c2,c3,c4,↓reduceIte] at g1 g2 g3 g4;omega let wm:=Yk (bv>>>16);let wa:=(j*inW).toUSize;QY6G4 (λ r1 r2 r3 r4=>((if r1<߿ then r1.toUInt32 else Yai X W b inW i j,if r2<߿ then r2.toUInt32 else Yai X W b inW (i+1) j),(if r3<߿ then r3.toUInt32 else Yai X W b inW (i+2) j,if r4<߿ then r4.toUInt32 else Yai X W b inW (i+2+1) j))) inWٿ (λ k hk=> let w:=W.uget (wa+k) (by have:=υ.mp hk;rw [Za _ א] at this;simp only [wa];rw [Zc _ _ (by rw [Za _ א];have:=τ;omega),Za _ א];omega) let v:=Yf w<<<((θ w).toUInt64-(wm+1));((((P1.uget (k+k+(w>>>31).toUSize) (by have:=υ.mp hk;rw [Za _ א] at this;have:=D0 k w א;omega)).toUInt64-ބ)*v,((P2.uget (k+k+(w>>>31).toUSize) (by have:=υ.mp hk;rw [Za _ א] at this;have:=D0 k w א;omega)).toUInt64-ބ)*v),(((P3.uget (k+k+(w>>>31).toUSize) (by have:=υ.mp hk;rw [Za _ א] at this;have:=D0 k w א;omega)).toUInt64-ބ)*v,((P4.uget (k+k+(w>>>31).toUSize) (by have:=υ.mp hk;rw [Za _ א] at this;have:=D0 k w א;omega)).toUInt64-ބ)*v))) (Yk (bx1>>>16)+wm) (Yk (bx2>>>16)+wm) (Yk (bx3>>>16)+wm) (Yk (bx4>>>16)+wm) b[j]! 0 0 0 0 0 0 0 0 0 else (QPa2 X P1 P2 I1 I2 W b inW i j bx1 bx2 bv,QPa2 X P3 P4 I3 I4 W b inW (i+2) j bx3 bx4 bv) @[specialize] def YS64 {β:Type} (kont:ػ -> ػ -> ػ -> ػ -> β) (q:ف) (X W:ؽ δ) (x1a x2a x3a x4a wa n:ؾ) (h1:x1aپ+nپ<=Xٽ) (h2:x2aپ+nپ<=Xٽ) (h3:x3aپ+nپ<=Xٽ) (h4:x4aپ+nپ<=Xٽ) (hW:waپ+nپ<=Wٽ) (g1:x1aپ+nپ<Λ) (g2:x2aپ+nپ<Λ) (g3:x3aپ+nپ<Λ) (g4:x4aپ+nپ<Λ) (hw:waپ+nپ<Λ) (lo1 lo2 lo3 lo4:ػ) (e1 e2 e3 e4:ٴ) (bw:ؼ) (a2 a1 a0 ac b2 b1 b0 bc c2 c1 c0 cc d2 d1 d0 dc:ػ) (k:ؾ):β:= if h:kYL16 lo2 x2 w b2 b1 b0 bc λ b2 b1 b0 bc=>YL16 lo3 x3 w c2 c1 c0 cc λ c2 c1 c0 cc=>YL16 lo4 x4 w d2 d1 d0 dc λ d2 d1 d0 dc=>YS64 kont q X W x1a x2a x3a x4a wa n h1 h2 h3 h4 hW g1 g2 g3 g4 hw lo1 lo2 lo3 lo4 e1 e2 e3 e4 bw a2 a1 a0 ac b2 b1 b0 bc c2 c1 c0 cc d2 d1 d0 dc (k+1) else YL6 lo1 x1 w a2 a1 a0 ac λ a2 a1 a0 ac=>YL6 lo2 x2 w b2 b1 b0 bc λ b2 b1 b0 bc=>YL6 lo3 x3 w c2 c1 c0 cc λ c2 c1 c0 cc=>YL6 lo4 x4 w d2 d1 d0 dc λ d2 d1 d0 dc=>YS64 kont q X W x1a x2a x3a x4a wa n h1 h2 h3 h4 hW g1 g2 g3 g4 hw lo1 lo2 lo3 lo4 e1 e2 e3 e4 bw a2 a1 a0 ac b2 b1 b0 bc c2 c1 c0 cc d2 d1 d0 dc (k+1) else kont (YL lo1 ζ bw a2 a1 a0 ac λ v2 v1 v0 c'=>YD v2 v1 v0 c' e1) (YL lo2 ζ bw b2 b1 b0 bc λ v2 v1 v0 c'=>YD v2 v1 v0 c' e2) (YL lo3 ζ bw c2 c1 c0 cc λ v2 v1 v0 c'=>YD v2 v1 v0 c' e3) (YL lo4 ζ bw d2 d1 d0 dc λ v2 v1 v0 c'=>YD v2 v1 v0 c' e4) termination_by nپ-kپ decreasing_by all_goals exact ZI n k h @[inline] def YaU4 (X W b:ؽ δ) (inW i j:ٳ) (bx1 bx2 bx3 bx4 bv:ؼ):(δ × δ) × (δ × δ):= let bw:=b[j]! let lo1:=Yp bx1 bv bw;let hi1:=Yu bx1 bv bw;let lo2:=Yp bx2 bv bw;let hi2:=Yu bx2 bv bw let lo3:=Yp bx3 bv bw;let hi3:=Yu bx3 bv bw;let lo4:=Yp bx4 bv bw;let hi4:=Yu bx4 bv bw let q:=hi1-lo1<=16 if h:i*inW+inW<=Xٽ/\(i+1)*inW+inW<=Xٽ/\(i+2)*inW+inW<=Xٽ/\(i+2+1)*inW+inW<=Xٽ/\j*inW+inW<=Wٽ/\i*inW+inW<=ހ/\(i+1)*inW+inW<=ހ/\(i+2)*inW+inW<=ހ/\(i+2+1)*inW+inW<=ހ/\j*inW+inW<=ހ/\inW<ށ/\ ((bx1&&&ޅ)=255||(bv&&&ޅ)=255||θ bw=255||hi1122)=false/\((bx2&&&ޅ)=255||(bv&&&ޅ)=255||θ bw=255||hi2122)=false/\ ((bx3&&&ޅ)=255||(bv&&&ޅ)=255||θ bw=255||hi3122)=false/\((bx4&&&ޅ)=255||(bv&&&ޅ)=255||θ bw=255||hi4122)=false/\ hi1-lo1<=63/\hi2-lo2<=63/\hi3-lo3<=63/\hi4-lo4<=63/\(hi2-lo2<=16)=q/\(hi3-lo3<=16)=q/\(hi4-lo4<=16)=q then have h1:(i*inW).toUSizeپ+inW.toUSizeپ<=Xٽ:=by rw [Za _ א,Za _ א];omega have g1:(i*inW).toUSizeپ+inW.toUSizeپ<Λ:=by rw [Za _ א,Za _ א];have:=τ;omega have h2:((i+1)*inW).toUSizeپ+inW.toUSizeپ<=Xٽ:=by rw [Za _ א,Za _ א];omega have g2:((i+1)*inW).toUSizeپ+inW.toUSizeپ<Λ:=by rw [Za _ א,Za _ א];have:=τ;omega have h3:((i+2)*inW).toUSizeپ+inW.toUSizeپ<=Xٽ:=by rw [Za _ א,Za _ א];omega have g3:((i+2)*inW).toUSizeپ+inW.toUSizeپ<Λ:=by rw [Za _ א,Za _ א];have:=τ;omega have h4:((i+2+1)*inW).toUSizeپ+inW.toUSizeپ<=Xٽ:=by rw [Za _ א,Za _ א];omega have g4:((i+2+1)*inW).toUSizeپ+inW.toUSizeپ<Λ:=by rw [Za _ א,Za _ א];have:=τ;omega have hW:(j*inW).toUSizeپ+inW.toUSizeپ<=Wٽ:=by rw [Za _ א,Za _ א];omega have hw:(j*inW).toUSizeپ+inW.toUSizeپ<Λ:=by rw [Za _ א,Za _ א];have:=τ;omega YS64 (λ r1 r2 r3 r4=>((if r1<߿ then r1.toUInt32 else Yai X W b inW i j,if r2<߿ then r2.toUInt32 else Yai X W b inW (i+1) j),(if r3<߿ then r3.toUInt32 else Yai X W b inW (i+2) j,if r4<߿ then r4.toUInt32 else Yai X W b inW (i+2+1) j))) q X W (i*inW).toUSize ((i+1)*inW).toUSize ((i+2)*inW).toUSize ((i+2+1)*inW).toUSize (j*inW).toUSize inWٿ h1 h2 h3 h4 hW g1 g2 g3 g4 hw lo1 lo2 lo3 lo4 ((lo1پ:ٴ)-298) ((lo2پ:ٴ)-298) ((lo3پ:ٴ)-298) ((lo4پ:ٴ)-298) bw 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 else ((YaU X W b inW i j bx1 bv,YaU X W b inW (i+1) j bx2 bv),(YaU X W b inW (i+2) j bx3 bv,YaU X W b inW (i+2+1) j bx4 bv)) @[inline] def QPa4w (X:ؽ δ) (P1 P2 P3 P4:ؽ ٳ) (I1 I2 I3 I4:ؽ ؼ) (W b:ؽ δ) (inW i j:ٳ) (bx1 bx2 bx3 bx4 bv:ؼ):(δ × δ) × (δ × δ):= if P1ٽ=0/\P2ٽ=0/\P3ٽ=0/\P4ٽ=0/\1<=inW then YaU4 X W b inW i j bx1 bx2 bx3 bx4 bv else ((QPa X P1 I1 W b inW i j bx1 bv,QPa X P2 I2 W b inW (i+1) j bx2 bv),(QPa X P3 I3 W b inW (i+2) j bx3 bv,QPa X P4 I4 W b inW (i+2+1) j bx4 bv)) @[specialize] def Yr4 (hw:ٳ) (f:ٳ -> (δ × δ) × (δ × δ)) (j:ٳ) (A B C D:ؽ δ):ؽ δ × ؽ δ × ؽ δ × ؽ δ:= if j ٳ -> δ) (f4:ٳ -> ٳ -> (δ × δ) × (δ × δ)) (d4:ٳ -> ف) (ch j:ٳ) (acc:ؽ δ):ؽ δ:= if j+3 ف) (f4:ٳ -> ٳ -> (δ × δ) × (δ × δ)) (e4:ٳ -> ف) (g4:ٳ -> ٳ -> (δ × δ) × (δ × δ)) (d:ٳ -> ف) (f2:ٳ -> ٳ -> δ × δ) (f:ٳ -> ٳ -> δ) (f4c:ٳ -> ٳ -> (δ × δ) × (δ × δ)) (d4c:ٳ -> ف) (ch:ٳ) (acc:ؽ δ):ؽ δ:= if ch+3 ػ -> ػ -> ػ -> β) (q:ف) (X W:ؽ δ) (xa w1a w2a w3a w4a n:ؾ) (hX:xaپ+nپ<=Xٽ) (hW1:w1aپ+nپ<=Wٽ) (hW2:w2aپ+nپ<=Wٽ) (hW3:w3aپ+nپ<=Wٽ) (hW4:w4aپ+nپ<=Wٽ) (hx:xaپ+nپ<Λ) (hw1:w1aپ+nپ<Λ) (hw2:w2aپ+nپ<Λ) (hw3:w3aپ+nپ<Λ) (hw4:w4aپ+nپ<Λ) (lo1 lo2 lo3 lo4:ػ) (e1 e2 e3 e4:ٴ) (bw1 bw2 bw3 bw4:ؼ) (a2 a1 a0 ac b2 b1 b0 bc c2 c1 c0 cc d2 d1 d0 dc:ػ) (k:ؾ):β:= if h:kYL16 lo2 x w2 b2 b1 b0 bc λ b2 b1 b0 bc=>YL16 lo3 x w3 c2 c1 c0 cc λ c2 c1 c0 cc=>YL16 lo4 x w4 d2 d1 d0 dc λ d2 d1 d0 dc=>YS6c4 kont q X W xa w1a w2a w3a w4a n hX hW1 hW2 hW3 hW4 hx hw1 hw2 hw3 hw4 lo1 lo2 lo3 lo4 e1 e2 e3 e4 bw1 bw2 bw3 bw4 a2 a1 a0 ac b2 b1 b0 bc c2 c1 c0 cc d2 d1 d0 dc (k+1) else YL6 lo1 x w1 a2 a1 a0 ac λ a2 a1 a0 ac=>YL6 lo2 x w2 b2 b1 b0 bc λ b2 b1 b0 bc=>YL6 lo3 x w3 c2 c1 c0 cc λ c2 c1 c0 cc=>YL6 lo4 x w4 d2 d1 d0 dc λ d2 d1 d0 dc=>YS6c4 kont q X W xa w1a w2a w3a w4a n hX hW1 hW2 hW3 hW4 hx hw1 hw2 hw3 hw4 lo1 lo2 lo3 lo4 e1 e2 e3 e4 bw1 bw2 bw3 bw4 a2 a1 a0 ac b2 b1 b0 bc c2 c1 c0 cc d2 d1 d0 dc (k+1) else kont (YL lo1 ζ bw1 a2 a1 a0 ac λ v2 v1 v0 c'=>YD v2 v1 v0 c' e1) (YL lo2 ζ bw2 b2 b1 b0 bc λ v2 v1 v0 c'=>YD v2 v1 v0 c' e2) (YL lo3 ζ bw3 c2 c1 c0 cc λ v2 v1 v0 c'=>YD v2 v1 v0 c' e3) (YL lo4 ζ bw4 d2 d1 d0 dc λ v2 v1 v0 c'=>YD v2 v1 v0 c' e4) termination_by nپ-kپ decreasing_by all_goals exact ZI n k h @[inline] def YaUc4 (X W b:ؽ δ) (inW i j:ٳ) (bx bv1 bv2 bv3 bv4:ؼ):(δ × δ) × (δ × δ):= let bw1:=b[j]!;let bw2:=b[j+1]!;let bw3:=b[j+2]!;let bw4:=b[j+2+1]! let lo1:=Yp bx bv1 bw1;let hi1:=Yu bx bv1 bw1;let lo2:=Yp bx bv2 bw2;let hi2:=Yu bx bv2 bw2 let lo3:=Yp bx bv3 bw3;let hi3:=Yu bx bv3 bw3;let lo4:=Yp bx bv4 bw4;let hi4:=Yu bx bv4 bw4 let q:=hi1-lo1<=16 if h:i*inW+inW<=Xٽ/\j*inW+inW<=Wٽ/\(j+1)*inW+inW<=Wٽ/\(j+2)*inW+inW<=Wٽ/\(j+2+1)*inW+inW<=Wٽ/\i*inW+inW<=ހ/\j*inW+inW<=ހ/\(j+1)*inW+inW<=ހ/\(j+2)*inW+inW<=ހ/\(j+2+1)*inW+inW<=ހ/\inW<ށ/\ ((bx&&&ޅ)=255||(bv1&&&ޅ)=255||θ bw1=255||hi1122)=false/\((bx&&&ޅ)=255||(bv2&&&ޅ)=255||θ bw2=255||hi2122)=false/\ ((bx&&&ޅ)=255||(bv3&&&ޅ)=255||θ bw3=255||hi3122)=false/\((bx&&&ޅ)=255||(bv4&&&ޅ)=255||θ bw4=255||hi4122)=false/\ hi1-lo1<=63/\hi2-lo2<=63/\hi3-lo3<=63/\hi4-lo4<=63/\(hi2-lo2<=16)=q/\(hi3-lo3<=16)=q/\(hi4-lo4<=16)=q then have hX:(i*inW).toUSizeپ+inW.toUSizeپ<=Xٽ:=by rw [Za _ א,Za _ א];omega have hx:(i*inW).toUSizeپ+inW.toUSizeپ<Λ:=by rw [Za _ א,Za _ א];have:=τ;omega have hW1:(j*inW).toUSizeپ+inW.toUSizeپ<=Wٽ:=by rw [Za _ א,Za _ א];omega have hw1:(j*inW).toUSizeپ+inW.toUSizeپ<Λ:=by rw [Za _ א,Za _ א];have:=τ;omega have hW2:((j+1)*inW).toUSizeپ+inW.toUSizeپ<=Wٽ:=by rw [Za _ א,Za _ א];omega have hw2:((j+1)*inW).toUSizeپ+inW.toUSizeپ<Λ:=by rw [Za _ א,Za _ א];have:=τ;omega have hW3:((j+2)*inW).toUSizeپ+inW.toUSizeپ<=Wٽ:=by rw [Za _ א,Za _ א];omega have hw3:((j+2)*inW).toUSizeپ+inW.toUSizeپ<Λ:=by rw [Za _ א,Za _ א];have:=τ;omega have hW4:((j+2+1)*inW).toUSizeپ+inW.toUSizeپ<=Wٽ:=by rw [Za _ א,Za _ א];omega have hw4:((j+2+1)*inW).toUSizeپ+inW.toUSizeپ<Λ:=by rw [Za _ א,Za _ א];have:=τ;omega YS6c4 (λ r1 r2 r3 r4=>((if r1<߿ then r1.toUInt32 else Yai X W b inW i j,if r2<߿ then r2.toUInt32 else Yai X W b inW i (j+1)),(if r3<߿ then r3.toUInt32 else Yai X W b inW i (j+2),if r4<߿ then r4.toUInt32 else Yai X W b inW i (j+2+1)))) q X W (i*inW).toUSize (j*inW).toUSize ((j+1)*inW).toUSize ((j+2)*inW).toUSize ((j+2+1)*inW).toUSize inWٿ hX hW1 hW2 hW3 hW4 hx hw1 hw2 hw3 hw4 lo1 lo2 lo3 lo4 ((lo1پ:ٴ)-298) ((lo2پ:ٴ)-298) ((lo3پ:ٴ)-298) ((lo4پ:ٴ)-298) bw1 bw2 bw3 bw4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 else ((YaU X W b inW i j bx bv1,YaU X W b inW i (j+1) bx bv2),(YaU X W b inW i (j+2) bx bv3,YaU X W b inW i (j+2+1) bx bv4)) @[inline] def QPac4 (X:ؽ δ) (P:ؽ ٳ) (I:ؽ ؼ) (W b:ؽ δ) (inW i j:ٳ) (bx bv1 bv2 bv3 bv4:ؼ):(δ × δ) × (δ × δ):= if Pٽ=0/\1<=inW then YaUc4 X W b inW i j bx bv1 bv2 bv3 bv4 else ((QPa X P I W b inW i j bx bv1,QPa X P I W b inW i (j+1) bx bv2),(QPa X P I W b inW i (j+2) bx bv3,QPa X P I W b inW i (j+2+1) bx bv4)) @[specialize] def Yak4 (c hw:ٳ) (f:ٳ -> ٳ -> δ) (f4:ٳ -> ٳ -> (δ × δ) × (δ × δ)) (d4:ٳ -> ف) (ch:ٳ) (acc:ؽ δ):ؽ δ:= if ch ػ -> ػ -> ػ -> β) (n:ؾ) (f:(k:ؾ) -> k (ػ × ػ) × (ػ × ػ)) (B1 B2 B3 B4:ػ) (bw1 bw2 bw3 bw4:ؼ) (h1 l1 h2 l2 h3 l3 h4 l4:ػ) (k:ؾ):β:= if h:k>>63)) h1 l1 0 λ v2 v1 v0 c'=>YD v2 v1 v0 c' ((B1پ:ٴ)-298)) (YL B2 ζ bw2 ((0:ػ)-(h2>>>63)) h2 l2 0 λ v2 v1 v0 c'=>YD v2 v1 v0 c' ((B2پ:ٴ)-298)) (YL B3 ζ bw3 ((0:ػ)-(h3>>>63)) h3 l3 0 λ v2 v1 v0 c'=>YD v2 v1 v0 c' ((B3پ:ٴ)-298)) (YL B4 ζ bw4 ((0:ػ)-(h4>>>63)) h4 l4 0 λ v2 v1 v0 c'=>YD v2 v1 v0 c' ((B4پ:ٴ)-298)) termination_by nپ-kپ decreasing_by exact ZI n k h @[inline] def QPcD (X:ؽ δ) (P:ؽ ٳ) (I:ؽ ؼ) (W b:ؽ δ) (inW i J:ٳ) (bx bv:ؼ):ف:=decide (Pٽ=2*inW/\Iٽ=0/\i*inW+inW<=Xٽ/\J*inW+inW<=Wٽ/\i*inW+inW<=ހ /\ J*inW+inW<=ހ/\inW<ށ/\(bx&&&ޅ)≠255/\(bv&&&ޅ)≠255 /\ Yk (bx>>>16)<=Yk (bx&&&ޅ)/\Yk (bv>>>16)<=Yk (bv&&&ޅ)/\(QYF bx).toNat+(QYF bv).toNat<=15 /\ θ (b[J]!)≠255/\(Yf (b[J]!)=0\/(Yk (bx>>>16)+Yk (bv>>>16)<=Yd ζ+Yd (b[J]!)/\Yd ζ+Yd (b[J]!)-(Yk (bx>>>16)+Yk (bv>>>16))<80))/\(1:ػ)<=Yk (bv>>>16)) @[inline] def QPad4 (X:ؽ δ) (P:ؽ ٳ) (I:ؽ ؼ) (W b:ؽ δ) (inW i j:ٳ) (bx bv1 bv2 bv3 bv4:ؼ):(δ × δ) × (δ × δ):= if h:QPcD X P I W b inW i j bx bv1=true/\QPcD X P I W b inW i (j+1) bx bv2=true/\QPcD X P I W b inW i (j+2) bx bv3=true/\QPcD X P I W b inW i (j+2+1) bx bv4=true then have g:Pٽ=2*inW/\j*inW+inW<=Wٽ/\(j+1)*inW+inW<=Wٽ/\(j+2)*inW+inW<=Wٽ/\(j+2+1)*inW+inW<=Wٽ/\j*inW+inW<=ހ/\(j+1)*inW+inW<=ހ/\(j+2)*inW+inW<=ހ/\(j+2+1)*inW+inW<=ހ/\inW<ށ:=by simp only [QPcD,decide_eq_true_eq] at h;omega let xm:=Yk (bx>>>16);let wm1:=Yk (bv1>>>16);let wm2:=Yk (bv2>>>16);let wm3:=Yk (bv3>>>16);let wm4:=Yk (bv4>>>16) let wa1:=(j*inW).toUSize;let wa2:=((j+1)*inW).toUSize;let wa3:=((j+2)*inW).toUSize;let wa4:=((j+2+1)*inW).toUSize QYc4 (λ r1 r2 r3 r4=>((if r1<߿ then r1.toUInt32 else Yai X W b inW i j,if r2<߿ then r2.toUInt32 else Yai X W b inW i (j+1)),(if r3<߿ then r3.toUInt32 else Yai X W b inW i (j+2),if r4<߿ then r4.toUInt32 else Yai X W b inW i (j+2+1)))) inWٿ (λ k hk=> let p:=(P.uget (k+k) (by have:=υ.mp hk;rw [Za _ א] at this;rw [Zc _ _ (by have:=τ;omega)];omega)).toUInt64-ބ let w1:=W.uget (wa1+k) (by have:=υ.mp hk;rw [Za _ א] at this;simp only [wa1];rw [Zc _ _ (by rw [Za _ א];have:=τ;omega),Za _ א];omega);let e1:=Yf w1<<<((θ w1).toUInt64-(wm1+1));let m1:=(0:ػ)-(w1>>>31).toUInt64;let q1:=((p*e1)^^^m1)-m1 let w2:=W.uget (wa2+k) (by have:=υ.mp hk;rw [Za _ א] at this;simp only [wa2];rw [Zc _ _ (by rw [Za _ א];have:=τ;omega),Za _ א];omega);let e2:=Yf w2<<<((θ w2).toUInt64-(wm2+1));let m2:=(0:ػ)-(w2>>>31).toUInt64;let q2:=((p*e2)^^^m2)-m2 let w3:=W.uget (wa3+k) (by have:=υ.mp hk;rw [Za _ א] at this;simp only [wa3];rw [Zc _ _ (by rw [Za _ א];have:=τ;omega),Za _ א];omega);let e3:=Yf w3<<<((θ w3).toUInt64-(wm3+1));let m3:=(0:ػ)-(w3>>>31).toUInt64;let q3:=((p*e3)^^^m3)-m3 let w4:=W.uget (wa4+k) (by have:=υ.mp hk;rw [Za _ א] at this;simp only [wa4];rw [Zc _ _ (by rw [Za _ א];have:=τ;omega),Za _ א];omega);let e4:=Yf w4<<<((θ w4).toUInt64-(wm4+1));let m4:=(0:ػ)-(w4>>>31).toUInt64;let q4:=((p*e4)^^^m4)-m4 ((q1,q2),(q3,q4))) (xm+wm1) (xm+wm2) (xm+wm3) (xm+wm4) b[j]! b[j+1]! b[j+2]! b[j+2+1]! 0 0 0 0 0 0 0 0 0 else ((QPa X P I W b inW i j bx bv1,QPa X P I W b inW i (j+1) bx bv2),(QPa X P I W b inW i (j+2) bx bv3,QPa X P I W b inW i (j+2+1) bx bv4)) @[inline] def QPsS (X:ؽ δ) (P:ؽ ٳ) (I:ؽ ؼ) (W b:ؽ δ) (inW i J:ٳ) (bx bv:ؼ):ف:=decide (Pٽ=2*Iٽ/\Iٽ≠0/\Iٽ<=inW/\i*inW+inW<=Xٽ/\J*inW+inW<=Wٽ/\i*inW+inW<=ހ /\ J*inW+inW<=ހ/\inW<ށ/\(bx&&&ޅ)≠255/\(bv&&&ޅ)≠255 /\ Yk (bx>>>16)<=Yk (bx&&&ޅ)/\Yk (bv>>>16)<=Yk (bv&&&ޅ)/\(QYF bx).toNat+(QYF bv).toNat<=15 /\ θ (b[J]!)≠255/\(Yf (b[J]!)=0\/(Yk (bx>>>16)+Yk (bv>>>16)<=Yd ζ+Yd (b[J]!)/\Yd ζ+Yd (b[J]!)-(Yk (bx>>>16)+Yk (bv>>>16))<80))/\(1:ػ)<=Yk (bv>>>16)) @[inline] def QPas4 (X:ؽ δ) (P:ؽ ٳ) (I:ؽ ؼ) (W b:ؽ δ) (inW i j:ٳ) (bx bv1 bv2 bv3 bv4:ؼ):(δ × δ) × (δ × δ):= if h:QPsS X P I W b inW i j bx bv1=true/\QPsS X P I W b inW i (j+1) bx bv2=true/\QPsS X P I W b inW i (j+2) bx bv3=true/\QPsS X P I W b inW i (j+2+1) bx bv4=true then have g:Pٽ=2*Iٽ/\Iٽ<=inW/\j*inW+inW<=Wٽ/\(j+1)*inW+inW<=Wٽ/\(j+2)*inW+inW<=Wٽ/\(j+2+1)*inW+inW<=Wٽ/\j*inW+inW<=ހ/\(j+1)*inW+inW<=ހ/\(j+2)*inW+inW<=ހ/\(j+2+1)*inW+inW<=ހ/\inW<ށ:=by simp only [QPsS,decide_eq_true_eq] at h;omega let xm:=Yk (bx>>>16);let wm1:=Yk (bv1>>>16);let wm2:=Yk (bv2>>>16);let wm3:=Yk (bv3>>>16);let wm4:=Yk (bv4>>>16) let wa1:=(j*inW).toUSize;let wa2:=((j+1)*inW).toUSize;let wa3:=((j+2)*inW).toUSize;let wa4:=((j+2+1)*inW).toUSize let iw:=(inW-1).toUInt32 QYc4 (λ r1 r2 r3 r4=>((if r1<߿ then r1.toUInt32 else Yai X W b inW i j,if r2<߿ then r2.toUInt32 else Yai X W b inW i (j+1)),(if r3<߿ then r3.toUInt32 else Yai X W b inW i (j+2),if r4<߿ then r4.toUInt32 else Yai X W b inW i (j+2+1)))) Iٽٿ (λ k hk=> let u:=I.uget k (by have:=υ.mp hk;rw [Za _ א] at this;omega) let p:=(P.uget (k+k) (by have:=υ.mp hk;rw [Za _ א] at this;rw [Zc _ _ (by have:=τ;omega)];omega)).toUInt64-ބ let w1:=W.uget (wa1+(min u iw).toUSize) (by have:=υ.mp hk;rw [Za _ א] at this;have:=(R8 u inW א).1;simp only [wa1,iw] at *;rw [Zc _ _ (by rw [Za _ א,AI];have:=τ;omega),Za _ א,AI];omega);let e1:=Yf w1<<<((θ w1).toUInt64-(wm1+1));let m1:=(0:ػ)-(w1>>>31).toUInt64;let q1:=((p*e1)^^^m1)-m1 let w2:=W.uget (wa2+(min u iw).toUSize) (by have:=υ.mp hk;rw [Za _ א] at this;have:=(R8 u inW א).1;simp only [wa2,iw] at *;rw [Zc _ _ (by rw [Za _ א,AI];have:=τ;omega),Za _ א,AI];omega);let e2:=Yf w2<<<((θ w2).toUInt64-(wm2+1));let m2:=(0:ػ)-(w2>>>31).toUInt64;let q2:=((p*e2)^^^m2)-m2 let w3:=W.uget (wa3+(min u iw).toUSize) (by have:=υ.mp hk;rw [Za _ א] at this;have:=(R8 u inW א).1;simp only [wa3,iw] at *;rw [Zc _ _ (by rw [Za _ א,AI];have:=τ;omega),Za _ א,AI];omega);let e3:=Yf w3<<<((θ w3).toUInt64-(wm3+1));let m3:=(0:ػ)-(w3>>>31).toUInt64;let q3:=((p*e3)^^^m3)-m3 let w4:=W.uget (wa4+(min u iw).toUSize) (by have:=υ.mp hk;rw [Za _ א] at this;have:=(R8 u inW א).1;simp only [wa4,iw] at *;rw [Zc _ _ (by rw [Za _ א,AI];have:=τ;omega),Za _ א,AI];omega);let e4:=Yf w4<<<((θ w4).toUInt64-(wm4+1));let m4:=(0:ػ)-(w4>>>31).toUInt64;let q4:=((p*e4)^^^m4)-m4 ((q1,q2),(q3,q4))) (xm+wm1) (xm+wm2) (xm+wm3) (xm+wm4) b[j]! b[j+1]! b[j+2]! b[j+2+1]! 0 0 0 0 0 0 0 0 0 else ((QPa X P I W b inW i j bx bv1,QPa X P I W b inW i (j+1) bx bv2),(QPa X P I W b inW i (j+2) bx bv3,QPa X P I W b inW i (j+2+1) bx bv4)) @[inline] def QPq4 (X:ؽ δ) (P:ؽ ٳ) (I:ؽ ؼ) (W b:ؽ δ) (inW i j:ٳ) (bx bv1 bv2 bv3 bv4:ؼ):(δ × δ) × (δ × δ):= if Pٽ=0 then QPac4 X P I W b inW i j bx bv1 bv2 bv3 bv4 else if Iٽ=0 then QPad4 X P I W b inW i j bx bv1 bv2 bv3 bv4 else QPas4 X P I W b inW i j bx bv1 bv2 bv3 bv4 set_option maxHeartbeats 1000000 in def YaV (rows inW outW:ٳ) (relu:ف) (X W b:ؽ δ):ؽ δ:= let BX:ؽ ؼ:=ڀ rows λ i=>Yc X inW i.val let BV:ؽ ؼ:=ڀ outW λ j=>Yc W inW j.val let P:ؽ (ؽ ٳ × ؽ ؼ):=if QPS inW BX BV then ڀ rows λ i=> if (QYF BX[i.val]!).toNat+(BV.foldl (λ (m:ػ) (bv:ؼ)=>max m (QYF bv)) 0).toNat>15 then (#[],#[]) else let I:=QPI inW (λ t=>X[i.val*inW+t]!) 0 (Ba inW) if 0X[i.val*inW+(I[m]!).toNat]!) (Yk (BX[i.val]! >>> 16)) 0 (Ba (2*Iٽ)),I) else (QPD inW (λ t=>X[i.val*inW+t]!) (Yk (BX[i.val]! >>> 16)) 0 (Ba (2*inW)),#[]) else Χ rows (#[],#[]) let F:=λ i j=>act relu (QPa X P[i]!.1 P[i]!.2 W b inW i j BX[i]! BV[j]!) let F4:=(λ i j=>let r:=QPq4 X P[i]!.1 P[i]!.2 W b inW i j BX[i]! BV[j]! BV[j+1]! BV[j+2]! BV[j+2+1]!;((act relu r.1.1,act relu r.1.2),(act relu r.2.1,act relu r.2.2))) let D4:=(λ i=>(P[i]!.1ٽ==0&&1<=inW)||(P[i]!.1ٽ==2*inW&&P[i]!.2ٽ==0)||(P[i]!.2ٽ!=0&&P[i]!.1ٽ==2*P[i]!.2ٽ)) if rows<2 then Yak4 rows outW F F4 D4 0 (AY (rows*outW)) else YT4l rows outW (λ i=>P[i]!.1ٽ==2*inW&&P[i+1]!.1ٽ==2*inW&&P[i+2]!.1ٽ==2*inW&&P[i+2+1]!.1ٽ==2*inW) (λ i j=> let r:=QPa4 X P[i]!.1 P[i+1]!.1 P[i+2]!.1 P[i+2+1]!.1 P[i]!.2 P[i+1]!.2 P[i+2]!.2 P[i+2+1]!.2 W b inW i j BX[i]! BX[i+1]! BX[i+2]! BX[i+2+1]! BV[j]! ((act relu r.1.1,act relu r.1.2),(act relu r.2.1,act relu r.2.2))) (λ i=>P[i]!.1ٽ==0&&P[i+1]!.1ٽ==0&&P[i+2]!.1ٽ==0&&P[i+2+1]!.1ٽ==0) (λ i j=> let r:=QPa4w X P[i]!.1 P[i+1]!.1 P[i+2]!.1 P[i+2+1]!.1 P[i]!.2 P[i+1]!.2 P[i+2]!.2 P[i+2+1]!.2 W b inW i j BX[i]! BX[i+1]! BX[i+2]! BX[i+2+1]! BV[j]! ((act relu r.1.1,act relu r.1.2),(act relu r.2.1,act relu r.2.2))) (λ i=>P[i]!.1ٽ==2*inW&&P[i+1]!.1ٽ==2*inW) (λ i j=> let r:=QPa2 X P[i]!.1 P[i+1]!.1 P[i]!.2 P[i+1]!.2 W b inW i j BX[i]! BX[i+1]! BV[j]! (act relu r.1,act relu r.2)) F F4 D4 0 (AY (rows*outW)) lemma Zq (k:ؼ):(Yk k)˧=k؎-1:=by unfold Yk;split_ifs with h;subst h;rfl;rw[AG,Dj _ _ (by rw[AJ];exact Dd.2 λ a=>h (ύ.1 a))];rfl lemma E6 (x y:ؼ):(Yk x+Yk y)˧=x؎-1+(y؎-1):=by rw[ξ,Zq,Zq];have:x؎<2^32:=AK _;have:y؎<2^32:=AK _;exact ν א lemma ZM (a:ؼ):(Yd ζ+Yd a)˧=γ ζ+γ a:=B6 ζ a lemma D7 (b d a:ؼ):(Yp b d a)˧<=((b>>>16)؎-1)+((d>>>16)؎-1) /\ (ε a≠0 -> (Yp b d a)˧<=γ ζ+γ a):=by have h:=E6 (b>>>16) (d>>>16);have j:=ZM a;unfold Yp;dsimp only;rw[E7 a];split_ifs with e;simp only[Ω,ϵ,decide_eq_false_iff_not,ת,Ψ]at e;omega;simp only[Ω,ϵ,decide_eq_false_iff_not,ת,Ψ,not_and,not_lt]at e;constructor;omega;intro g;have:=e g;omega lemma D6 (b d a:ؼ):((b&&&ޅ)؎-1)+((d&&&ޅ)؎-1)<=(Yu b d a)˧ /\ (ε a≠0 -> γ ζ+γ a<=(Yu b d a)˧):=by have h:=E6 (b&&&ޅ) (d&&&ޅ);have j:=ZM a;unfold Yu;dsimp only;rw[E7 a];split_ifs with e;simp only[Ω,ϵ,decide_eq_false_iff_not,ת,Ψ]at e;omega;simp only[Ω,ϵ,decide_eq_false_iff_not,ת,Ψ,not_and,not_lt]at e;constructor;omega;intro g;have:=e g;omega lemma Zo (a:ؼ) (L H:ٳ) (h:a؎=L*2^16+H) (hH:H<2^16):(a>>>16)؎=L/\(a&&&ޅ)؎=H:=by constructor;rw[Ϣ,show(16:ؼ)؎%32=16 from rfl,ψ,h];omega;rw[AH,show(ޅ:ؼ)؎=2^16-1 from rfl,ϡ,h];omega lemma O2 (X W b:ؽ δ) (a i j:ٳ):Yai X W b a i j=Γ (a+1) (λ t=>if t < a then X[i*a+t]! else ζ) (λ t=>if t < a then W[j*a+t]! else b[j]!):=by unfold Yai;rw[Zi] lemma Zp (A:ؽ δ) (a i:ٳ) (b:i*a+a<=Aٽ) (d:i*a+a<=ހ) : ∃ L H:ٳ,(Yc A a i)؎=L*2^16+H/\L<=511/\H<=255 /\ ∀ t,t < a -> L<=YR A[i*a+t]! /\ YM A[i*a+t]! <= H:=by have f:(i*a)۞؛=i*a:=Za _ א;have g:a۞؛=a:=Za _ א;unfold Yc;rw[dif_pos ⟨b,א⟩];obtain⟨L,H,e,h,c,-,-,j⟩:=W8 A (i*a)۞ a۞ (by rw[f,g];exact b) (by rw[f,g];have:=τ;omega) 0xFFFFFFFF 0 0 ג ד;refine⟨L,H,e,h,c,λt k=>?_⟩;have:=j t ג (by rw[g];exact k);rwa[f]at this lemma A9 (S:ٴ) (a:ػ) (c:ف) (b D:δ) (d:S=0 -> b=D) (e:D=ρ (S*2^a˧) (-298) c) : (if (if S=0 then ߿ else (ρ S ((a˧:ٴ)-298) false)܅)<߿ then (if S=0 then ߿ else (ρ S ((a˧:ٴ)-298) false)܅)՜ else b)=D:=by by_cases f:S=0;rw[if_pos f,if_neg ד,d f];rw[if_neg f,if_pos (by rw[Ψ];simpa using AK (ρ S ((a˧:ٴ)-298) false):(ρ S ((a˧:ٴ)-298) false)܅<߿),e,<-Aa,(by apply ύ.mp;simp:(ρ S ((a˧:ٴ)-298) false)܅՜=ρ S ((a˧:ٴ)-298) false)];unfold finishWord;rw[if_neg f,if_neg f,show(-298:ٴ)+(a˧:ٴ)=(a˧:ٴ)-298 by ring] lemma E8 (u p:ػ) (b:¬u122):p˧<=u˧/\u˧-p˧<=122:=by rw[Ψ]at b;have d:p˧<=u˧:=א;rw[gt_iff_lt,Ψ,Η _ _ (ϐ.2 d)]at a;exact⟨d,DZ.1 a⟩ lemma H4 {L r i:ٳ} (a:L<=r) (b:r<=i+1):L-1<=i:=א lemma H3 {m H i:ٳ} (a:m<=H) (b:i+1<=max m 1):i<=H-1:=א lemma ZQ {p u a b c d B:ٳ} {x w:δ} (h:p<=(a-1)+(b-1)) (j:(c-1)+(d-1)<=u) (k:u-p<=B) (e:a<=YR x/\YM x<=c) (f:b<=YR w/\YM w<=d) (g:ε x*ε w≠0):p<=γ x+γ w/\γ x+γ w<=p+B:= have l:=(Zb x).2.2.2 (left_ne_zero_of_mul g);have n:=(Zb w).2.2.2 (right_ne_zero_of_mul g);⟨h.trans (Cy (H4 e.1 l.1) (H4 f.1 n.1)),(Cy (H3 e.2 l.2) (H3 f.2 n.2)).trans (j.trans (BK.mp k))⟩ @[specialize] def YE (n:ؾ) (fx fw:(t:ؾ) -> t δ) (lo:ػ) (e:ٴ) (bx bw:ؼ) (w2 w1 w0 c:ػ) (k:ؾ):ػ:= if h:k YE n fx fw lo e bx bw v2 v1 v0 c' (k+1) else YL lo bx bw w2 w1 w0 c λ v2 v1 v0 c'=>YD v2 v1 v0 c' e termination_by nپ-kپ decreasing_by exact ZI n k h def Yr (fa fb:ٳ -> δ) (lo k:ٳ):ٳ -> ٴ | 0=>0 | r+1=>sv (fa k)*sv (fb k)*2^(γ (fa k)+γ (fb k)-lo)+Yr fa fb lo (k+1) r lemma H2 (n:ؾ) (l o:(t:ؾ) -> t δ) (f a:ٳ -> δ) (p:∀ t h,l t h=f t؛) (q:∀ t h,o t h=a t؛) (b:ػ) (e:ٴ) (g j:ؼ) (s:n؛<2^32) (r:ε g*ε j≠0 -> b˧<=γ g+γ j/\γ g+γ j k؛<=n؛ -> c˧<=k؛ -> (∀ t,k؛<=t -> t ε (f t)*ε (a t)≠0 -> b˧<=γ (f t)+γ (a t)/\γ (f t)+γ (a t) ((Yx z A B+c˧:ٳ):ٴ)%2^192=S0%2^192 -> S=S0+Yr f a b˧ k؛ (n؛-k؛)+sv g*sv j*2^(γ g+γ j-b˧) -> -2^191<=S -> S<2^191 -> YE n l o b e g j z A B c k=if S=0 then ߿ else (ρ S e false)܅:=by intro d;induction d<;>intro k z A B c S0 S C P K J ·rw[YE,dif_neg (υ.not.2 א)];obtain⟨u,v,w,x,E,-,F⟩:=Zr b g j z A B c (YD · · · · e) א r;rw[E,C,Yr];intro G H L M;apply ZV u v w x e S L M;rw[F,H,add_zero];exact DT _ G rename_i N;have D:=υ.2 (Al C);have y:=QK n k D;rw[YE,dif_pos D,p,q];obtain⟨u,v,w,x,E,O,F⟩:=Zr b (f k؛) (a k؛) z A B c (YE n l o b e g j · · · · (k+1)) א (J k؛ le_rfl (υ.1 D));rw[E,show n؛-k؛=(n؛-(k+1)؛)+1 by clear* -y C;omega,Yr,y];have I:=N (k+1) u v w x (S0+sv (f k؛)*sv (a k؛)*2^(γ (f k؛)+γ (a k؛)-b˧)) S (by clear* -y C;omega) (y▸υ.1 D) (y▸O.trans (Nat.succ_le_succ K)) (λ t Q=>J t א);exact λ G H=>I (F.trans (DT _ G)) (by rw[H,y];ring) lemma G4 (a b:ٳ -> δ) (d:ٳ):∀ (r k:ٳ),(∀ t,k<=t -> t ε (a t)*ε (b t)≠0 -> d<=γ (a t)+γ (b t)/\γ (a t)+γ (b t)<=d+122) -> -((r:ٴ)*2^170)<=Yr a b d k r/\Yr a b d k r<=(r:ٴ)*2^170:=by intro r;induction r<;>intro k h ·simp[Yr] rename_i e;obtain⟨f,g⟩:=ZL (a k) (b k) d (h k le_rfl א);obtain⟨j,l⟩:=e (k+1) (λ t n o=>h t א א);rw[Yr];push_cast;constructor<;>linarith lemma Q6 (a b:ٳ -> δ) (K d:ٳ) (e f:ؼ):∀ r k,k+r<=K -> (∀ t,k<=t -> t ε (a t)*ε (b t)≠0 -> d<=γ (a t)+γ (b t)) -> Yo (λ t=>if tif tintro k j h ·simp[Yo,Yr] rename_i g;rw[Yo,Yr,g (k+1) א (λ t l n=>h t א א)];simp only[show k t δ) (e a:ٳ -> δ) (o:∀ t h,f t h=e t؛) (p:∀ t h,g t h=a t؛) (b:ؼ) (d:ػ) (hK:K<ށ) (q:∀ t,t θ (e t)≠255) (r:∀ t,t θ (a t)≠255) (s:θ b≠255) (j:∀ t,t ε (e t)*ε (a t)≠0 -> d˧<=γ (e t)+γ (a t)/\γ (e t)+γ (a t)<=d˧+122) (l:ε ζ*ε b≠0 -> d˧<=γ ζ+γ b/\γ ζ+γ b<=d˧+122) (n:δ) (u:n=Γ (K+1) (λ t=>if tif tif tif tj t א v);have E:=ZL ζ b d˧ l;generalize z:Yr e a d˧ 0 K+sv ζ*sv b*2^(γ ζ+γ b-d˧)=Srel;rw[H2 K۞ f g e a o p d ((d˧:ٴ)-298) ζ b א (λ h=>by have:=l h;omega) K 0 0 0 0 0 0 Srel (by simp[x]) ג ג (λ t _ y v=>by have:=j t א v;omega) (by simp[Yx]) (by rw[<-z,x];simp) א א];exact A9 _ _ _ _ _ (λ _=>u) (by rw[Zy (K+1) _ _ (by intro k F;by_cases w:ksimp only[w,ר,ש];exact⟨q k w,r k w⟩;exact⟨ד,s⟩:∀k,kθ ((λ t=>if tif t(j t א v).1)];simp;rw[ZA oneW b d˧ (λ h=>(l h).1),<-z];ring:Γ (K+1) (λ t=>if tif tif tif tX[a+t]!) (λ t=>W[b+t]!) d k r:=by intro r;induction r;intro;rfl;next r e=>intro;rw[YB,Yr,e] lemma R7 (X W:ؽ δ) (a b n:ؾ) (f:a؛+n؛<=Xٽ) (g:b؛+n؛<=Wٽ) (j:a؛+n؛<Λ) (l:b؛+n؛<Λ) (o:ػ) (e:ٴ) (p:ؼ):∀ d (k:ؾ) (r s u c:ػ),n؛-k؛=d -> YS X W a b n f g j l o e p r s u c k=YE n (λ t h=>X.uget (a+t) (A4 X a n t f j h)) (λ t h=>W.uget (b+t) (A4 W b n t g l h)) o e ζ p r s u c k:=by intro d;induction d<;>intro k r s u c v ·have q:¬k f˧<=γ ζ+γ g/\γ ζ+γ g k؛<=n؛ -> c˧<=k؛ -> (∀ t,k؛<=t -> t ε X[a؛+t]! * ε W[b؛+t]! ≠ 0 -> f˧<=γ X[a؛+t]! + γ W[b؛+t]! /\ γ X[a؛+t]! + γ W[b؛+t]! < f˧+128) -> ((Yx s u v+c˧:ٳ):ٴ)%2^192=S0%2^192 -> S=S0+YB X W a؛ b؛ f˧ k؛ (n؛-k؛)+sv ζ*sv g*2^(γ ζ+γ g-f˧) -> -2^191<=S -> S<2^191 -> YS X W a b n j l o p f e g s u v c k=if S=0 then ߿ else (ρ S e false)܅:=by intro d k s u v c S0 S w x y z A B C D;rw[R7 X W a b n j l o p f e g _ k s u v c rfl];exact H2 n _ _ (λ t=>X[a؛+t]!) (λ t=>W[b؛+t]!) (λ t h=>B3 X a t _ (by have:=υ.mp h;omega)) (λ t h=>B3 W b t _ (by have:=υ.mp h;omega)) f e ζ g q r d k s u v c S0 S w x y z A (by rw[B,S2]) C D lemma W6 (X W:ؽ δ) (a b d:ٳ):∀ (r k:ٳ),(∀ t,k<=t -> t ε X[a+t]! * ε W[b+t]! ≠ 0 -> d<=γ X[a+t]! + γ W[b+t]! /\ γ X[a+t]! + γ W[b+t]! <= d+122) -> -((r:ٴ)*2^170)<=YB X W a b d k r/\YB X W a b d k r<=(r:ٴ)*2^170:=λ r k h=>S2 X W a b d r k▸G4 _ _ d r k h lemma L8 (X W:ؽ δ) (a i j:ٳ) (b:ؼ) (d:ػ) (e:(i*a)۞؛+a۞؛<=Xٽ) (f:(j*a)۞؛+a۞؛<=Wٽ) (g:(i*a)۞؛+a۞؛<Λ) (k:(j*a)۞؛+a۞؛<Λ) (n:(i*a)۞؛=i*a) (o:(j*a)۞؛=j*a) (x:a۞؛=a) (p:a<ށ) (q:∀ t,t < a -> θ X[i*a+t]! ≠ 255) (r:∀ t,t < a -> θ W[j*a+t]! ≠ 255) (s:θ b≠255) (u:∀ t,t < a -> ε X[i*a+t]! * ε W[j*a+t]! ≠ 0 -> d˧<=γ X[i*a+t]! + γ W[j*a+t]! /\ γ X[i*a+t]! + γ W[j*a+t]! <= d˧+122) (v:ε ζ*ε b≠0 -> d˧<=γ ζ+γ b/\γ ζ+γ b<=d˧+122) (l:δ) (w:l=Γ (a+1) (λ t=>if t < a then X[i*a+t]! else ζ) (λ t=>if t < a then W[j*a+t]! else b)) : (if YS X W (i*a)۞ (j*a)۞ a۞ e f g k d ((d˧:ٴ)-298) b 0 0 0 0 0<߿ then (YS X W (i*a)۞ (j*a)۞ a۞ e f g k d ((d˧:ٴ)-298) b 0 0 0 0 0)՜ else l) = Γ (a+1) (λ t=>if t < a then X[i*a+t]! else ζ) (λ t=>if t < a then W[j*a+t]! else b):=by rw[R7 X W _ _ _ e f g k d _ b _ 0 0 0 0 0 rfl];exact L7 a _ _ (λ t=>X[i*a+t]!) (λ t=>W[j*a+t]!) (λ t h=>by rw[B3 X _ t _ (by have:=υ.mp h;omega),n]) (λ t h=>by rw[B3 W _ t _ (by have:=υ.mp h;omega),o]) b d p q r s u v l w lemma ZcB (X W b:ؽ δ) (a i j:ٳ):YaU X W b a i j (Yc X a i) (Yc W a j)=Γ (a+1) (λ t=>if t < a then X[i*a+t]! else ζ) (λ t=>if t < a then W[j*a+t]! else b[j]!):=by have F:=O2 X W b a i j;unfold YaU;split;swap;exact F;obtain⟨G,H,I,J,K⟩:=‹_∧_›;have w:=Za (i*a) א;have x:=Za (j*a) א;have p:=Za a א;obtain⟨Lx,Hx,y,Z,L,r⟩:=Zp X a i G I;obtain⟨Lv,Hv,z,_,M,s⟩:=Zp W a j H J;generalize Yc X a i=f at y⊢;generalize Yc W a j=g at z⊢;obtain⟨N,A⟩:=Zo f Lx Hx y א;obtain⟨O,B⟩:=Zo g Lv Hv z א;obtain⟨k,u⟩:=D7 f g b[j]!;obtain⟨l,v⟩:=D6 f g b[j]!;rw[N,O]at k;rw[A,B]at l;dsimp only;split;exact F;rename_i C;simp only[Ϸ,ת,not_or]at C;obtain⟨⟨⟨⟨P,Q⟩,R⟩,S⟩,T⟩:=C;obtain⟨Y,D⟩:=E8 _ _ S T;by_cases n:Yu f g b[j]! -Yp f g b[j]!<=63;rw[if_pos n,I6 _ X W (i*a)۞ (j*a)۞ a۞ _ _ _ _ (Yp f g b[j]!) _ b[j]! א _ (λq=>ϐ.1 (of_decide_eq_true q)) (ϐ.1 n) (λt d o=>by rw[w,x]at o⊢;exact ZQ k l (Η _ _ (ϐ.2 Y)).ge (r t (p▸d)) (s t (p▸d)) o) a۞؛ 0 0 0 0 0 ג (λ_=>⟨rfl,ג⟩)];swap;rw[if_neg n];all_goals exact L8 X W a i j b[j]! (Yp f g b[j]!) _ _ _ _ w x p K (λt d=>(Zb _).2.2.1 ((r t d).2.trans_lt (L.lt_of_ne λh=>P (ύ.1 (A.trans h))))) (λt d=>(Zb _).2.2.1 ((s t d).2.trans_lt (M.lt_of_ne λh=>Q (ύ.1 (B.trans h))))) R (λt d=>ZQ k l D (r t d) (s t d)) (λo=>⟨u (right_ne_zero_of_mul o),(v (right_ne_zero_of_mul o)).trans (BK.1 D)⟩) _ F section open ExactRuntime FloatLib.Floats.Formats.BinaryInterchange FloatLib.Floats FloatLib.Numerics open Model open RationalBinary (floorLog2 scaleByPowerOfTwo scaleByPowerOfTwo_snd_ne_zero) open FloatLib.Numerics (binaryRadix Radix.toReal) end section open ExactRuntime FloatLib.Floats.Formats.BinaryInterchange FloatLib.Floats FloatLib.Floats.Formats.Flocq open Float.Model.UnpackedFloat open FloatLib.Numerics (binaryRadix Radix.toReal) end section open ExactRuntime FloatLib.Floats.Formats.BinaryInterchange FloatLib.Floats open Float.Model.UnpackedFloat end section open ExactRuntime FloatLib.Floats.Formats.BinaryInterchange FloatLib.Floats end def Ye (q:ػ):ٴ:=(qپ:ٴ)-2^64*(qپ/2^63:ٳ) termination_by nپ-kپ decreasing_by exact ZI n k h lemma E2 (w:ؼ) (m:ػ) (k:ٳ) (a:k<=39) (h:ε w=0\/(m˧<=γ w/\γ w-m˧<=k)) : (Yf w<<<(Yd w-m))˧=ε w*2^(γ w-m˧) /\ ε w*2^(γ w-m˧)<2^(24+k):=by rcases h with b|⟨e,f⟩ . have:Yf w=0:=σ.mp (by rw[Zk,b];rfl);rw[this,b];simp . have g:(Yd w-m)˧=γ w-m˧:=by rw[Η _ _ (ϐ.mpr (by rwa[Zf])),Zf] have j:=Ϛ w;have d:ε w*2^(γ w-m˧)<2^(24+k):=calc _<2^24*2^(γ w-m˧):=Aj j (Δ _) _<=2^24*2^k:=Ci _ (Ι ב f) _=2^(24+k):=by rw[pow_add] refine⟨?_,d⟩;rw[ό,g,Zk,ν (show γ w-m˧<64 by omega),Α];exact ν (d.trans_le (Ι ב א)) lemma K8 (p:ػ) (a:ف) (b:p˧<2^63):Ye (if a then (0:ػ)-p else p)=if a then -(p˧:ٴ) else p˧:=by unfold Ye;cases a;simp only[φ,ש];rw[Υ b];simp;simp only[ר];rw[Τ];simp only[Ϝ,ϑ];by_cases d:p˧=0;simp[d];omega lemma QE {x y m:ٴ} (k:ٴ) (h:x=y+m*k):x%m=y%m:=by rw[h,CA] lemma T2 (V:ٳ) (a:ٴ) (h:(V:ٴ)%2^128=a%2^128) (b:V<2^128) (d : -2^127<=a) (e:a<2^127) : (((2^64-V/2^127)%2^64*2^128+V:ٳ):ٴ)%2^192=a%2^192:=by obtain⟨c,f⟩:=Int.ModEq.dvd h;clear h;exact QE (V/2^127:ٳ) א lemma E9 (a b c:ػ) (d:ٴ) (e:c˧=0) (h:((a˧*2^64+b˧:ٳ):ٴ)%2^128=d%2^128) (f : -2^127<=d) (g:d<2^127) : ((Yx ((0:ػ)-(a>>>63)) a b+c˧:ٳ):ٴ)%2^192=d%2^192:=by have n:=b܉;have o:=a܉;unfold Yx;rw[(by rw[Τ,Ξ];simp[ψ]:((0:ػ)-(a>>>63))˧=(2^64-a˧/2^63)%2^64),e,ϑ,BU,(א:a˧/2^63=(a˧*2^64+b˧)/2^127)];exact T2 _ d h (א:a˧*2^64+b˧<2^128) f g lemma K7 (a:ؼ) (b:ػ) (d:Yf a=0\/(b<=Yd ζ+Yd a/\Yd ζ+Yd a-b<80)) : ε ζ*ε a≠0 -> b˧<=γ ζ+γ a/\γ ζ+γ a<=b˧+79:=by intro f;obtain⟨e,j⟩:=d.resolve_left λh=>f (by rw[<-Zk a,h];simp);have k:=ϐ.mp e;have l:=Ψ.mp j;rw[ZM]at k;rw[Η _ _ e,ZM]at l;have:(80:ػ)˧=80:=rfl;constructor<;>omega lemma D8 (d a e b:ػ):((((d+e+(if a+brename_i h<;>rw[Ψ,ξ]at h<;>simp only[ξ,Bc,Nat.mod_add_mod]<;>push_cast<;>omega lemma S7 (a:ػ):((((0:ػ)-(a>>>63))˧*2^64+a˧:ٳ):ٴ)%2^128=Ye a%2^128:=by have:=a܉;unfold Ye;simp only[Τ];norm_num;omega lemma A2 {α:Type} [Inhabited α] (A:ؽ α) (i:ؾ) (h:i؛>>63))˧*2^64+q˧:ٳ):ٴ)%2^128=Ye q%2^128:=S7 q lemma QZb (w:ؼ):((w>>>31)܅)˧=if η w then 1 else 0:=by have h:=D4 w 0;rwa[EE,show η 0=false from rfl,EM]at h lemma C9 (x w:ؼ) (b a:ػ) (d f:ٳ) (l:d+f<=15) (j:ε x=0\/(b˧<=γ x/\γ x-b˧<=d)) (g:ε w=0\/(a˧<=γ w/\γ w-a˧<=f)) (k:1<=a) : Ye (((QPb x b (η w))߸-ބ)*(Yf w<<<((θ w)܅-(a+1)))) = sv x*sv w*2^(γ x+γ w-(b˧+a˧)) /\ -2^63grind:∀c:ف,((if c then ބ-M else ބ+M)˧߸-ބ)*D=if c then 0-M*D else M*D),show(η x !=η w)=Ζ (η x) (η w) by cases η x<;>cases η w<;>rfl];generalize M*D=p at n⊢;have Zk:(if Ζ (η x) (η w)then-(p˧:ٴ)else p˧)=sv x*sv w*2^(γ x+γ w-(b˧+a˧)):=by rw[n,<-Zn];by_cases q:ε x*ε w=0;rcases Ax.mp q with h|h<;>simp[h];have B:=j.resolve_left (left_ne_zero_of_mul q);have C:=g.resolve_left (right_ne_zero_of_mul q);rw[(א:γ x+γ w-(b˧+a˧)=γ x-b˧+(γ w-a˧)),pow_add];split_ifs<;>push_cast<;>ring have E:(p˧:ٴ)<2^63:=by rw[n];exact_mod_cast o refine⟨(K8 p (Ζ (η x) (η w)) (by rw[n];omega)).trans Zk,?_,?_⟩<;>rw[<-Zk]<;>split_ifs<;>omega lemma C8 (X W:ؽ δ) (e g:ٳ) (n:ؾ) (f:(k:ؾ) -> k ػ) (a:ػ) (b:ؼ) (j:n؛<=ށ) (o:∀ t h,Ye (f t h)=sv X[e+t؛]!*sv W[g+t؛]!*2^(γ X[e+t؛]!+γ W[g+t؛]!-a˧) /\ -2^63<=Ye (f t h) /\ Ye (f t h)<=2^63) (l:ε ζ*ε b≠0 -> a˧<=γ ζ+γ b/\γ ζ+γ b<=a˧+122) : ∀ (d:ٳ) (k:ؾ) (p r:ػ) (S0 S:ٴ),n؛-k؛=d -> k؛<=n؛ -> ((p˧*2^64+r˧:ٳ):ٴ)%2^128=S0%2^128 -> -((k؛:ٴ)*2^63)<=S0 -> S0<=k؛*2^63 -> S=S0+YB X W e g a˧ k؛ (n؛-k؛)+sv ζ*sv b*2^(γ ζ+γ b-a˧) -> -2^191<=S -> S<2^191 -> QY6G n f a b p r k=if S=0 then ߿ else (ρ S ((a˧:ٴ)-298) false)܅:=by intro d;induction d<;>intro k p r S0 S s z A x y B C D;rw[QY6G,dif_neg (by rw[υ];exact DZ.2 (De.1 s))];obtain⟨I,J,K,L,M,-,v⟩:=Zr a ζ b _ p r 0 (YD · · · · ((a˧:ٴ)-298)) ג (λh=>⟨(l h).1,(l h).2.trans_lt ג⟩);rw[M];apply ZV I J K L _ S C D;rw[v,Ϫ,E9 p r 0 S0 rfl A (by clear*-x y z j;omega) (by clear*-x y z j;omega),<-Ϫ,B,s,YB];ring_nf;rename_i d N;have v:=Al s;have w:=υ.2 v;have u:=QK n k w;have E:n؛-(k+1)؛=d:=by rw[u,Cx,s,Cz] rw[QY6G,dif_pos w];dsimp only;obtain⟨F,G,H⟩:=o k w;generalize f k w=q at F G H⊢;refine N (k+1) _ _ (S0+Ye q) S E (u▸v) ?_ (by clear*-u x G;omega) (by clear*-u y H;omega) ?_ C D;unfold QhiS;rw[D8,Ϫ,A,Qsx q,<-Ϫ];rw[B,s,YB,E,u,F];ring lemma C7 (A:ؽ δ) (a i c:ٳ) (e:i*a+a<=Aٽ) (f:i*a+a<=ހ) (g:(Yc A a i&&&ޅ)≠255) (b:Yk (Yc A a i>>>16)<=Yk (Yc A a i&&&ޅ)) (d:(QYF (Yc A a i))˧<=c) : ∀ t,t < a -> (ε A[i*a+t]! = 0\/((Yk (Yc A a i>>>16))˧<=γ A[i*a+t]!/\γ A[i*a+t]!-(Yk (Yc A a i>>>16))˧<=c)) /\ θ A[i*a+t]!≠255:=by obtain⟨L,H,o,-,hH,p⟩:=Zp A a i e f;obtain⟨q,k⟩:=Zo _ L H o א;have j:=Zq (Yc A a i>>>16);have h:=Zq (Yc A a i&&&ޅ);rw[q]at j;rw[k]at h;unfold QYF at d;rw[Η _ _ b,j,h]at d;have r:H≠255:=λ c=>g (ύ.mp (by rw[k,c];rfl));intro t s;obtain⟨-,-,u,v⟩:=Zb A[i*a+t]!;have:=p t s;refine⟨?_,u (Ρ this.2 (Nat.lt_of_le_of_ne hH r))⟩;by_cases l:ε A[i*a+t]! =0;exact Ea l;have n:=v l;right;rw[j];exact⟨H4 this.1 n.1,(BZ (H3 this.2 n.2) _).trans d⟩ lemma R5 (X W b:ؽ δ) (a i j w x:ٳ) (d e:ؼ) (l o:ؽ δ) (r s:ٳ) (n:ؾ) (f:(k:ؾ) -> k ػ) (C:i*a+a<=Xٽ) (D:j*a+a<=Wٽ) (y:i*a+a<=ހ) (z:j*a+a<=ހ) (g:a<ށ) (E:w+x<=122) (F:n؛<=ށ) (G:YB l o r s ((Yk (d>>>16))+(Yk (e>>>16)))˧ 0 n؛=YB X W (i*a) (j*a) ((Yk (d>>>16))+(Yk (e>>>16)))˧ 0 a) (A:∀ t,t < a -> (ε X[i*a+t]! = 0\/((Yk (d>>>16))˧<=γ X[i*a+t]!/\γ X[i*a+t]!-(Yk (d>>>16))˧<=w)) /\ θ X[i*a+t]!≠255) (B:∀ t,t < a -> (ε W[j*a+t]! = 0\/((Yk (e>>>16))˧<=γ W[j*a+t]!/\γ W[j*a+t]!-(Yk (e>>>16))˧<=x)) /\ θ W[j*a+t]!≠255) (u:θ b[j]!≠255) (v:Yf b[j]! = 0\/(Yk (d>>>16)+Yk (e>>>16)<=Yd ζ+Yd b[j]!/\Yd ζ+Yd b[j]!-(Yk (d>>>16)+Yk (e>>>16))<80)) (H:∀ t h,Ye (f t h)=sv l[r+t؛]!*sv o[s+t؛]!*2^(γ l[r+t؛]!+γ o[s+t؛]!-((Yk (d>>>16))˧+(Yk (e>>>16))˧)) /\ -2^63<=Ye (f t h) /\ Ye (f t h)<=2^63) : (if QY6G n f (Yk (d>>>16)+Yk (e>>>16)) b[j]! 0 0 0<߿ then (QY6G n f (Yk (d>>>16)+Yk (e>>>16)) b[j]! 0 0 0)՜ else Yai X W b a i j) = Γ (a+1) (λ t=>if t < a then X[i*a+t]! else ζ) (λ t=>if t < a then W[j*a+t]! else b[j]!):=by have H':=Za (i*a) א;have I:=Za (j*a) א;have J:=Za a א;have L:=τ;have R:(Yk (d>>>16)+Yk (e>>>16))˧=(Yk (d>>>16))˧+(Yk (e>>>16))˧:=by rw[E6,Zq,Zq] have M:=K7 b[j]! _ v;have G':∀t,tε X[i*a+t]!*ε W[j*a+t]!≠0->(Yk (d>>>16)+Yk (e>>>16))˧<=γ X[i*a+t]!+γ W[j*a+t]!/\γ X[i*a+t]!+γ W[j*a+t]!<=(Yk (d>>>16)+Yk (e>>>16))˧+122:=by intro t N K;have:=(A t N).1.resolve_left (left_ne_zero_of_mul K);have:=(B t N).1.resolve_left (right_ne_zero_of_mul K);omega have T:=W6 X W (i*a) (j*a) _ a 0 (λ t _ h=>G' t א);have K:=ZL ζ b[j]! _ (λ c=>⟨(M c).1,א⟩);generalize O:YB X W (i*a) (j*a) (Yk (d>>>16)+Yk (e>>>16))˧ 0 a+sv ζ*sv b[j]!*(2:ٴ)^(γ ζ+γ b[j]!-(Yk (d>>>16)+Yk (e>>>16))˧)=S;have P:-2^191<=S:=א;have Q:S<2^191:=א;rw[C8 l o r s n f _ b[j]! F (by rwa[R]) א n؛ 0 0 0 0 S rfl ג ג ג ג (by rw[<-O,<-G];simp) P Q,<-W7 X W (i*a)۞ (j*a)۞ a۞ א א א א _ _ b[j]! א (λ c=>⟨(M c).1,א⟩) a 0 0 0 0 0 0 S J ג ג (λ t _ h=>by rw[H',I];have:=G' t א;omega) (by simp[Yx]) (by rw[<-O,H',I,J];simp) P Q];exact L8 X W a i j b[j]! _ _ _ _ _ H' I J g (λ t h=>(A t h).2) (λ t h=>(B t h).2) u G' א _ (O2 X W b a i j) lemma J1 (n:ٳ) (f:ٳ -> ؼ) (m:ػ):∀ k t (P:ؽ ٳ),n-t=k -> (QPD n f m t P)܍=P܍ ++ (Bd (2*t) (2*(n-t))).map λ u=>QPb (f (u/2)) m (u%2=1):=by intro k;induction k with |zero=>intro t P h;unfold QPD;rw[if_neg (DZ.2 (De.1 h))];simp[h] |succ k a=>intro t P h;unfold QPD;rw[if_pos (Al h)];dsimp only;have e:n-(t+1)=k:=(by rw[Cx,h,Cz]);rw[a (t+1) _ e,h,e,Nat.mul_succ 2 k,Ϩ,Ϩ];simp[Cf,show 2*(t+1)=2*t+1+1 from rfl] lemma D2 (n c:ٳ) (f:ٳ -> ؼ) (m:ػ):QPD n f m 0 (Ba c)=ڀ (2*n) λ u=>QPb (f (u܂/2)) m (u܂%2=1):=by apply ϻ;rw[J1 n f m _ 0 _ rfl];apply ϩ<;>simp lemma J0 (n:ٳ) (f:ٳ -> ؼ):∀ k t (I:ؽ ؼ),n-t=k -> (QPI n f t I)܍=I܍ ++ ((Bd t (n-t)).filter λ u=>Yf (f u)≠0).map (·.toUInt32):=by intro k;induction k with |zero=>intro t I h;unfold QPI;rw[if_neg א];simp[h] |succ k a=>intro t I h;unfold QPI;rw[if_pos א,a (t+1) _ א,(א:n-t=(n-(t+1))+1),Ϩ];split<;>simp[*] lemma R6 (X W:ؽ δ) (a b d:ٳ):∀ r k,YB X W a b d k r=((Bd k r).map λ u=>sv X[a+u]!*sv W[b+u]!*2^(γ X[a+u]!+γ W[b+u]!-d)).sum:=by intro r;induction r;intro;rfl;next r e=>intro;rw[YB,e,Ϩ];simp lemma QFL (L:List ٳ) (p:ٳ -> Prop) [DecidablePred p] (g:ٳ -> ٴ) (h:∀ x ∈ L,¬p x -> g x=0):((L.filter p).map g).sum=(L.map g).sum:=by induction L;rfl;next x L a=>simp only[List.filter_cons,CR,DV];split<;>simp_all lemma R9 (t:ؾ) (w:ؼ) (h:t؛<ށ):(t+t+(w>>>31).toUSize)؛=2*t؛+(w>>>31)؎/\(w>>>31)؎<2 /\ (2*t؛+(w>>>31)؎)/2=t؛/\decide ((2*t؛+(w>>>31)؎)%2=1)=η w:=by obtain⟨a,b⟩:=D0 t w h;have h:=QZb w;simp only[AG]at h;refine⟨a,b,?_⟩;rcases (η w).eq_false_or_eq_true with c|c<;>rw[c]at h⊢<;>simp only[↓reduceIte,φ,ת,decide_eq_false_iff_not]at h⊢<;>omega lemma I9 (X:ؽ δ) (P:ؽ ٳ) (I:ؽ ؼ) (W b:ؽ δ) (d i j:ٳ) (H:(Iٽ=0 -> ∀ t,t<2*d -> Pٽ=2*d -> P[t]! = QPb X[i*d+t/2]! (Yk (Yc X d i>>>16)) (t%2=1)) /\ (Iٽ≠0 -> I܍=((ϒ d).filter λ t=>Yf X[i*d+t]! ≠ 0).map (·.toUInt32) /\ ∀ u,u<2*Iٽ -> Pٽ=2*Iٽ -> P[u]! = QPb X[i*d+(I[u/2]!)؎]! (Yk (Yc X d i>>>16)) (u%2=1))) : QPa X P I W b d i j (Yc X d i) (Yc W d j) = Γ (d+1) (λ t=>if t < d then X[i*d+t]! else ζ) (λ t=>if t < d then W[j*d+t]! else b[j]!):=by unfold QPa;by_cases c:Iٽ=0<;>simp only[c,↓reduceDIte,↓reduceIte]<;>split<;>(try exact ZcB ..)<;>obtain⟨F,O,x,y,z,A,G,K,L,B,C,l,n,o,p⟩:=‹_∧_›<;>have r:=C7 X d i _ x z K B le_rfl<;>have s:=C7 W d j _ y A L C le_rfl<;>have e:∀u:ؾ,u؛by rw[Zc _ _ (by rw[Za _ א];have:=τ;omega),Za _ א] exact R5 X W b d i j _ _ _ _ X W _ _ _ _ x y z A G א (by rw[Za _ א];omega) (by rw[Za _ א]) r s n o (λt h=>by have f:t؛δ)m,m(I.map g)[0+m]! =g I[m]!:=λg m h=>by rw[Β,ح _ m (by rwa[CC]),CN,ح I m h] exact R5 X W b d i j _ _ _ _ (I.map λv=>X[i*d+v؎]!) (I.map λv=>W[j*d+v؎]!) 0 0 _ _ x y z A G א (by rw[Za _ א];omega) (by rw[Za _ א,R6,R6,<-Ca,<-Ca,<-QFL (ϒ d) (λt=>Yf X[i*d+t]!≠0) _ (λu _ h=>by simp only[sv,<-Zk,not_not.1 h,Ϝ,CP,neg_zero,ite_self,zero_mul])];apply congrArg;apply ϩ (by simp only[Ds,CM,<-Array.length_toList,D]);intro m E N;simp only[Ds,CM]at E;simp only[List.getElem_map,List.getElem_range,V _ _ E,ح I m E,<-DL,D,Cd,UInt32.toNat_ofNat_of_lt' ((BM.1 (List.mem_of_mem_filter (List.getElem_mem (Ds _▸N)))).trans (א:d<߿))]) r s n o (λt h=>by have f:t؛ ػ -> β) (n:ؾ) (F:(k:ؾ) -> k ػ × ػ) (j l:ػ) (a:ؼ) (b e f g:ػ) (k:ؾ) : QY6G2 kont n F j l a b e f g k=kont (QY6G n (λ k h=>(F k h).1) j a b e k) (QY6G n (λ k h=>(F k h).2) l a f g k):=by induction q:n؛-k؛generalizing b e f g k with |zero=> have o:¬k have o:k δ × δ):∀ k j (A B:ؽ δ),a-j=k -> (Yr2 a g j A B).1.toList=A܍++(Bd j (a-j)).map (λ t=>(g t).1)/\(Yr2 a g j A B).2.toList=B܍++(Bd j (a-j)).map (λ t=>(g t).2):=by intro k;induction k<;>intro j A B h<;>unfold Yr2 ·rw[if_neg א];simp[h] rename_i b;rw[if_pos א];dsimp only;obtain⟨d,e⟩:=b (j+1) (A.push (g j).1) (B.push (g j).2) א;rw[d,e,show a-j=(a-(j+1))+1 by omega,Ϩ];simp lemma QG4 {β:Type} (kont:ػ -> ػ -> ػ -> ػ -> β) (n:ؾ) (F:(k:ؾ) -> k (ػ × ػ) × (ػ × ػ)) (B1 B2 B3 B4:ػ) (a:ؼ) (h1 l1 h2 l2 h3 l3 h4 l4:ػ) (k:ؾ) : QY6G4 kont n F B1 B2 B3 B4 a h1 l1 h2 l2 h3 l3 h4 l4 k=kont (QY6G n (λ k h=>(F k h).1.1) B1 a h1 l1 k) (QY6G n (λ k h=>(F k h).1.2) B2 a h2 l2 k) (QY6G n (λ k h=>(F k h).2.1) B3 a h3 l3 k) (QY6G n (λ k h=>(F k h).2.2) B4 a h4 l4 k):=by induction E:n؛-k؛generalizing h1 l1 h2 l2 h3 l3 h4 l4 k with |zero=> have o:¬k have o:k ػ -> ػ -> ػ -> β) (q:ف) (X W:ؽ δ) (x1a x2a x3a x4a wa n:ؾ) (h1:x1aپ+nپ<=Xٽ) (h2:x2aپ+nپ<=Xٽ) (h3:x3aپ+nپ<=Xٽ) (h4:x4aپ+nپ<=Xٽ) (hW:waپ+nپ<=Wٽ) (g1:x1aپ+nپ<Λ) (g2:x2aپ+nپ<Λ) (g3:x3aپ+nپ<Λ) (g4:x4aپ+nپ<Λ) (hw:waپ+nپ<Λ) (lo1 lo2 lo3 lo4:ػ) (e1 e2 e3 e4:ٴ) (bw:ؼ) (a2 a1 a0 ac b2 b1 b0 bc c2 c1 c0 cc d2 d1 d0 dc:ػ) (k:ؾ) : YS64 kont q X W x1a x2a x3a x4a wa n h1 h2 h3 h4 hW g1 g2 g3 g4 hw lo1 lo2 lo3 lo4 e1 e2 e3 e4 bw a2 a1 a0 ac b2 b1 b0 bc c2 c1 c0 cc d2 d1 d0 dc k=kont (YS6 q X W x1a wa n h1 hW g1 hw lo1 e1 bw a2 a1 a0 ac k) (YS6 q X W x2a wa n h2 hW g2 hw lo2 e2 bw b2 b1 b0 bc k) (YS6 q X W x3a wa n h3 hW g3 hw lo3 e3 bw c2 c1 c0 cc k) (YS6 q X W x4a wa n h4 hW g4 hw lo4 e4 bw d2 d1 d0 dc k):=by induction E:n؛-k؛generalizing a2 a1 a0 ac b2 b1 b0 bc c2 c1 c0 cc d2 d1 d0 dc k with |zero=> have o:¬k have o:ksimp only[YL16,YL6,Bool.false_eq_true,↓reduceIte]<;>apply p<;>have:=QK n k o<;>omega lemma Y4U (X W b:ؽ δ) (inW i j:ٳ) (bx1 bx2 bx3 bx4 bv:ؼ) : YaU4 X W b inW i j bx1 bx2 bx3 bx4 bv=((YaU X W b inW i j bx1 bv,YaU X W b inW (i+1) j bx2 bv),(YaU X W b inW (i+2) j bx3 bv,YaU X W b inW (i+2+1) j bx4 bv)):=by unfold YaU4;dsimp only;split . rename_i h;obtain⟨A1,A2,A3,A4,B,C1,C2,C3,C4,D,E,F1,F2,F3,F4,G1,G2,G3,G4,K2,K3,K4⟩:=h;rw[Y64];unfold YaU;simp only[A1,A2,A3,A4,B,C1,C2,C3,C4,D,E,and_self,↓reduceDIte,F1,F2,F3,F4,G1,G2,G3,G4,K2,K3,K4,Bool.false_eq_true,↓reduceIte,decide_true] . rfl lemma QW4 (X:ؽ δ) (P1 P2 P3 P4:ؽ ٳ) (I1 I2 I3 I4:ؽ ؼ) (W b:ؽ δ) (inW i j:ٳ) (bx1 bx2 bx3 bx4 bv:ؼ) : QPa4w X P1 P2 P3 P4 I1 I2 I3 I4 W b inW i j bx1 bx2 bx3 bx4 bv=((QPa X P1 I1 W b inW i j bx1 bv,QPa X P2 I2 W b inW (i+1) j bx2 bv),(QPa X P3 I3 W b inW (i+2) j bx3 bv,QPa X P4 I4 W b inW (i+2+1) j bx4 bv)):=by unfold QPa4w;split . rename_i h;obtain⟨z1,z2,z3,z4,z5⟩:=h;rw[Y4U];have Z:∀(P:ؽ ٳ) (I:ؽ ؼ) (r:ٳ) (bx:ؼ),Pٽ=0->QPa X P I W b inW r j bx bv=YaU X W b inW r j bx bv:=λ P I r bx z=>by unfold QPa;dsimp only;rw[dif_neg (λ h=>by have:=h.1;rw[z]at this;split at this<;>omega)] rw[Z _ _ _ _ z1,Z _ _ _ _ z2,Z _ _ _ _ z3,Z _ _ _ _ z4] . rfl lemma H9 (a:ٳ) (g:ٳ -> (δ × δ) × (δ × δ)):∀ k j (A B C D:ؽ δ),a-j=k -> (Yr4 a g j A B C D).1.toList=A܍++(Bd j (a-j)).map (λ t=>(g t).1.1)/\(Yr4 a g j A B C D).2.1.toList=B܍++(Bd j (a-j)).map (λ t=>(g t).1.2)/\(Yr4 a g j A B C D).2.2.1.toList=C܍++(Bd j (a-j)).map (λ t=>(g t).2.1)/\(Yr4 a g j A B C D).2.2.2.toList=D܍++(Bd j (a-j)).map (λ t=>(g t).2.2):=by intro k;induction k<;>intro j A B C D h<;>unfold Yr4 ·rw[if_neg א];simp[h] rename_i b;rw[if_pos א];dsimp only;obtain⟨u,v,w,x⟩:=b (j+1) (A.push (g j).1.1) (B.push (g j).1.2) (C.push (g j).2.1) (D.push (g j).2.2) א;rw[u,v,w,x,show a-j=(a-(j+1))+1 by omega,Ϩ];simp lemma Yc64 {β:Type} (kont:ػ -> ػ -> ػ -> ػ -> β) (q:ف) (X W:ؽ δ) (xa w1a w2a w3a w4a n:ؾ) (hX:xaپ+nپ<=Xٽ) (hW1:w1aپ+nپ<=Wٽ) (hW2:w2aپ+nپ<=Wٽ) (hW3:w3aپ+nپ<=Wٽ) (hW4:w4aپ+nپ<=Wٽ) (hx:xaپ+nپ<Λ) (hw1:w1aپ+nپ<Λ) (hw2:w2aپ+nپ<Λ) (hw3:w3aپ+nپ<Λ) (hw4:w4aپ+nپ<Λ) (lo1 lo2 lo3 lo4:ػ) (e1 e2 e3 e4:ٴ) (bw1 bw2 bw3 bw4:ؼ) (a2 a1 a0 ac b2 b1 b0 bc c2 c1 c0 cc d2 d1 d0 dc:ػ) (k:ؾ) : YS6c4 kont q X W xa w1a w2a w3a w4a n hX hW1 hW2 hW3 hW4 hx hw1 hw2 hw3 hw4 lo1 lo2 lo3 lo4 e1 e2 e3 e4 bw1 bw2 bw3 bw4 a2 a1 a0 ac b2 b1 b0 bc c2 c1 c0 cc d2 d1 d0 dc k=kont (YS6 q X W xa w1a n hX hW1 hx hw1 lo1 e1 bw1 a2 a1 a0 ac k) (YS6 q X W xa w2a n hX hW2 hx hw2 lo2 e2 bw2 b2 b1 b0 bc k) (YS6 q X W xa w3a n hX hW3 hx hw3 lo3 e3 bw3 c2 c1 c0 cc k) (YS6 q X W xa w4a n hX hW4 hx hw4 lo4 e4 bw4 d2 d1 d0 dc k):=by induction E:n؛-k؛generalizing a2 a1 a0 ac b2 b1 b0 bc c2 c1 c0 cc d2 d1 d0 dc k with |zero=> have o:¬k have o:ksimp only[YL16,YL6,Bool.false_eq_true,↓reduceIte]<;>apply p<;>have:=QK n k o<;>omega lemma Yuc4 (X W b:ؽ δ) (inW i j:ٳ) (bx bv1 bv2 bv3 bv4:ؼ) : YaUc4 X W b inW i j bx bv1 bv2 bv3 bv4=((YaU X W b inW i j bx bv1,YaU X W b inW i (j+1) bx bv2),(YaU X W b inW i (j+2) bx bv3,YaU X W b inW i (j+2+1) bx bv4)):=by unfold YaUc4;dsimp only;split . rename_i h;obtain⟨A,B1,B2,B3,B4,C,G1,G2,G3,G4,E,F1,F2,F3,F4,H1,H2,H3,H4,K2,K3,K4⟩:=h;rw[Yc64];unfold YaU;simp only[A,B1,B2,B3,B4,C,G1,G2,G3,G4,E,and_self,↓reduceDIte,F1,F2,F3,F4,H1,H2,H3,H4,K2,K3,K4,Bool.false_eq_true,↓reduceIte,decide_true] . rfl lemma QWc4 (X:ؽ δ) (P:ؽ ٳ) (I:ؽ ؼ) (W b:ؽ δ) (inW i j:ٳ) (bx bv1 bv2 bv3 bv4:ؼ) : QPac4 X P I W b inW i j bx bv1 bv2 bv3 bv4=((QPa X P I W b inW i j bx bv1,QPa X P I W b inW i (j+1) bx bv2),(QPa X P I W b inW i (j+2) bx bv3,QPa X P I W b inW i (j+2+1) bx bv4)):=by unfold QPac4;split . rename_i h;obtain⟨z1,z2⟩:=h;rw[Yuc4];have Z:∀(r:ٳ) (bv:ؼ),QPa X P I W b inW i r bx bv=YaU X W b inW i r bx bv:=λ r bv=>by unfold QPa;dsimp only;rw[dif_neg (λ h=>by have:=h.1;rw[z1]at this;split at this<;>omega)] rw[Z,Z,Z,Z] . rfl lemma Zj4 (hw:ٳ) (f:ٳ -> ٳ -> δ) (f4:ٳ -> ٳ -> (δ × δ) × (δ × δ)) (d4:ٳ -> ف) (ch:ٳ) (u:∀ j,f4 ch j=((f ch j,f ch (j+1)),(f ch (j+2),f ch (j+2+1)))) : ∀ k j (n:ؽ δ),hw-j<=k -> Yaj4 hw f f4 d4 ch j n=Yaj hw f ch j n:=by have Y1:∀ m (n:ؽ δ),mYaj hw f ch m n=Yaj hw f ch (m+1) (n.push (f ch m)):=λ m n o=>by conv_lhs=>unfold Yaj;rw[if_pos o] intro k;induction k with |zero=>intro j n h;unfold Yaj4 Yaj;rw[if_neg א,if_neg א,if_neg א] |succ k p=> intro j n h;unfold Yaj4;split · rename_i o;split · dsimp only;rw[p _ _ (by omega),u,Y1 j n (by omega),Y1 (j+1) _ (by omega),Y1 (j+1+1) _ (by omega),Y1 (j+1+1+1) _ (by omega)] · rw[p _ _ (by omega),Y1 j n (by omega)] split · rename_i o o2;rw[p _ _ (by omega),Y1 j n o2] · unfold Yaj;rw[if_neg ‹_›] lemma Zk4 (c hw:ٳ) (f:ٳ -> ٳ -> δ) (f4:ٳ -> ٳ -> (δ × δ) × (δ × δ)) (d4:ٳ -> ف) (u:∀ i j,f4 i j=((f i j,f i (j+1)),(f i (j+2),f i (j+2+1)))) : ∀ k l (n:ؽ δ),c-l<=k -> Yak4 c hw f f4 d4 l n=Yak c hw f l n:=by intro k;induction k with |zero=>intro l n h;unfold Yak4 Yak;rw[if_neg א,if_neg א] |succ k p=>intro l n h;unfold Yak4 Yak;by_cases o:l ف) (f4:ٳ -> ٳ -> (δ × δ) × (δ × δ)) (e4:ٳ -> ف) (g4:ٳ -> ٳ -> (δ × δ) × (δ × δ)) (d:ٳ -> ف) (b:ٳ -> ٳ -> δ × δ) (f:ٳ -> ٳ -> δ) (f4c:ٳ -> ٳ -> (δ × δ) × (δ × δ)) (d4c:ٳ -> ف) (wc:∀ i j,f4c i j=((f i j,f i (j+1)),(f i (j+2),f i (j+2+1)))) (u:∀ i j,f4 i j=((f i j,f (i+1) j),(f (i+2) j,f (i+2+1) j))) (v:∀ i j,g4 i j=((f i j,f (i+1) j),(f (i+2) j,f (i+2+1) j))) (g:∀ i j,b i j=(f i j,f (i+1) j)) : ∀ k l (n:ؽ δ),c-l<=k -> YT4l c a d4 f4 e4 g4 d b f f4c d4c l n=Yak c a f l n:=by intro k;induction k with |zero=>intro l n h;unfold YT4l Yak;rw[if_neg א,if_neg א,if_neg א,if_neg א] |succ k p=> intro l n h have Y2:l+1Yak c a f l n=Yak c a f (l+2) (Yaj a f (l+1) 0 (Yaj a f l 0 n)):=λ o=>by conv_lhs=>unfold Yak;rw[if_pos (א:lYak c a f l n=Yak c a f (l+2+2) (Yaj a f (l+2+1) 0 (Yaj a f (l+2) 0 (Yaj a f (l+1) 0 (Yaj a f l 0 n)))):=λ o=>by rw[Y2 (by omega)];conv_lhs=>unfold Yak;rw[if_pos (א:l+2 ٳ -> (δ × δ) × (δ × δ),(∀ j,F l j=((f l j,f (l+1) j),(f (l+2) j,f (l+2+1) j))) -> (((n++(Yr4 a (F l) 0 (AY a) (AY a) (AY a) (AY a)).1)++(Yr4 a (F l) 0 (AY a) (AY a) (AY a) (AY a)).2.1)++(Yr4 a (F l) 0 (AY a) (AY a) (AY a) (AY a)).2.2.1)++(Yr4 a (F l) 0 (AY a) (AY a) (AY a) (AY a)).2.2.2=Yaj a f (l+2+1) 0 (Yaj a f (l+2) 0 (Yaj a f (l+1) 0 (Yaj a f l 0 n))):=λ F e=>by apply ϻ;obtain⟨q,r,s,t⟩:=H9 a (F l) _ 0 (AY a) (AY a) (AY a) (AY a) rfl;simp only[Array.toList_append,q,r,s,t,D3 a f (l+2+1) _ 0 _ rfl,D3 a f (l+2) _ 0 _ rfl,D3 a f (l+1) _ 0 _ rfl,D3 a f l _ 0 _ rfl,e];simp have Q2:(n++(Yr2 a (b l) 0 (AY a) (AY a)).1)++(Yr2 a (b l) 0 (AY a) (AY a)).2=Yaj a f (l+1) 0 (Yaj a f l 0 n):=by apply ϻ;obtain⟨q,r⟩:=H8 a (b l) _ 0 (AY a) (AY a) rfl;simp only[Array.toList_append,q,r,D3 a f (l+1) _ 0 _ rfl,D3 a f l _ 0 _ rfl,g];simp unfold YT4l;split · rename_i o;rw[Y4 o];split · dsimp only;rw[p _ _ (by omega)];congr 1;exact Q f4 (u l) split · dsimp only;rw[p _ _ (by omega)];congr 1;exact Q g4 (v l) rw[<-Y4 o,Y2 (by omega)];split · dsimp only;rw[p _ _ (by omega),Q2] · rw[p _ _ (by omega),Zj4 a f f4c d4c (l+1) (wc (l+1)) _ 0 _ le_rfl,Zj4 a f f4c d4c l (wc l) _ 0 _ le_rfl] split · rename_i o o2;rw[Y2 o2];split · dsimp only;rw[p _ _ (by omega),Q2] · rw[p _ _ (by omega),Zj4 a f f4c d4c (l+1) (wc (l+1)) _ 0 _ le_rfl,Zj4 a f f4c d4c l (wc l) _ 0 _ le_rfl] rename_i o o2;split · rename_i o3;rw[Zj4 a f f4c d4c l (wc l) _ 0 _ le_rfl];unfold Yak;rw[if_pos o3];unfold Yak;rw[if_neg (by omega)] · unfold Yak;rw[if_neg ‹_›] lemma ZB6 (c a:ٳ) (f4c:ٳ -> ٳ -> (δ × δ) × (δ × δ)) (d4c:ٳ -> ف) (d4:ٳ -> ف) (f4:ٳ -> ٳ -> (δ × δ) × (δ × δ)) (e4:ٳ -> ف) (g4:ٳ -> ٳ -> (δ × δ) × (δ × δ)) (d:ٳ -> ف) (b:ٳ -> ٳ -> δ × δ) (f:ٳ -> ٳ -> δ) (w:∀ i j,f4c i j=((f i j,f i (j+1)),(f i (j+2),f i (j+2+1)))) (u:∀ i j,f4 i j=((f i j,f (i+1) j),(f (i+2) j,f (i+2+1) j))) (v:∀ i j,g4 i j=((f i j,f (i+1) j),(f (i+2) j,f (i+2+1) j))) (e:∀ i j,b i j=(f i j,f (i+1) j)) : (if c<2 then Yak4 c a f f4c d4c 0 (AY (c*a)) else YT4l c a d4 f4 e4 g4 d b f f4c d4c 0 (AY (c*a)))=YT c a f:=by split;exact Zk4 c a f f4c d4c w _ 0 _ le_rfl;exact ZB4 c a d4 f4 e4 g4 d b f f4c d4c w u v e _ 0 _ le_rfl lemma QGc4 {β:Type} (kont:ػ -> ػ -> ػ -> ػ -> β) (n:ؾ) (F:(k:ؾ) -> k (ػ × ػ) × (ػ × ػ)) (B1 B2 B3 B4:ػ) (a1 a2 a3 a4:ؼ) (h1 l1 h2 l2 h3 l3 h4 l4:ػ) (k:ؾ) : QYc4 kont n F B1 B2 B3 B4 a1 a2 a3 a4 h1 l1 h2 l2 h3 l3 h4 l4 k=kont (QY6G n (λ k h=>(F k h).1.1) B1 a1 h1 l1 k) (QY6G n (λ k h=>(F k h).1.2) B2 a2 h2 l2 k) (QY6G n (λ k h=>(F k h).2.1) B3 a3 h3 l3 k) (QY6G n (λ k h=>(F k h).2.2) B4 a4 h4 l4 k):=by induction E:n؛-k؛generalizing h1 l1 h2 l2 h3 l3 h4 l4 k with |zero=> have o:¬k have o:k>>31).toUInt64))-((0:ػ)-(w>>>31).toUInt64)=((QPb x m (η w)).toUInt64-(ބ:ػ))*e:=by have h1:∀ s,(QPb x m s).toUInt64-(ބ:ػ)=if η x != s then -(Yf x<<<(Yd x-m)) else Yf x<<<(Yd x-m):=λ s=>by unfold QPb;split<;>simp only[Nat.toUInt64_eq,UInt64.ofNat_toNat]<;>generalize Yf x<<<(Yd x-m)=M<;>grind have h3:(w>>>31).toUInt64=if η w then 1 else 0:=by apply UInt64.toNat_inj.mp;rw[QZb w];split<;>rfl have n:∀ q:ػ,(q^^^((0:ػ)-1))-((0:ػ)-1)=-q:=λ q=>by apply UInt64.toBitVec_inj.mp;simp only[UInt64.toBitVec_sub,UInt64.toBitVec_xor,UInt64.toBitVec_neg,UInt64.toBitVec_zero,UInt64.toBitVec_one];rw[show (0#64-1#64:BitVec 64)=BitVec.allOnes 64 from by decide,BitVec.xor_allOnes];apply BitVec.eq_of_toNat_eq;simp only[BitVec.toNat_sub,BitVec.toNat_not,BitVec.toNat_neg,BitVec.toNat_allOnes];omega rw[h1,h1,h3];generalize Yf x<<<(Yd x-m)=M;generalize η w=a;generalize η x=c;cases a<;>cases c<;>simp (config:={decide:=true}) only[↓reduceIte,UInt64.neg_mul]<;>generalize M*e=q<;>first|(rw[n]<;>try simp)|simp lemma QDd4 (X:ؽ δ) (P:ؽ ٳ) (I:ؽ ؼ) (W b:ؽ δ) (inW i j:ٳ) (bx bv1 bv2 bv3 bv4:ؼ) (hP:Pٽ=2*inW -> Iٽ=0 -> ∀ t,t<2*inW -> P[t]! = QPb X[i*inW+t/2]! (Yk (bx>>>16)) (t%2=1)) : QPad4 X P I W b inW i j bx bv1 bv2 bv3 bv4=((QPa X P I W b inW i j bx bv1,QPa X P I W b inW i (j+1) bx bv2),(QPa X P I W b inW i (j+2) bx bv3,QPa X P I W b inW i (j+2+1) bx bv4)):=by have K:∀ (J:ٳ) (bv:ؼ),QPcD X P I W b inW i J bx bv=true -> ∀ (F:(k:ؾ)->k < inWٿ->ػ),(∀ k hk,F k hk=((P[2*k؛+(W[J*inW+k؛]!>>>31)؎]!).toUInt64-(ބ:ػ))*(Yf W[J*inW+k؛]!<<<((θ W[J*inW+k؛]!).toUInt64-(Yk (bv>>>16)+1)))) -> QPa X P I W b inW i J bx bv=(if QY6G inWٿ F (Yk (bx>>>16)+Yk (bv>>>16)) b[J]! 0 0 0<߿ then (QY6G inWٿ F (Yk (bx>>>16)+Yk (bv>>>16)) b[J]! 0 0 0).toUInt32 else Yai X W b inW i J):=by intro J bv hJ F hF;have hJ':=hJ;simp only[QPcD,decide_eq_true_eq] at hJ';obtain⟨p,i0,rest⟩:=hJ' have q:J*inW+inW<=Wٽ/\J*inW+inW<=ހ/\inW<ށ:=⟨rest.2.1,rest.2.2.2.1,rest.2.2.2.2.1⟩ unfold QPa;dsimp only;rw[dif_pos ⟨by rw[if_pos i0];exact p,by omega,rest⟩,dif_pos i0] have e:(λ (k:ؾ) (hk:k < inWٿ)=>((P.uget (k+k+(W.uget ((J*inW)ٿ+k) (by have:=υ.mp hk;rw [Za _ א] at this;rw [Zc _ _ (by rw [Za _ א];have:=τ;omega),Za _ א];omega)>>>31).toUSize) (by have:=υ.mp hk;rw [Za _ א] at this;have:=D0 k (W.uget ((J*inW)ٿ+k) (by have:=υ.mp hk;rw [Za _ א] at this;rw [Zc _ _ (by rw [Za _ א];have:=τ;omega),Za _ א];omega)) א;omega)).toUInt64-(ބ:ػ))*(Yf (W.uget ((J*inW)ٿ+k) (by have:=υ.mp hk;rw [Za _ א] at this;rw [Zc _ _ (by rw [Za _ א];have:=τ;omega),Za _ א];omega))<<<((θ (W.uget ((J*inW)ٿ+k) (by have:=υ.mp hk;rw [Za _ א] at this;rw [Zc _ _ (by rw [Za _ א];have:=τ;omega),Za _ א];omega))).toUInt64-(Yk (bv>>>16)+1))))=F:=by funext k hk;have f:k؛ < inW:=by have:=υ.mp hk;rwa[Za _ א] at this have g:((J*inW)ٿ+k)؛=J*inW+k؛:=by rw [Zc _ _ (by rw [Za _ א];have:=τ;omega),Za _ א] rw[hF];simp only[D9,g];have r:=R9 k W[J*inW+k؛]! (by omega);rw[r.1] rw[e] have Pe:∀ (J:ٳ) (bv:ؼ) (k:ٳ),k < inW -> Pٽ=2*inW -> Iٽ=0 -> ((((P[2*k]!).toUInt64-(ބ:ػ))*(Yf W[J*inW+k]!<<<((θ W[J*inW+k]!).toUInt64-(Yk (bv>>>16)+1))))^^^((0:ػ)-(W[J*inW+k]!>>>31).toUInt64))-((0:ػ)-(W[J*inW+k]!>>>31).toUInt64)=((P[2*k+(W[J*inW+k]!>>>31)؎]!).toUInt64-(ބ:ػ))*(Yf W[J*inW+k]!<<<((θ W[J*inW+k]!).toUInt64-(Yk (bv>>>16)+1))):=by intro J bv k f p i0;have h:=QZb W[J*inW+k]!;simp only[AG] at h have s:(W[J*inW+k]!>>>31)؎<2:=by split at h<;>omega have d:decide ((2*k+(W[J*inW+k]!>>>31)؎)%2=1)=η W[J*inW+k]!:=by rcases (η W[J*inW+k]!).eq_false_or_eq_true with c|c<;>rw[c]at h⊢<;>simp only[↓reduceIte,φ,ת,decide_eq_false_iff_not]at h⊢<;>omega rw[hP p i0 _ (by omega),hP p i0 _ (by omega),show 2*k/2=k by omega,show (2*k+(W[J*inW+k]!>>>31)؎)/2=k by omega,d,show decide (2*k%2=1)=false by simp] exact Qsg _ _ _ _ unfold QPad4;split · rename_i h;obtain⟨h1,h2,h3,h4⟩:=h;dsimp only;rw[QGc4] dsimp only;refine Prod.ext (Prod.ext ?_ ?_) (Prod.ext ?_ ?_) · have hJ:=h1;simp only[QPcD,decide_eq_true_eq] at hJ;obtain⟨p,i0,rest⟩:=hJ;have q:j*inW+inW<=ހ/\inW<ށ:=⟨rest.2.2.2.1,rest.2.2.2.2.1⟩ refine (K j bv1 h1 _ (λ k hk=>?_)).symm;clear * - hk q p i0 Pe;have f:k؛ < inW:=by have:=υ.mp hk;rwa[Za _ א] at this have g1:(k+k)؛=2*k؛:=by rw[Zc _ _ (by have:=τ;omega)];omega have g2:(Nat.toUSize (j*inW)+k)؛=j*inW+k؛:=by rw [Zc _ _ (by rw [Za _ א];have:=τ;omega),Za _ א] simp only[D9,g1,g2];exact Pe j bv1 k؛ f p i0 · have hJ:=h2;simp only[QPcD,decide_eq_true_eq] at hJ;obtain⟨p,i0,rest⟩:=hJ;have q:(j+1)*inW+inW<=ހ/\inW<ށ:=⟨rest.2.2.2.1,rest.2.2.2.2.1⟩ refine (K (j+1) bv2 h2 _ (λ k hk=>?_)).symm;clear * - hk q p i0 Pe;have f:k؛ < inW:=by have:=υ.mp hk;rwa[Za _ א] at this have g1:(k+k)؛=2*k؛:=by rw[Zc _ _ (by have:=τ;omega)];omega have g2:(Nat.toUSize ((j+1)*inW)+k)؛=(j+1)*inW+k؛:=by rw [Zc _ _ (by rw [Za _ א];have:=τ;omega),Za _ א] simp only[D9,g1,g2];exact Pe (j+1) bv2 k؛ f p i0 · have hJ:=h3;simp only[QPcD,decide_eq_true_eq] at hJ;obtain⟨p,i0,rest⟩:=hJ;have q:(j+2)*inW+inW<=ހ/\inW<ށ:=⟨rest.2.2.2.1,rest.2.2.2.2.1⟩ refine (K (j+2) bv3 h3 _ (λ k hk=>?_)).symm;clear * - hk q p i0 Pe;have f:k؛ < inW:=by have:=υ.mp hk;rwa[Za _ א] at this have g1:(k+k)؛=2*k؛:=by rw[Zc _ _ (by have:=τ;omega)];omega have g2:(Nat.toUSize ((j+2)*inW)+k)؛=(j+2)*inW+k؛:=by rw [Zc _ _ (by rw [Za _ א];have:=τ;omega),Za _ א] simp only[D9,g1,g2];exact Pe (j+2) bv3 k؛ f p i0 · have hJ:=h4;simp only[QPcD,decide_eq_true_eq] at hJ;obtain⟨p,i0,rest⟩:=hJ;have q:(j+2+1)*inW+inW<=ހ/\inW<ށ:=⟨rest.2.2.2.1,rest.2.2.2.2.1⟩ refine (K (j+2+1) bv4 h4 _ (λ k hk=>?_)).symm;clear * - hk q p i0 Pe;have f:k؛ < inW:=by have:=υ.mp hk;rwa[Za _ א] at this have g1:(k+k)؛=2*k؛:=by rw[Zc _ _ (by have:=τ;omega)];omega have g2:(Nat.toUSize ((j+2+1)*inW)+k)؛=(j+2+1)*inW+k؛:=by rw [Zc _ _ (by rw [Za _ א];have:=τ;omega),Za _ א] simp only[D9,g1,g2];exact Pe (j+2+1) bv4 k؛ f p i0 · rfl lemma QYcg (n:ؾ) (f g:(k:ؾ) -> k ػ) (B:ػ) (bw:ؼ) (h l:ػ) (k:ؾ) (e:∀ k hk,f k hk=g k hk) : QY6G n f B bw h l k=QY6G n g B bw h l k:=by have:f=g:=funext λ k=>funext λ hk=>e k hk;rw[this] lemma QDs4 (X:ؽ δ) (P:ؽ ٳ) (I:ؽ ؼ) (W b:ؽ δ) (inW i j:ٳ) (bx bv1 bv2 bv3 bv4:ؼ) (hP:Pٽ=2*Iٽ -> Iٽ≠0 -> ∀ u,u<2*Iٽ -> P[u]! = QPb X[i*inW+(I[u/2]!)؎]! (Yk (bx>>>16)) (u%2=1)) : QPas4 X P I W b inW i j bx bv1 bv2 bv3 bv4=((QPa X P I W b inW i j bx bv1,QPa X P I W b inW i (j+1) bx bv2),(QPa X P I W b inW i (j+2) bx bv3,QPa X P I W b inW i (j+2+1) bx bv4)):=by have K:∀ (J:ٳ) (bv:ؼ),QPsS X P I W b inW i J bx bv=true -> ∀ (F:(k:ؾ)->k < Iٽٿ->ػ),(∀ k hk,F k hk=((P[2*k؛+(W[J*inW+(min I[k؛]! (inW-1).toUInt32)؎]!>>>31)؎]!).toUInt64-(ބ:ػ))*(Yf W[J*inW+(min I[k؛]! (inW-1).toUInt32)؎]!<<<((θ W[J*inW+(min I[k؛]! (inW-1).toUInt32)؎]!).toUInt64-(Yk (bv>>>16)+1)))) -> QPa X P I W b inW i J bx bv=(if QY6G Iٽٿ F (Yk (bx>>>16)+Yk (bv>>>16)) b[J]! 0 0 0<߿ then (QY6G Iٽٿ F (Yk (bx>>>16)+Yk (bv>>>16)) b[J]! 0 0 0).toUInt32 else Yai X W b inW i J):=by intro J bv hJ F hF;have hJ':=hJ;simp only[QPsS,decide_eq_true_eq] at hJ';obtain⟨p,i0,rest⟩:=hJ' have q:J*inW+inW<=Wٽ/\J*inW+inW<=ހ/\inW<ށ:=⟨rest.2.2.1,rest.2.2.2.2.1,rest.2.2.2.2.2.1⟩ unfold QPa;dsimp only;rw[dif_pos ⟨by rw[if_neg i0];exact p,rest⟩,dif_neg i0,QYcg _ _ F _ _ _ _ _ (λ k hk=>?_)] rw[hF];have f:k؛ < Iٽ:=by have:=υ.mp hk;rwa[Za _ א] at this have r8:=R8 I[k؛]! inW q.2.2 have g:((J*inW)ٿ+(min I[k؛]! (inW-1).toUInt32).toUSize)؛=J*inW+(min I[k؛]! (inW-1).toUInt32)؎:=by rw [Zc _ _ (by rw [Za _ א,AI];have:=τ;omega),Za _ א,AI] simp only[D9,g];have r:=R9 k W[J*inW+(min I[k؛]! (inW-1).toUInt32)؎]! (by omega);rw[r.1] have Pe:∀ (J:ٳ) (bv:ؼ) (k:ٳ),k < Iٽ -> Pٽ=2*Iٽ -> Iٽ≠0 -> ((((P[2*k]!).toUInt64-(ބ:ػ))*(Yf W[J*inW+(min I[k]! (inW-1).toUInt32)؎]!<<<((θ W[J*inW+(min I[k]! (inW-1).toUInt32)؎]!).toUInt64-(Yk (bv>>>16)+1))))^^^((0:ػ)-(W[J*inW+(min I[k]! (inW-1).toUInt32)؎]!>>>31).toUInt64))-((0:ػ)-(W[J*inW+(min I[k]! (inW-1).toUInt32)؎]!>>>31).toUInt64)=((P[2*k+(W[J*inW+(min I[k]! (inW-1).toUInt32)؎]!>>>31)؎]!).toUInt64-(ބ:ػ))*(Yf W[J*inW+(min I[k]! (inW-1).toUInt32)؎]!<<<((θ W[J*inW+(min I[k]! (inW-1).toUInt32)؎]!).toUInt64-(Yk (bv>>>16)+1))):=by intro J bv k f p i0;have h:=QZb W[J*inW+(min I[k]! (inW-1).toUInt32)؎]!;simp only[AG] at h have s:(W[J*inW+(min I[k]! (inW-1).toUInt32)؎]!>>>31)؎<2:=by split at h<;>omega have d:decide ((2*k+(W[J*inW+(min I[k]! (inW-1).toUInt32)؎]!>>>31)؎)%2=1)=η W[J*inW+(min I[k]! (inW-1).toUInt32)؎]!:=by rcases (η W[J*inW+(min I[k]! (inW-1).toUInt32)؎]!).eq_false_or_eq_true with c|c<;>rw[c]at h⊢<;>simp only[↓reduceIte,φ,ת,decide_eq_false_iff_not]at h⊢<;>omega rw[hP p i0 _ (by omega),hP p i0 _ (by omega),show 2*k/2=k by omega,show (2*k+(W[J*inW+(min I[k]! (inW-1).toUInt32)؎]!>>>31)؎)/2=k by omega,d,show decide (2*k%2=1)=false by simp] exact Qsg _ _ _ _ unfold QPas4;split · rename_i h;obtain⟨h1,h2,h3,h4⟩:=h;dsimp only;rw[QGc4] dsimp only;refine Prod.ext (Prod.ext ?_ ?_) (Prod.ext ?_ ?_) · have hJ:=h1;simp only[QPsS,decide_eq_true_eq] at hJ;obtain⟨p,i0,rest⟩:=hJ;have q:j*inW+inW<=ހ/\inW<ށ:=⟨rest.2.2.2.2.1,rest.2.2.2.2.2.1⟩ have iI:Iٽ<=inW:=rest.1;refine (K j bv1 h1 _ (λ k hk=>?_)).symm;clear * - hk q p i0 Pe iI;have f:k؛ < Iٽ:=by have:=υ.mp hk;rwa[Za _ א] at this have r8:=R8 I[k؛]! inW q.2 have g1:(k+k)؛=2*k؛:=by rw[Zc _ _ (by have:=τ;omega)];omega have g2:(Nat.toUSize (j*inW)+(min I[k؛]! (inW-1).toUInt32).toUSize)؛=j*inW+(min I[k؛]! (inW-1).toUInt32)؎:=by rw [Zc _ _ (by rw [Za _ א,AI];have:=τ;omega),Za _ א,AI] simp only[D9,g1,g2];exact Pe j bv1 k؛ f p i0 · have hJ:=h2;simp only[QPsS,decide_eq_true_eq] at hJ;obtain⟨p,i0,rest⟩:=hJ;have q:(j+1)*inW+inW<=ހ/\inW<ށ:=⟨rest.2.2.2.2.1,rest.2.2.2.2.2.1⟩ have iI:Iٽ<=inW:=rest.1;refine (K (j+1) bv2 h2 _ (λ k hk=>?_)).symm;clear * - hk q p i0 Pe iI;have f:k؛ < Iٽ:=by have:=υ.mp hk;rwa[Za _ א] at this have r8:=R8 I[k؛]! inW q.2 have g1:(k+k)؛=2*k؛:=by rw[Zc _ _ (by have:=τ;omega)];omega have g2:(Nat.toUSize ((j+1)*inW)+(min I[k؛]! (inW-1).toUInt32).toUSize)؛=(j+1)*inW+(min I[k؛]! (inW-1).toUInt32)؎:=by rw [Zc _ _ (by rw [Za _ א,AI];have:=τ;omega),Za _ א,AI] simp only[D9,g1,g2];exact Pe (j+1) bv2 k؛ f p i0 · have hJ:=h3;simp only[QPsS,decide_eq_true_eq] at hJ;obtain⟨p,i0,rest⟩:=hJ;have q:(j+2)*inW+inW<=ހ/\inW<ށ:=⟨rest.2.2.2.2.1,rest.2.2.2.2.2.1⟩ have iI:Iٽ<=inW:=rest.1;refine (K (j+2) bv3 h3 _ (λ k hk=>?_)).symm;clear * - hk q p i0 Pe iI;have f:k؛ < Iٽ:=by have:=υ.mp hk;rwa[Za _ א] at this have r8:=R8 I[k؛]! inW q.2 have g1:(k+k)؛=2*k؛:=by rw[Zc _ _ (by have:=τ;omega)];omega have g2:(Nat.toUSize ((j+2)*inW)+(min I[k؛]! (inW-1).toUInt32).toUSize)؛=(j+2)*inW+(min I[k؛]! (inW-1).toUInt32)؎:=by rw [Zc _ _ (by rw [Za _ א,AI];have:=τ;omega),Za _ א,AI] simp only[D9,g1,g2];exact Pe (j+2) bv3 k؛ f p i0 · have hJ:=h4;simp only[QPsS,decide_eq_true_eq] at hJ;obtain⟨p,i0,rest⟩:=hJ;have q:(j+2+1)*inW+inW<=ހ/\inW<ށ:=⟨rest.2.2.2.2.1,rest.2.2.2.2.2.1⟩ have iI:Iٽ<=inW:=rest.1;refine (K (j+2+1) bv4 h4 _ (λ k hk=>?_)).symm;clear * - hk q p i0 Pe iI;have f:k؛ < Iٽ:=by have:=υ.mp hk;rwa[Za _ א] at this have r8:=R8 I[k؛]! inW q.2 have g1:(k+k)؛=2*k؛:=by rw[Zc _ _ (by have:=τ;omega)];omega have g2:(Nat.toUSize ((j+2+1)*inW)+(min I[k؛]! (inW-1).toUInt32).toUSize)؛=(j+2+1)*inW+(min I[k؛]! (inW-1).toUInt32)؎:=by rw [Zc _ _ (by rw [Za _ א,AI];have:=τ;omega),Za _ א,AI] simp only[D9,g1,g2];exact Pe (j+2+1) bv4 k؛ f p i0 · rfl lemma QWq4 (X:ؽ δ) (P:ؽ ٳ) (I:ؽ ؼ) (W b:ؽ δ) (inW i j:ٳ) (bx bv1 bv2 bv3 bv4:ؼ) (hP:Pٽ=2*inW -> Iٽ=0 -> ∀ t,t<2*inW -> P[t]! = QPb X[i*inW+t/2]! (Yk (bx>>>16)) (t%2=1)) (hPs:Pٽ=2*Iٽ -> Iٽ≠0 -> ∀ u,u<2*Iٽ -> P[u]! = QPb X[i*inW+(I[u/2]!)؎]! (Yk (bx>>>16)) (u%2=1)) : QPq4 X P I W b inW i j bx bv1 bv2 bv3 bv4=((QPa X P I W b inW i j bx bv1,QPa X P I W b inW i (j+1) bx bv2),(QPa X P I W b inW i (j+2) bx bv3,QPa X P I W b inW i (j+2+1) bx bv4)):=by unfold QPq4;split;exact QWc4 ..;split;exact QDd4 X P I W b inW i j bx bv1 bv2 bv3 bv4 hP;exact QDs4 X P I W b inW i j bx bv1 bv2 bv3 bv4 hPs lemma ZcC:YaV=linearSpec:=by funext m a o p X W b;unfold YaV linearSpec linearWith;dsimp only;rw[ZB6 _ _ _ _ _ _ _ _ _ _ _ (λ i j=>by rw[QWq4 _ _ _ _ _ _ _ _ _ _ _ _ _ (λ hs hi t ht=>?_) (λ hs hi u hu=>?_)] · by_cases hQ:QPS a (ڀ m λ i=>Yc X a i.val) (ڀ o λ j=>Yc W a j.val)=true<;>simp only[hQ,↓reduceIte,Bool.false_eq_true] at hs hi ⊢ · by_cases hm:i < m · rw[ح _ i (by simp only[AE];omega)] at hs hi ⊢;simp only[AD] at hs hi ⊢ split at hs · simp only[CK,Dr] at hs;omega · rename_i hsp;simp only[hsp,↓reduceIte] at hi ⊢;split at hs · rename_i l;simp only[l,↓reduceIte] at hi;simp only[Ω,ת] at l;omega · rename_i l;simp only[l,↓reduceIte,Bool.false_eq_true] at hi ⊢;rw[D2,ح _ t (by simp only[AE];omega)];simp only[AD] · rw[getElem!_neg _ _ (by simp only[AE];omega)] at hs;have z:(default:ؽ ٳ × ؽ ؼ).1ٽ=0:=rfl;omega · by_cases hm:i < m · rw[ح _ i (by simp only[DN];omega),CW] at hs;simp_all · rw[getElem!_neg _ _ (by simp only[DN];omega)] at hs;have z:(default:ؽ ٳ × ؽ ؼ).1ٽ=0:=rfl;omega · by_cases hQ:QPS a (ڀ m λ i=>Yc X a i.val) (ڀ o λ j=>Yc W a j.val)=true<;>simp only[hQ,↓reduceIte,Bool.false_eq_true] at hs hi hu ⊢ · by_cases hm:i < m · rw[ح _ i (by simp only[AE];omega)] at hs hi hu ⊢;simp only[AD] at hs hi hu ⊢ split at hi · simp only[CK,Dr] at hi;exact absurd rfl hi · rename_i hsp;simp only[hsp,↓reduceIte] at hs hu ⊢;split at hi · rename_i l;simp only[l,↓reduceIte] at hs hu ⊢;rw[D2,ح _ u (by simp only[AE];omega)];simp only[AD] · rename_i l;simp only[l,↓reduceIte,Bool.false_eq_true] at hi;simp at hi · rw[getElem!_neg _ _ (by simp only[AE];omega)] at hi;have z:(default:ؽ ٳ × ؽ ؼ).2ٽ=0:=rfl;omega · by_cases hm:i < m · rw[ح _ i (by simp only[DN];omega),CW] at hi;simp at hi · rw[getElem!_neg _ _ (by simp only[DN];omega)] at hi;have z:(default:ؽ ٳ × ؽ ؼ).2ٽ=0:=rfl;omega) (λ i j=>by simp only[D4q,D1]) (λ i j=>by simp only[QW4]) (λ i j=>by simp only[D1]),ZB _ _ _ rfl]<;>congr 1<;>funext q<;>have f:=q.isLt<;>have h:=CU (Ek f)<;>have e:=ϕ (f.trans_eq (Θ m o))<;>rw[Ze m (Yc X a) _ e,Ze o (Yc W a) _ (Ε q܂ h)] rw[I9];split . rw[ح _ (q܂/o) (by simp only[Bw,Ω,ת,AE,Fin.is_lt,ح,AD];omega)];simp only[AD];split . exact⟨λ _ t g d=>by simp only[CK,Dr]at d;omega,(absurd rfl ·)⟩ split . rename_i l;simp only[Ω,ת]at l;refine⟨λ c=>absurd c (by dsimp only;omega),λ _=>⟨?_,λ u n d=>?_⟩⟩ . rw[J0 _ _ _ 0 _ rfl];simp only[Bw,Array.toList_empty,Cd,ne_eq,decide_not,tsub_zero,←Ca,EB] . rw[D2,ح _ u (by rw[AE];omega)];simp only[Bw,AD];rw[Ze m _ _ e] . exact⟨λ _ t g d=>by rw[D2,ح _ t (by simp only[AE];omega)];simp only[AD];rw[Ze m _ _ e],(absurd rfl ·)⟩ . rw[ح _ _ (by simp only[DN];omega),CW];exact⟨λ _ t g d=>by simp only[CK,Dr]at d;omega,(absurd rfl ·)⟩ section end section open ExactRuntime FloatLib.Floats.Formats.BinaryInterchange FloatLib.Floats open Float.Model.UnpackedFloat end section open ExactRuntime FloatLib.Floats.Formats.BinaryInterchange FloatLib.Floats FloatLib.Numerics open Model open RationalBinary (floorLog2 scaleByPowerOfTwo scaleByPowerOfTwo_snd_ne_zero) open FloatLib.Numerics (binaryRadix Radix.toReal) end section open ExactRuntime FloatLib.Floats.Formats.BinaryInterchange FloatLib.Floats end section open ExactRuntime FloatLib.Floats.Formats.BinaryInterchange FloatLib.Floats FloatLib.Numerics open Model open RationalBinary (floorLog2 scaleByPowerOfTwo scaleByPowerOfTwo_snd_ne_zero) open FloatLib.Numerics (binaryRadix Radix.toReal) end section open ExactRuntime FloatLib.Floats.Formats.BinaryInterchange FloatLib.Floats end section end def kernels:Kernels where core:=kernels0.core dense:=⟨YaV,kernels0.dense.2⟩ conv:=kernels0.conv elem:=kernels0.elem norm:=kernels0.norm theorem correct:Obligation kernels:=by have h:kernels0=specKernels:=ZbZ;simp only[Obligation,kernels,h,specKernels,specDense,specConv,specElem,specNorm,ZcC] end Submission