import ContractExact namespace SmallDot open FloatLib.Floats.Formats.BinaryInterchange FloatLib.Floats ExactRuntime @[inline] def FJ (s:Bool) (p:Nat):Int:=if s then -(p:Int) else (p:Int) lemma AA (s:Bool) (p:Nat):FJ s p=(if s then -1 else 1)*(p:Int):=by cases s<;>simp [FJ] @[specialize] def FK (fa fb:Nat→Word) (index:Nat):Nat→Nat→Nat | 0,m=>m | count+1,m=>FK fa fb (index+1) count (min m (idxOf (fa index)+idxOf (fb index))) @[specialize] def FL (fa fb:Nat→Word) (m index:Nat):Nat→Int | 0=>0 | count+1=>FJ (Bool.xor (signOf (fa index)) (signOf (fb index))) ((mantOf (fa index)*mantOf (fb index))<<<(idxOf (fa index)+idxOf (fb index) - m))+ FL fa fb m (index+1) count @[specialize] def FM (fa fb:Nat→Word) (index:Nat):Nat→Bool | 0=>true | count+1=>(expOf (fa index) !=255&&expOf (fb index) !=255)&&FM fa fb (index+1) count @[specialize] def FN (fa fb:Nat→Word) (index:Nat):Nat→Bool | 0=>true | count+1=>(decide (mantOf (fa index)*mantOf (fb index)=0)&& Bool.xor (signOf (fa index)) (signOf (fb index)))&&FN fa fb (index+1) count lemma AB (fa fb:Nat→Word) (A B:Array UInt32):∀count index, (∀k,index≤k→k< index+count→ A[k]! =fa k∧B[k]! =fb k)→ FN fa fb index count=dallNZ A B index count:=by intro count;induction count with | zero=>intro index _;rfl | succ c ih=> intro index h obtain ⟨a,b⟩:=h index le_rfl (by omega) simp only[FN,dallNZ,a,b,ih (index+1) (fun k d e=>h k (by omega) (by omega))] @[inline] def FO:DotFn:=fun n fa fb=> if FM fa fb 0 n then let m:=FK fa fb 0 n 1024 let S:=FL fa fb m 0 n if S≠0 then finishWord S ((m:Int) - 298) false else toWord (Model.zero Fmt (decide (n≠0)&&FN fa fb 0 n)) else dotOf n fa fb lemma AC (A B:Array UInt32) (p:A.size=B.size) (b: ∀k,kintro index m0;exact ⟨le_rfl,fun k a b=>by omega⟩ | succ c ih=> intro index m0 obtain ⟨a,b⟩:=ih (index+1) (min m0 (idxOf (fa index)+idxOf (fb index))) simp only [FK] refine ⟨le_trans a (min_le_left _ _),fun k d e=> ?_⟩ by_cases f:k=index ·subst f;exact le_trans a (min_le_right _ _) ·exact b k (by omega) (by omega) lemma AF (fa fb:Nat→Word) (m:Nat) (A B:Array UInt32): ∀count index, (∀k,index≤k→k< index+count→ A[k]! =fa k∧B[k]! =fb k∧m≤ idxOf (fa k)+idxOf (fb k))→ FL fa fb m index count*2^m=dsum A B index count:=by intro count induction count with | zero=>intro index _;simp [FL,dsum] | succ c ih=> intro index h obtain ⟨a,b,d⟩:=h index le_rfl (by omega) simp only [FL,dsum] rw [add_mul,ih (index+1) (fun k f g=>h k (by omega) (by omega)),a,b] congr 1 rw [AA,Nat.shiftLeft_eq] have e:(2:Int)^(idxOf (fa index)+idxOf (fb index))= 2^(idxOf (fa index)+idxOf (fb index) - m)*2^m:=by rw [←pow_add,Nat.sub_add_cancel d] rw [e] unfold sv cases signOf (fa index)<;>cases signOf (fb index)<;>simp<;>push_cast<;>ring lemma AG (fa fb:Nat→Word): ∀count index,FM fa fb index count=true→ ∀k,index≤k→k< index+count→expOf (fa k)≠255∧expOf (fb k)≠255:=by intro count induction count with | zero=>intro index _ k a b;omega | succ c ih=> intro index h k a b simp only [FM,Bool.and_eq_true,bne_iff_ne,ne_eq] at h by_cases d:k=index ·subst d;exact ⟨h.1.1,h.1.2⟩ ·exact ih (index+1) h.2 k (by omega) (by omega) lemma AH:FO=dotOf:=by funext n fa fb unfold FO split ·rename_i l simp only[] set A:=Array.ofFn (n:=n) fun i=>fa i.val with e set B:=Array.ofFn (n:=n) fun i=>fb i.val with f have a: ∀k,k⟨(a k (by omega)).1,(a k (by omega)).2,m k (Nat.zero_le _) o⟩) split ·rename_i g have j:dsum A B 0 A.size≠0:=by rw [b,←h];exact mul_ne_zero g (pow_ne_zero _ two_ne_zero) show _=dotSpec A B rw [AC A B (by simp [e,f]) (fun k c=>by rw [b] at c rw [(a k c).1,(a k c).2];exact d k (Nat.zero_le _) (by omega)) j false,b,←h, ←finishWord_scale] congr 1 ·rename_i g have p:dsum A B 0 A.size=0:=by rw[b,←h];simp only[not_ne_iff] at g;rw[g];simp show _=dotSpec A B rw[AD A B (by simp[e,f]) (fun k c=>by rw[b] at c;rw[(a k c).1,(a k c).2];exact d k (Nat.zero_le _) (by omega)) p,b] congr 2 rw[AB fa fb A B n 0 (fun k _ c=>a k (by omega))] ·rfl end SmallDot namespace Submission local notation"א"=>by omega local notation"ב"=>by norm_num local notation"ג"=>by simp local notation"ד"=>by linarith local notation"А"=>USize.lt_iff_toNat_lt local notation"Б"=>mul_le_mul_of_nonneg_right local notation"В"=>Nat.and_two_pow_sub_one_eq_mod local notation"Г"=>Nat.mod_eq_of_lt local notation"Д"=>ite_eq_right local notation"Е"=>getElem!_pos local notation"Ж"=>UInt32.le_iff_toNat_le local notation"З"=>Nat.mul_le_mul_right local notation"И"=>UInt32.toNat_inj local notation"Й"=>mul_le_mul_of_nonneg_left local notation"К"=>Nat.zero_add local notation"Л"=>ite_eq_left local notation"М"=>zpow_add₀ local notation"Н"=>Nat.pos_of_ne_zero local notation"О"=>UInt32.toNat_and local notation"П"=>abs_nonneg local notation"Р"=>dite_eq_left local notation"С"=>two_ne_zero local notation"Т"=>UInt32.toNat_toUSize local notation"У"=>abs_of_nonneg local notation"Ф"=>zpow_le_zpow_right₀ local notation"Х"=>dite_eq_right local notation"Ц"=>zpow_natCast local notation"Ч"=>abs_add_le local notation"Ш"=>mul_lt_mul_of_pos_right local notation"Щ"=>USize.toNat_one local notation"Ъ"=>Nat.mod_lt local notation"Ы"=>UInt64.toNat_add local notation"Ь"=>mul_nonneg local notation"Э"=>Nat.cast_nonneg local notation"Ю"=>Nat.shiftRight_eq_div_pow local notation"Я"=>Nat.add_zero local notation"а"=>FloatLib.Numerics.Dyadic.toRat_eq_zero_iff local notation"б"=>getElem!_neg local notation"в"=>lt_of_le_of_lt local notation"г"=>mul_le_mul local notation"д"=>Nat.pow_le_pow_right local notation"е"=>UInt32.toNat_ofNat' local notation"ж"=>FloatLib.Numerics.Dyadic.cast_toRat local notation"з"=>Nat.add_assoc local notation"и"=>Nat.lt_or_eq_of_le local notation"й"=>Nat.le_mul_of_pos_right local notation"к"=>Nat.pos_of_mul_pos_left local notation"л"=>UInt32.toNat_shiftRight local notation"м"=>UInt64.toNat_shiftRight local notation"н"=>List.mem_range local notation"о"=>Nat.mul_comm local notation"п"=>UInt32.lt_iff_toNat_lt local notation"р"=>UInt64.lt_iff_toNat_lt local notation"с"=>Nat.div_eq_of_lt local notation"т"=>Nat.shiftLeft_eq local notation"у"=>Bool.and_eq_true_iff local notation"ф"=>Nat.add_mul local notation"х"=>Nat.div_lt_of_lt_mul local notation"ц"=>Nat.one_mul local notation"ч"=>Nat.pow_add local notation"ш"=>Nat.lt_succ_iff local notation"щ"=>Nat.two_pow_add_eq_or_of_lt local notation"ъ"=>Array.ext local notation"ы"=>Finset.sum_congr local notation"ь"=>Nat.exists_eq_add_of_le local notation"э"=>UInt64.toNat_and local notation"ю"=>zpow_pos local notation"я"=>lt_of_mul_lt_mul_right local notation"ذ"=>Nat.div_div_eq_div_mul local notation"ر"=>Nat.succ_mul local notation"ز"=>Nat.succ_pos local notation"س"=>UInt32.toNat_sub_of_le local notation"ش"=>List.mem_filter local notation"ص"=>Nat.mod_add_div local notation"ض"=>Array.getElem_push_eq local notation"ط"=>Array.getElem_push_lt local notation"ظ"=>le_trans local notation"ع"=>Rat.cast_zero open ExactRuntime FloatLib.Floats.Formats.BinaryInterchange FloatLib.Floats structure F1 where (s t:Float) structure R1 where (ix:Array UInt32) (buf:FloatArray) (c:USize) (hi:UInt32) structure D_Sc where (lo hi:UInt32) structure D_C where (dw relu f4:Bool) (s:ConvShape) (X W b:Array UInt32) (k C ho wo wp:Nat) (step:USize) (hi:UInt32) (xd:FloatArray) (nf:Float) (tab:Array UInt32) structure D_P where (g:D_C) (wd:FloatArray) (off:Array UInt32) (e l1 l4:USize) (e0 bv ze:Float) (he:e.toNat<=off.size) (hw:e.toNat<=wd.size) (hs:g.xd.size<2^32) (h1:∀b:USize,b∀j (h:j∀j (h:jUInt32) (k:Nat) (a:kf i.val)[k]! =f k:=by rw[Е _ k (by simpa using a),Array.getElem_ofFn] @[inline] def FP:DotFn:=SmallDot.FO lemma AJ:FP=dotOf:=SmallDot.AH lemma AK (w:Word):toWord (ofW w)=w:=by apply И.mp;simp only[toWord,ofW,Model.toNatBits,ofUInt32_bits,UInt32.toNat_ofNat'];exact Г w.toBitVec.isLt lemma AL (z:Model Fmt):ofW (toWord z)=z:=by have h:z.toNatBits<2^32:=Model.toNatBits_lt_two_pow z;simp only[ofW,toWord,Model.ofUInt32,UInt32.toNat_ofNat',Nat.mod_eq_of_lt h];exact Model.ofNatBits_toNatBits z @[inline] def FQ (w:Word):Int:= if signOf w then -((mantOf w<<< idxOf w:Nat):Int) else ((mantOf w<<< idxOf w:Nat):Int) lemma AM (w:Word):FQ w=sv w*2^idxOf w:=by unfold FQ sv;split<;>simp[Nat.shiftLeft_eq] lemma AN (w:Word):(decodeD w).toReal=(FQ w:ℝ)*2^(-149:Int):=by rw[<-ж,decodeD_toRat,AM];push_cast;rw[zpow_sub₀ С,Ц];ring @[inline] def FR (a b:Word):Word:= if expOf a=255∨expOf b=255 then toWord (Model.maximum (ofW a) (ofW b)) else match compare (FQ a) (FQ b) with | .lt=>b | .gt=>a | .eq=>toWord (if Model.isZero (ofW a)&&Model.isZero (ofW b) then Model.zero Fmt (Model.signBit (ofW a)&&Model.signBit (ofW b)) else ofW a) lemma AO (a b:Word):Model.cmpDyadic (decodeD a) (decodeD b)=compare (FQ a) (FQ b):=by have c:(0:ℝ)<2^(-149:Int):=ю two_pos _;cases h:compare (FQ a) (FQ b);. rw[Model.cmpDyadic_lt_iff,AN,AN];exact Ш (by exact_mod_cast compare_lt_iff_lt.mp h) c . rw[Model.cmpDyadic_eq_iff,AN,AN,compare_eq_iff_eq.mp h] . rw[Model.cmpDyadic_gt_iff,AN,AN];exact Ш (by exact_mod_cast compare_gt_iff_gt.mp h) c lemma AP (a b:Word):ofW (FR a b)=Model.maximum (ofW a) (ofW b):=by unfold FR;split;. exact AL _ . rename_i f;have g:=toDyadic_ofUInt32 a (λh=>f (Or.inl h));have i:=toDyadic_ofUInt32 b (λh=>f (Or.inr h));have d:=Model.isNaN_eq_false_of_toDyadic?_some g;have e:=Model.isNaN_eq_false_of_toDyadic?_some i;have j:Model.compare (ofW a) (ofW b)=some _:=Model.compare_eq_some_cmpDyadic_of_toDyadic? _ _ g i;rw[AO] at j;have c:Model.chooseNaN2 (ofW a) (ofW b)=none:=(Model.chooseNaN2_eq_none_iff _ _).2 ⟨d,e⟩;unfold Model.maximum;rw[Model.withNaNSelection_of_none _ _ c];dsimp only;rw[Model.compareNonNaN_eq_of_compare_eq_some _ _ _ _ j];cases compare (FQ a) (FQ b)<;>simp only[AL] def FS (c h w k:Nat) (inp:Array Word):Array Word:= Array.ofFn (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) (List.range (k*k)).foldl (λacc t=>FR acc (poolAt h w k inp ch y x t)) (poolAt h w k inp ch y x 0) lemma AQ (p:Nat->Word) (l:List Nat) (acc:Word): l.foldl (λm t=>Model.maximum m (ofW (p t))) (ofW acc)=ofW (l.foldl (λa t=>FR a (p t)) acc):=by induction l generalizing acc with | nil=>rfl | cons t l ih=>simp only[List.foldl_cons,<-AP,ih] lemma AR:FS=maxpoolSpec:=by funext c h w k inp;simp only[FS,maxpoolSpec,AQ,AK] lemma AS (t n:USize) (h:ta.push (FX i)) (FloatArray.emptyWithCapacity 512) lemma AW:pw.data=(List.range 512).toArray.map FX:=by have key:∀(l:List Nat) (a:FloatArray),(l.foldl (λa i=>a.push (FX i)) a).data=a.data++(l.toArray.map FX):=by intro l;induction l with | nil=>intro a;simp | cons x l ih=>intro a;simp only[List.foldl_cons,ih];simp[FloatArray.push] simp only[pw,key];simp[FloatArray.emptyWithCapacity] lemma AX:pw.size=512:=by simp[FloatArray.size,AW] lemma AY (w:UInt32):(w>>>(23:UInt32)).toUSize.toNat>>(23:UInt32)).toUSize (AY w) @[inline] def FY (w:UInt32):Bool:= let v:=w&&&0x7FFFFFFF v==0 || v-(0x00800000:UInt32)<=(0x7EFFFFFF:UInt32) def FZ (A:Array UInt32) (n i:USize) (hn:n.toNat<=A.size) (lo hi:UInt32):UInt32:= if h:i>>(29:UInt64) let y:UInt64:=((s-e).toBits+(0x0FFFFFFF:UInt64))>>>(29:UInt64) let ex:UInt64:=(x>>>(23:UInt64))&&&(0x7FF:UInt64) if x==y&&ex-(897:UInt64)<(254:UInt64) then (((x>>>(34:UInt64))<<<(31:UInt64)) ||| ((x&&&(0x3FFFFFFFF:UInt64))-((896:UInt64)<<<(23:UInt64)))).toUInt32 else 0xFFFFFFFF @[inline] def mx (a w:UInt32):UInt32:= let m:=w&&&0x7FFFFFFF if m<=a then a else m def Fc (X:Array UInt32) (o n t:USize) (ix:Array UInt32) (buf:FloatArray) (c:USize) (hi:UInt32):R1:= if h:tUInt32) (bw:UInt32):ℝ:= (Finset.range n).sum (λt=>wv (xw t)*wv (ww t))+wv bw def Fe (n:Nat):Float:=(n.toUInt64+8).toFloat*Float.ofBits 0x3CC0000000000000 lemma Aa:FloatFormat.binary64.isIEEE=true:=by decide lemma Ab (a:Model FloatFormat.binary64):Model.isFinite a=(Model.toModel a).isFinite:=by have c:=Model.toDyadic?_ieee_eq_model _ Aa a;cases f:Model.toModel a with | notANumber=> rw[f] at c;cases h:Model.isFinite a with | false=>rfl | true=>obtain ⟨d,b⟩:=Model.exists_toDyadic?_of_isFinite h;rw[c] at b;cases b | infinity s=> rw[f] at c;cases h:Model.isFinite a with | false=>rfl | true=>obtain ⟨d,b⟩:=Model.exists_toDyadic?_of_isFinite h;rw[c] at b;cases b | zero s=>rw[f] at c;exact Model.isFinite_eq_true_of_toDyadic?_some c | finite s m e h=>rw[f] at c;exact Model.isFinite_eq_true_of_toDyadic?_some c abbrev Ff (x:Float):Model FloatFormat.binary64:=Model.ofFloatModel x.toModel lemma Ac (x:Float):R x=Model.toReal (Ff x):=rfl lemma Ad (x:Float):Model.isFinite (Ff x)=x.isFinite:=by rw[Ab,Model.toModel_ofFloatModel];rfl lemma Ae (e:ℤ):Formats.Flocq.bpow FloatLib.Numerics.binaryRadix e=(2:ℝ)^e:=by simp[Formats.Flocq.bpow,FloatLib.Numerics.binaryRadix,FloatLib.Numerics.Radix.toReal] lemma Af:(2:ℝ)^(1000:ℤ)<=Model.toReal (Model.posMaxFinite FloatFormat.binary64):=by rw[Model.toReal_posMaxFinite] have a:Model.pow2 FloatFormat.binary64.fracWidth+FloatFormat.binary64.maxFiniteFracField =2^53-1:=by decide+kernel have b:FloatFormat.binary64.maxNormalExponent-Int.ofNat FloatFormat.binary64.fracWidth =971:=by decide+kernel rw[a,b];have c:Model.bpow 971=(2:ℝ)^(971:ℤ):=by simp only[Model.bpow,Ae] rw[c,show (1000:ℤ)=29+971 from rfl,М ב];apply Б _ (by positivity);norm_num lemma Ag (x y:Float) (c:x.isFinite=true) (d:y.isFinite=true) (e: |R x| + |R y| ≤2^(1000:ℤ)): (x+y).isFinite=true∧R (x+y)=Model.roundAt FloatFormat.binary64 (R x+R y):=by have f:Ff (x+y)=Model.add (Ff x) (Ff y):=toModel_ofFloat_add_of_isFinite x y c d have a:Model.isFinite (Ff x)=true:=by rw[Ad,c] have b:Model.isFinite (Ff y)=true:=by rw[Ad,d] constructor . rw[<-Ad,f];exact Model.isFinite_add_of_abs_add_le_posMaxFinite _ _ Aa a b (e.trans Af) . rw[Ac,f];exact Model.toReal_add_eq_roundAt_of_abs_add_le_posMaxFinite _ _ Aa a b (e.trans Af) lemma Ah (x y:Float) (c:x.isFinite=true) (d:y.isFinite=true) (e: |R x| + |R y| ≤2^(1000:ℤ)): (x-y).isFinite=true∧R (x-y)=Model.roundAt FloatFormat.binary64 (R x-R y):=by have f:Ff (x-y)=Model.sub (Ff x) (Ff y):=toModel_ofFloat_sub_of_isFinite x y c d have a:Model.isFinite (Ff x)=true:=by rw[Ad,c] have b:Model.isFinite (Ff y)=true:=by rw[Ad,d] constructor . rw[<-Ad,f];exact Model.isFinite_sub_of_abs_add_le_posMaxFinite _ _ Aa a b (e.trans Af) . rw[Ac,f];exact Model.toReal_sub_eq_roundAt_of_abs_add_le_posMaxFinite _ _ Aa a b (e.trans Af) open Float.Model.UnpackedFloat in lemma Ai (b:BitVec 64) (s m e h) (a:Float.Model.UnpackedFloat.unpack Float.Model.Format.binary64 b=.finite s m e h):(2^52<=m∧-1074<=e)∨e=-1074:=by unfold Float.Model.UnpackedFloat.unpack at a;simp only at a;have f:(Float.Model.Format.binary64.exponentBias:ℤ)=1023:=by decide rw[f] at a;split_ifs at a with j k c l . injection a with _ _ d;right;have:(unpackExponent (spec:=Float.Model.Format.binary64) b).toNat=0:=by simp[c] rw[this] at d;omega . injection a with _ g d;left;have:(unpackExponent (spec:=Float.Model.Format.binary64) b).toNat≠0:=by intro i;exact c (BitVec.eq_of_toNat_eq (by simpa using i)) constructor;. rw[<-g,BitVec.toNat_append];refine ظ ?_ Nat.left_le_or;simp[Nat.shiftLeft_eq] . omega open Float.Model.UnpackedFloat in lemma Aj (spec:Float.Model.Format) (s:Sign) (m:ℕ) (e:ℤ) (h:e<=spec.targetExponent (Float.Model.totalExponent m e)):Float.Model.UnpackedFloat.round spec s m e=roundWithAccuracy spec s m e .exact:=by unfold Float.Model.UnpackedFloat.round decreaseExponent;have a:(e-spec.targetExponent (Float.Model.totalExponent m e)).toNat=0:=א;simp[a] open Float.Model.UnpackedFloat in lemma Ak (s₁ s₂ m₁ m₂ e₁ e₂ b c) (b₁ b₂:BitVec 64) (d:unpack Float.Model.Format.binary64 b₁=.finite s₁ m₁ e₁ b) (e:unpack Float.Model.Format.binary64 b₂=.finite s₂ m₂ e₂ c): e₁+e₂<=Float.Model.Format.binary64.targetExponent (Float.Model.totalExponent (m₁*m₂) (e₁+e₂)):=by have c₁:=Ai _ _ _ _ _ d have c₂:=Ai _ _ _ _ _ e have f:m₁*m₂≠0:=Nat.mul_ne_zero b.ne' c.ne' have a:2^52<=m₁*m₂->52<=(m₁*m₂).log2:=λh=>(Nat.le_log2 f).2 h simp only[Float.Model.Format.targetExponent,Float.Model.totalExponent,Float.Model.Format.mantissaBits,Float.Model.Format.minExponent] rcases c₁ with ⟨c₁,_⟩ | c₁ . have:=a (ظ c₁ (й _ c));apply le_max_of_le_left;norm_num;omega . rcases c₂ with ⟨c₂,_⟩ | c₂;. have:=a (ظ c₂ (Nat.le_mul_of_pos_left _ b));apply le_max_of_le_left;norm_num;omega . apply le_max_of_le_right;norm_num;omega open Float.Model.UnpackedFloat in lemma Al (x y:Float) (f:x.isFinite=true) (g:y.isFinite=true):Ff (x*y)=Model.mul (Ff x) (Ff y):=by have h:Model.toModel (Ff x)=x.toModel.unpack:=Model.toModel_ofFloatModel _;have i:Model.toModel (Ff y)=y.toModel.unpack:=Model.toModel_ofFloatModel _;change Model.ofFloatModel (Float.Model.mul x.toModel y.toModel)=_;rw[Float.Model.mul,Model.ofFloatModel_pack,Model.Proof.mul_eq_spec,Model.Spec.mul,Model.toDyadic?_ieee_eq_model _ Aa (Ff x),Model.toDyadic?_ieee_eq_model _ Aa (Ff y),h,i];change x.toModel.unpack.isFinite=true at f;change y.toModel.unpack.isFinite=true at g;cases a:x.toModel.unpack<;>cases b:y.toModel.unpack<;>simp only[a,b,Float.Model.UnpackedFloat.isFinite,Bool.false_eq_true] at f g case zero.zero s₁ s₂=> cases s₁<;>cases s₂<;>simp[Model.unpackedToDyadic?,Float.Model.UnpackedFloat.mul] all_goals first | (rw[Model.negZero_eq_ofModel_zero];rfl) | (rw[Model.posZero_eq_ofModel_zero];rfl) case zero.finite s₁ s₂ m₂ e₂ c=> cases s₁<;>cases s₂<;>simp[Model.unpackedToDyadic?,Float.Model.UnpackedFloat.mul] all_goals first | (rw[Model.negZero_eq_ofModel_zero];rfl) | (rw[Model.posZero_eq_ofModel_zero];rfl) case finite.zero s₁ m₁ e₁ d s₂=> cases s₁<;>cases s₂<;>simp[Model.unpackedToDyadic?,Float.Model.UnpackedFloat.mul] all_goals first | (rw[Model.negZero_eq_ofModel_zero];rfl) | (rw[Model.posZero_eq_ofModel_zero];rfl) case finite.finite s₁ m₁ e₁ d s₂ m₂ e₂ c=> simp only[Model.unpackedToDyadic?,Float.Model.UnpackedFloat.mul];have e:=Ak s₁ s₂ m₁ m₂ e₁ e₂ d c _ _ a b;have j:(m₁==0 || m₂==0)=false:=by simp[d.ne',c.ne'] rw[<-Aj _ _ _ _ e,j];have k:Model.modelSign (Model.modelSignBit s₁^^Model.modelSignBit s₂)=s₁*s₂:=by cases s₁<;>cases s₂<;>rfl simp only[Bool.false_eq_true,ite_false,Model.roundDyadic,Aa,ite_true,Model.ieeeRoundDyadic,k];rfl lemma Am (x y:Float) (c:x.isFinite=true) (d:y.isFinite=true) (e: |R x| * |R y| ≤2^(1000:ℤ)): (x*y).isFinite=true∧R (x*y)=Model.roundAt FloatFormat.binary64 (R x*R y):=by have f:Ff (x*y)=Model.mul (Ff x) (Ff y):=Al x y c d have a:Model.isFinite (Ff x)=true:=by rw[Ad,c] have b:Model.isFinite (Ff y)=true:=by rw[Ad,d] constructor . rw[<-Ad,f];exact Model.isFinite_mul_of_abs_mul_le_posMaxFinite _ _ Aa a b (e.trans Af) . rw[Ac,f];exact Model.toReal_mul_eq_roundAt_of_abs_mul_le_posMaxFinite _ _ Aa a b (e.trans Af) noncomputable def Fg:ℝ:=2^(-1021:ℤ) noncomputable def Fh:ℝ:=2^(300:ℤ) lemma An:0rw[<-a];exact Model.toModel_canonicalizeModel _ | negative=> have d:(Model.toModel (Ff f)).isFinite=true:=by rw[a];rfl have b:=Model.toModel_neg_of_isFinite Aa (Ff f) d;rw[a] at b;have g:Float.Model.UnpackedFloat.neg (.finite .negative m e h)=.finite .positive m e h:=rfl;rw[g] at b;rw[<-b];exact Model.toModel_canonicalizeModel _ lemma A0 (f:Float) (c:f.isFinite=true):f.abs.isFinite=true∧R f.abs= |R f|:=by have b:Ff f.abs=Model.ofModel FloatFormat.binary64 f.toModel.unpack.abs:=Model.ofFloatModel_pack _;change f.toModel.unpack.isFinite=true at c;cases a:f.toModel.unpack with | notANumber=>simp[a,Float.Model.UnpackedFloat.isFinite] at c | infinity s=>simp[a,Float.Model.UnpackedFloat.isFinite] at c | zero s=> rw[a] at b;constructor;. rw[<-Ad,b];exact Model.isFinite_ofModel_zero _ Aa _ . rw[Ac f.abs,b,Ay f,a];simp[Float.Model.UnpackedFloat.abs,Model.toReal_ofModel_zero _ Aa] | finite s m e h=> rw[a] at b;have d:=Az f s m e h a;change Model.toModel (Model.ofModel FloatFormat.binary64 (.finite .positive m e h))=_ at d;constructor;. rw[<-Ad,b,Ab];change (Model.toModel (Model.ofModel FloatFormat.binary64 (.finite .positive m e h))).isFinite=_;rw[d];rfl . rw[Ac f.abs,b,Ay f,a];change Model.toReal (Model.ofModel FloatFormat.binary64 (.finite .positive m e h))=_;rw[Model.toReal_eq_unpackedToReal_toModel Aa,d];simp only[Model.unpackedToReal_finite,Ae];have g:(0:ℝ)<=(m:ℝ)*2^e:=by positivity cases s<;>simp[Model.modelSignBit,abs_of_nonneg g] lemma A1 (f:Float) (k:ℕ) (d:k<2^53) (g:f.toModel=Float.Model.pack (Float.Model.UnpackedFloat.ofNat Float.Model.Format.binary64 k)):f.isFinite=true∧R f=k:=by have b:Ff f=Model.roundDyadic FloatFormat.binary64 (FloatLib.Numerics.Dyadic.ofScaledInt k 0):=by change Model.ofFloatModel f.toModel=_;rw[g,Model.ofFloatModel_pack];exact Model.ofModel_ofInt_eq_roundDyadic _ Aa (k:ℤ) have e:(FloatLib.Numerics.Dyadic.ofScaledInt k 0).toReal=k:=by rw[<-ж,FloatLib.Numerics.Dyadic.ofScaledInt_toRat];simp have c:(k:ℝ)<=2^(1000:ℤ):=by have h:(k:ℝ)<=2^53:=by exact_mod_cast d.le have i:(2:ℝ)^53<=2^256*2^42:=ב calc (k:ℝ)<=2^53:=h _<=2^256*2^42:=i _<=Fh:=Aq _<=Fh*2:=by linarith [Ap] _<=_:=Ar have a:Model.isFinite (Ff f)=true:=by rw[b];apply Model.isFinite_roundDyadic_of_isIEEE_of_abs_toReal_le_posMaxFinite _ Aa;rw[e,У (Э _)];exact c.trans Af refine ⟨by rw[<-Ad];exact a,?_⟩;rw[Ac,b,Model.toReal_roundDyadic_eq_roundAt _ Aa _ (b▸a),e];have:=Ax k 0 (by simpa using d) ב;simpa using this lemma A2 (m:UInt32) (h:m.toNat<2^53):m.toFloat.isFinite=true∧R m.toFloat=m.toNat:=A1 _ _ h rfl lemma A3 (m:UInt64) (h:m.toNat<2^53):m.toFloat.isFinite=true∧R m.toFloat=m.toNat:=A1 _ _ h rfl lemma A4:(0:Float).toModel.unpack=.zero .positive:=by rfl lemma A5:(0:Float).isFinite=true∧R 0=0:=by refine ⟨?_,?_⟩;. change (0:Float).toModel.unpack.isFinite=true;rw[A4];rfl . rw[Ay,A4];simp def Fi (i:ℕ):UInt64:= let e:=(i%256).toUInt64 let s:UInt64:=if i≥256 then 0x8000000000000000 else 0 if e==0 then s else s ||| ((e+873)<<<(52:UInt64)) lemma A6 (i:ℕ):FX i=Float.ofBits (Fi i):=by unfold FX Fi;dsimp only;split<;>rfl def Fj (i:ℕ):Bool:= match Float.Model.UnpackedFloat.unpack Float.Model.Format.binary64 (Fi i).toBitVec with | .finite s m e _=>(Model.modelSignBit s==decide (256<=i))&&m==2^52&& e==((i%256:ℕ):ℤ)-202&&(i%256 !=0) | .zero _=>i%256==0 | _=>false lemma A7:∀i,i<512->Fj i=true:=by decide+kernel lemma A8 (i:ℕ) (d:i<512): (FX i).isFinite=true∧R (FX i)=if i%256=0 then 0 else (if 256<=i then -1 else 1)*2^(((i%256:ℕ):ℤ)-150):=by have a:=A7 i d rw[A6] have c:(Float.ofBits (Fi i)).toModel.unpack=Float.Model.UnpackedFloat.unpack Float.Model.Format.binary64 (Fi i).toBitVec:=Model.unpack_pack_unpack _ _ unfold Fj at a rw[Ay,c] change (Float.ofBits (Fi i)).toModel.unpack.isFinite=true∧_ rw[c] cases b:Float.Model.UnpackedFloat.unpack Float.Model.Format.binary64 (Fi i).toBitVec with | notANumber=>rw[b] at a;simp at a | infinity s=>rw[b] at a;simp at a | zero s=> rw[b] at a simp only[beq_iff_eq] at a refine ⟨rfl,?_⟩ simp[a] | finite s m e h=> rw[b] at a simp only[Bool.and_eq_true,beq_iff_eq,bne_iff_ne] at a obtain ⟨⟨⟨f,g⟩,j⟩,k⟩:=a refine ⟨rfl,?_⟩ have e:((2^52:ℕ):ℝ)*2^(((i%256:ℕ):ℤ)-202)=2^(((i%256:ℕ):ℤ)-150):=by rw[Nat.cast_pow,Nat.cast_ofNat,<-Ц,<-М ב] congr 1 push_cast ring rw[Model.unpackedToReal_finite,Ae,j,f,g,mul_assoc,e] simp only[decide_eq_true_eq,k,↓reduceIte] lemma A9 (i:USize) (h:i.toNat>>(23:UInt32)).toNat=w.toNat/2^23:=by rw[л,Ю];rfl lemma BD (w:UInt32):(expOf w).toNat=w.toNat/2^23%2^8:=by unfold expOf;rw[О,BC];exact В _ 8 lemma BE (w:UInt32):signOf w=decide (2^31<=w.toNat):=by have b:=w.toNat_lt;unfold signOf;have h:((w&&&0x80000000).toNat)=(w.toNat/2^31%2)*2^31:=by rw[О];show w.toNat&&&2^31=_;rw[Nat.and_two_pow,Nat.testBit_eq_decide_div_mod_eq];have a:w.toNat/2^31%2=0∨w.toNat/2^31%2=1:=א;rcases a with a | a<;>rw[a]<;>rfl rw[Bool.eq_iff_iff];simp only[bne_iff_ne,ne_eq,decide_eq_true_eq];rw[<-И,h];simp only[UInt32.toNat_zero];omega lemma BF (w:UInt32):((w&&&0x7FFFFF) ||| 0x800000).toNat=2^23+w.toNat%2^23:=by rw[UInt32.toNat_or,BB,Nat.or_comm];have h:w.toNat%2^23<2^23:=Ъ _ (by positivity);have:=щ h 1;simpa using this.symm lemma BG (w:UInt32) (h:FY w=true):w.toNat%2^31=0∨(2^23<=w.toNat%2^31∧w.toNat%2^31<0x7F800000):=by have a:=BA w;have b:=(w&&&0x7FFFFFFF).toNat_lt;unfold FY at h;simp only[Bool.or_eq_true,beq_iff_eq,decide_eq_true_eq] at h;rcases h with h | h;. left;rw[<-a,h];rfl . right;rw[Ж,UInt32.toNat_sub] at h;rw[<-a];generalize (w&&&0x7FFFFFFF).toNat=v at*;simp at h;omega noncomputable def Fk (v:ℕ):ℝ:= if v=0 then 0 else ((2^23+v%2^23:ℕ):ℝ)*2^(((v/2^23:ℕ):ℤ)-150) lemma BH (v:ℕ):0<=Fk v:=by unfold Fk;split_ifs<;>positivity lemma BI (w:UInt32) (e:FY w=true):wv w=(if 2^31<=w.toNat then -1 else 1)*Fk (w.toNat%2^31):=by have i:=w.toNat_lt;have f:=BG w e;have a:=BD w;have c:(fracOf w).toNat=w.toNat%2^23:=BB w;have b:expOf w≠255:=by intro h;rw[h] at a;change 255=_ at a;omega have g:wv w=(decodeD w).toReal:=by unfold wv ofW;rw[Model.toReal_eq,toDyadic_ofUInt32 w b] rw[g];unfold decodeD Fk;by_cases d:w.toNat%2^31=0 . have e0:expOf w=0:=by apply И.mp;rw[a];show _=0;omega have f0:fracOf w=0:=by apply И.mp;rw[c];show _=0;omega simp only[e0,f0,d,↓reduceIte];simp[FloatLib.Numerics.Dyadic.toReal,FloatLib.Numerics.Dyadic.signedSignificand] . have e0:expOf w≠0:=by intro h;rw[h] at a;change 0=_ at a;omega simp only[e0,d,↓reduceIte];have f1:w.toNat%2^31%2^23=(fracOf w).toNat:=by rw[c];omega have f2:w.toNat%2^31/2^23=(expOf w).toNat:=by rw[a];omega rw[f1,f2];simp only[FloatLib.Numerics.Dyadic.toReal,FloatLib.Numerics.Dyadic.signedSignificand,BE];simp;split_ifs<;>ring lemma BJ (v:ℕ) (h:v<0x7F800000):Fk v<=2^128:=by unfold Fk;split_ifs with d;. positivity . have b:((2^23+v%2^23:ℕ):ℝ)<=2^24:=by have:2^23+v%2^23<=2^24:=א;exact_mod_cast this have a:(2:ℝ)^(((v/2^23:ℕ):ℤ)-150)<=2^(104:ℤ):=Ф ב א;have c:(2:ℝ)^(104:ℤ)=2^104:=ב;rw[c] at a calc _<=(2:ℝ)^24*2^104:=г b a (by positivity) (by positivity) _=2^128:=ב lemma BK (a b:ℕ) (d:a<=b) (e:a=0∨2^23<=a):Fk a<=Fk b:=by rcases e with rfl | e;. simpa [Fk] using BH b unfold Fk;simp only[show¬a=0 by omega,show¬b=0 by omega,↓reduceIte];have c:a/2^23<=b/2^23:=Nat.div_le_div_right d;rcases c.eq_or_lt with f | j;. rw[f];apply Б _ (by positivity);have:2^23+a%2^23<=2^23+b%2^23:=א;exact_mod_cast this . have g:((2^23+a%2^23:ℕ):ℝ)<=2^23*2:=by have:2^23+a%2^23<=2^23*2:=א;exact_mod_cast this have h:(2:ℝ)^(((a/2^23:ℕ):ℤ)-150)*2<=2^(((b/2^23:ℕ):ℤ)-150):=by rw[<-zpow_add_one₀ ב];exact Ф ב א have i:(2:ℝ)^23<=((2^23+b%2^23:ℕ):ℝ):=by have:2^23<=2^23+b%2^23:=א;exact_mod_cast this calc _<=((2:ℝ)^23*2)*2^(((a/2^23:ℕ):ℤ)-150):= Б g (by positivity) _=2^23*(2^(((a/2^23:ℕ):ℤ)-150)*2):=by ring _<=_:=г i h (by positivity) (by positivity) lemma BL (w:UInt32) (j:FY w=true):(dv w).isFinite=true∧R (dv w)=wv w:=by have r:=w.toNat_lt;have b:=BG w j;have c:=BF w;have d:=A2 ((w&&&0x7FFFFF) ||| 0x800000) (by rw[c];omega);have m:(w>>>(23:UInt32)).toUSize.toNat=w.toNat/2^23:=by rw[Т,BC] have e:=A8 (w.toNat/2^23) א;unfold dv;rw[A9,m];have f: |R ((w&&&0x7FFFFF) ||| 0x800000).toFloat| ≤2^24:=by rw[d.2,c,У (Э _)];have:2^23+w.toNat%2^23<=2^24:=א;exact_mod_cast this have g: |R (FX (w.toNat/2^23))| ≤2^106:=by rw[e.2];split_ifs;. simp all_goals simp only[abs_mul,abs_neg,abs_one,one_mul];rw[abs_of_pos (by positivity)];have:(2:ℝ)^(((w.toNat/2^23%256:ℕ):ℤ)-150)<=2^(106:ℤ):=Ф ב א;simpa using this have n: |R ((w&&&0x7FFFFF) ||| 0x800000).toFloat| * |R (FX (w.toNat/2^23))| ≤2^(1000:ℤ):=by have h:=Aq;have e1:(2:ℝ)^24<=2^256*2^42:=ב;have e2:(2:ℝ)^106<=2^256*2^42:=ב;exact (г (f.trans (e1.trans h)) (g.trans (e2.trans h)) (П _) Ap.le).trans As obtain ⟨o,p⟩:=Am _ _ d.1 e.1 n;refine ⟨o,?_⟩;rw[p,d.2,e.2,BI w j,c];rcases b with q | ⟨h,s⟩;. have e0:w.toNat/2^23%256=0:=א;rw[q];simp only[e0,↓reduceIte,mul_zero,Model.roundAt_zero];simp[Fk] . have e0:¬w.toNat/2^23%256=0:=א;have e1:w.toNat%2^31/2^23=w.toNat/2^23%256:=א;have e2:w.toNat%2^31%2^23=w.toNat%2^23:=א;have e3:(256<=w.toNat/2^23)↔2^31<=w.toNat:=א;unfold Fk;rw[e1,e2];simp only[e0,e3,show¬w.toNat%2^31=0 by omega,↓reduceIte];have i:-1074<=((w.toNat/2^23%256:ℕ):ℤ)-150:=א;have a:2^23+w.toNat%2^23<2^53:=א;generalize ((w.toNat/2^23%256:ℕ):ℤ)-150=k at i⊢;generalize 2^23+w.toNat%2^23=M at a⊢;by_cases l:2^31<=w.toNat;. have:=Ax (-(M:ℤ)) k (by simpa using a) i;simp only[l,↓reduceIte];push_cast at this;rw[show (M:ℝ)*(-1*2^k)=-(M:ℝ)*2^k by ring,show -1*((M:ℝ)*2^k)=-(M:ℝ)*2^k by ring];exact this . have:=Ax (M:ℤ) k (by simpa using a) i;simp only[l,↓reduceIte,one_mul];push_cast at this;exact this def Fl (l:List Float):Float:=l.foldl (.+·) 0 noncomputable def Fm (l:List Float):ℝ:=(l.map λq=>|R q|).sum noncomputable def Fn (l:List Float):ℝ:=(l.map R).sum lemma BM (l:List Float):0<=Fm l:=by induction l with | nil=>simp[Fm] | cons q l ih=>simp only[Fm,List.map_cons,List.sum_cons] at ih⊢;positivity lemma BN (l:List Float) (q:Float):Fm (l++[q])=Fm l+ |R q|:=by simp[Fm] lemma BO (l:List Float) (q:Float):Fn (l++[q])=Fn l+R q:=by simp[Fn] lemma BP (l:List Float) (q:Float):Fl (l++[q])=Fl l+q:=by simp[Fl] lemma BQ (l:List Float): |Fn l| ≤Fm l:=by induction l with | nil=>simp[Fm,Fn] | cons q l ih=>simp only[Fm,Fn,List.map_cons,List.sum_cons] at ih⊢;exact (Ч _ _).trans ד lemma BR (l:List Float) (o:∀q∈l,q.isFinite=true) (c:l.length<=2^21) (p:Fm l<=Fh/4): (Fl l).isFinite=true∧ |R (Fl l)-Fn l| ≤2*l.length*(1/2^53*(Fm l+Fg)):=by induction l using List.reverseRecOn with | nil=> simp only[Fl,List.foldl_nil,List.length_nil] refine ⟨A5.1,?_⟩ simp[A5.2,Fn] | append_singleton l q ih=> rw[BN] at p have I:=BM l have f:=П (R q) obtain ⟨v,s⟩:=ih (λx w=>o x (by simp[w])) (by simp at c;omega) ד have t:(l.length:ℝ)+1<=2^21:=by simp at c exact_mod_cast c have y:(0:ℝ)<=l.length:=Э _ have u:=BQ l have i:=An have d:=Ao have J:=Ap have g:=Aq rw[BP,BN,BO,List.length_append,List.length_singleton] have z:(8:ℝ)<=Fh:=by have:(8:ℝ)<=2^256*2^42:=ב linarith only [i,d,g] have A:Fg<=1:=by have:(1/2^200*(1/2^200):ℝ)<=1:=ב linarith only [i,d] push_cast set r:=R (Fl l) set a:=R q set P:=Fm l set S:=Fn l set k:ℝ:=(l.length:ℝ) set W:=(1/2^53:ℝ)*(P+ |a| +Fg) with b have B:(1/2^53:ℝ)*(P+Fg)<=W:=by rw[b] apply Й _ ב linarith only [f] have j:0<=W:=by rw[b];positivity have C: |r-S| ≤2*k*W:=s.trans (Й B (by positivity)) have h:2*k*(1/2^53)<=1:=by norm_num at t⊢ linarith only [i,d,t] have m:(1/2^53:ℝ)* |r-S| ≤W:= calc (1/2^53:ℝ)* |r-S| ≤1/2^53*(2*k*W):= Й C ב _=(2*k*(1/2^53))*W:=by ring _<=1*W:=Б h j _=W:=one_mul _ have D: |r-S| ≤P+1:= calc |r-S| ≤2*k*(1/2^53*(P+Fg)):=s _=(2*k*(1/2^53))*(P+Fg):=by ring _<=1*(P+Fg):=Б h (by positivity) _<=P+1:=ד have E: |r| ≤Fh:=by have e:r=(r-S)+S:=by ring have:=Ч (r-S) S rw[<-e] at this linarith only [i,d,g,f,p,u,b,m,this] have F: |a| ≤Fh:=ד obtain ⟨n,K⟩:=Au (Fl l) q v (o q ג) E F refine ⟨n,?_⟩ have t1: |R (Fl l+q)-(S+a)| ≤ |R (Fl l+q)-(r+a)| + |r-S|:=by have e:R (Fl l+q)-(S+a)=(R (Fl l+q)-(r+a))+(r-S):=by ring rw[e] exact Ч _ _ have t2: |r+a| ≤ |r-S| +P+ |a|:=by have e:r+a=(r-S)+S+a:=by ring rw[e] have G:=Ч ((r-S)+S) a have H:=Ч (r-S) S linarith only [u,G,H] have t3:(1/2^53:ℝ)*(|r+a| +Fg)<=1/2^53* |r-S| +W:=by rw[b,<-mul_add] apply Й _ ב linarith only [t2] calc |R (Fl l+q)-(S+a)| ≤W+W+2*k*W:=ד _=2*(k+1)*W:=by ring lemma BS (n:ℕ) (l:n<2^20):(Fe n).isFinite=true∧R (Fe n)=((n:ℝ)+8)/2^51:=by have a:(n.toUInt64+8).toNat=n+8:=by have g:(8:UInt64).toNat=8:=rfl;simp[UInt64.toNat_add,g];omega have b:=A3 (n.toUInt64+8) (by rw[a];omega);have c:(Float.ofBits 0x3CC0000000000000).toModel.unpack=.finite .positive (2^52) (-103) (by decide):=by rfl have h:(Float.ofBits 0x3CC0000000000000).isFinite=true:=by change (Float.ofBits 0x3CC0000000000000).toModel.unpack.isFinite=true;rw[c];rfl have d:R (Float.ofBits 0x3CC0000000000000)=1/2^51:=by rw[Ay,c,Model.unpackedToReal_finite,Ae];simp;norm_num have i:(n:ℝ)+8<=2^21:=by have:n+8<=2^21:=א;exact_mod_cast this obtain ⟨j,k⟩:=Am _ _ b.1 h (by rw[b.2,d,a];have m:(1:ℝ)<=2^256*2^42:=ב;have f:=Aq;have o:(2:ℝ)^21<=2^256*2^42:=ב;refine ظ (г ?_ ?_ (П _) Ap.le) As;. rw[Nat.cast_add,У (by positivity)];push_cast;linarith only [i,f] . rw[У (by positivity)];have:(1:ℝ)/2^51<=1:=ב linarith only [f]) unfold Fe;refine ⟨j,?_⟩;rw[k,b.2,d,a];have:=Ax ((n:ℤ)+8) (-51) א ב;push_cast at this⊢;have e:(2:ℝ)^(-51:ℤ)=1/2^51:=ב;rw[e] at this;rw[this];ring lemma BT (c Y S T E z:ℝ) (u:8<=c) (b:c<=2^20+8) (i:z<=1/2^200*(1/2^200)) (j:0<=Y) (v: |S| ≤2*Y) (w: |T-Y| ≤Y/2^30+1/2^250) (k: |E-c/2^51*T| ≤1/2^53*(|c/2^51*T| +z)) (f:1/2^127≤ |S+E| +1/2^53*(|S+E| +z)):4*(c-7)*(1/2^53*Y)+1/2^53*(|S| + |E| +z)(first | linarith only [j,l] | linarith only [j,m] | linarith) have o:c/2^51<=1/2^30:=by have:(2:ℝ)^20+8<=2^21:=ב calc c/2^51<=2^21/2^51:=by gcongr;linarith only [b] _=1/2^30:=ב set G:=c/2^51*T with a have y: |G| ≤(2*Y+1/2^250)/2^30:=by rw[a,abs_mul,abs_of_pos (by positivity)] calc _<=(1/2^30:ℝ)*(2*Y+1/2^250):= г o n (П _) (by positivity) _=_:=by ring have g: |E| ≤ |E-G| + |G|:=by have e:E=(E-G)+G:=by ring have:=Ч (E-G) G;rwa [<-e] at this have p:=Ч S E;have A:=П G;have B:=П E;have C:1/2^129<=Y:=ד;have D:Y-Y/2^30-1/2^250<=T:=ד;have F:0<=Y-Y/2^30-1/2^250:=ד;have H:0<=T:=ד;have q:0<=G:=by rw[a];positivity rw[У q] at k g y;have r:=(abs_le.mp k).1;have h:c*(Y-Y/2^30-1/2^250)/2^51<=G:=by rw[a,show c/2^51*T=c*T/2^51 by ring];gcongr have s:c*Y<=2^21*Y:=by have:c<=2^21:=by have:(2:ℝ)^20+8<=2^21:=ב;linarith only [b] exact Б this j have t:c*(Y-Y/2^30-1/2^250)=c*Y-c*Y/2^30-c*(1/2^250):=by ring rw[t] at h have I:c*(1/2^250)<=2^21*(1/2^250):=by have:c<=2^21:=by have:(2:ℝ)^20+8<=2^21:=ב;linarith only [b] exact Б this (by positivity) have d:4*(c-7)*(1/2^53*Y)=c*Y/2^51-28*Y/2^53:=by ring rw[d];linarith only [b,i,v,f,k,g,p,r,h,s] lemma BU (n:ℕ) (C:n<2^20) (s t:Float) (D:s.isFinite=true) (G:t.isFinite=true) (X Y:ℝ) (d:0<=Y) (q:Y<=Fh/8) (H: |R s-X| ≤4*((n:ℝ)+1)*(1/2^53*Y)) (E: |R t-Y| ≤Y/2^30+1/2^250) (I: |R s| ≤2*Y) (c:(2:ℝ)^(-127:ℤ)≤ |R (s+Fe n*t)|):R (s-Fe n*t)(first | linarith only [p,key,z,B] | linarith only [o,key,y,A] | linarith) lemma BV (g h:ℕ->Float) (l:List ℕ) (a b:Float): l.foldl (λ(acc:F1) t=>F1.mk (acc.s+g t) (acc.t+h t)) ⟨a,b⟩=⟨(l.map g).foldl (.+·) a,(l.map h).foldl (.+·) b⟩:=by induction l generalizing a b with | nil=>rfl | cons x l ih=>simp only[List.foldl_cons,List.map_cons,ih] lemma BW (l:List Float) (c:∀q∈l,q.isFinite=true):Fm (l.map Float.abs)=Fm l∧Fn (l.map Float.abs)=Fm l:=by induction l with | nil=>simp[Fm,Fn] | cons q l ih=>obtain ⟨a,b⟩:=ih (λx d=>c x (by simp[d]));have e:=(A0 q (c q ג)).2;simp only[Fm,Fn,List.map_cons,List.sum_cons,List.map_map] at a b⊢;simp only[Function.comp_def,e,abs_abs];simp only[Function.comp_def] at a b;rw[a,b];simp lemma BX (ts:List ℕ) (q:ℕ->Float) (p:ℕ->ℝ) (i:∀t∈ts,|R (q t)-p t| ≤1/2^53*(|p t| +Fg)): |Fn (ts.map q)-(ts.map p).sum| ≤1/2^53*((ts.map λt=>|p t|).sum+ts.length*Fg)∧ Fm (ts.map q)<=(ts.map λt=>|p t|).sum+1/2^53*((ts.map λt=>|p t|).sum+ts.length*Fg)∧ (ts.map λt=>|p t|).sum<=2*Fm (ts.map q)+ts.length*Fg:=by induction ts with | nil=>simp[Fm,Fn] | cons x ts ih=> obtain ⟨a,b,c⟩:=ih (λt j=>i t (by simp[j])) have d:=i x ג simp only[Fm,Fn,List.map_cons,List.sum_cons,List.map_map,List.length_cons] at a b c⊢ simp only[Function.comp_def] at a b c⊢ have k:=An obtain ⟨l,m⟩:=abs_le.mp d obtain ⟨n,o⟩:=abs_le.mp a have f: |p x| ≤ |R (q x)| +1/2^53*(|p x| +Fg):=by have e:p x=R (q x)-(R (q x)-p x):=by ring have:=abs_sub (R (q x)) (R (q x)-p x) rw[<-e] at this linarith only [d,this] have g: |R (q x)| ≤ |p x| +1/2^53*(|p x| +Fg):=by have e:R (q x)=p x+(R (q x)-p x):=by ring have:=Ч (p x) (R (q x)-p x) rw[<-e] at this linarith only [d,this] have h:=П (p x) refine ⟨abs_le.mpr ⟨?_,?_⟩,?_,?_⟩<;>push_cast<;>(first | linarith only [l,n] | linarith only [m,o] | linarith only [b,g] | linarith only [c,k,f,h] | linarith) lemma BY (ts:List ℕ) (f:ℕ->ℝ) (M:ℝ) (h:∀t∈ts,f t<=M):(ts.map f).sum<=ts.length*M:=by induction ts with | nil=>simp | cons x ts ih=>have a:=ih (λt b=>h t (by simp[b]));have c:=h x ג;simp only[List.map_cons,List.sum_cons,List.length_cons];push_cast;linarith only [a,c] lemma BZ (w:UInt32) (a:FY w=true): |wv w| =Fk (w.toNat%2^31):=by rw[BI w a,abs_mul,У (BH _)];split_ifs<;>simp lemma Ba (w:UInt32) (a:FY w=true): |wv w| ≤2^128:=by rw[BZ w a];apply BJ;rcases BG w a with h | h<;>omega lemma Bb (w:UInt32) (a:FY w=true) (h:w&&&0x7FFFFFFF=0):wv w=0:=by rw[BI w a,<-BA w,h];simp[Fk] lemma Bc:(2:ℝ)^128<=Fh:=by have h:(2:ℝ)^128<=2^256*2^42:=ב;linarith [Aq] lemma Bd (a b:UInt32) (d:FY a=true) (e:FY b=true): (dv a*dv b).isFinite=true∧ |R (dv a*dv b)-wv a*wv b| ≤1/2^53*(|wv a*wv b| +Fg)∧ |wv a*wv b| ≤2^256:=by obtain ⟨fa,ra⟩:=BL a d obtain ⟨fb,rb⟩:=BL b e have la:=Ba a d have lb:=Ba b e have c: |wv a*wv b| ≤2^256:=by rw[abs_mul] calc |wv a| * |wv b| ≤2^128*2^128:=г la lb (П _) (by positivity) _=2^256:=ב obtain ⟨g,f⟩:=Aw _ _ fa fb (by rw[ra];exact la.trans Bc) (by rw[rb];exact lb.trans Bc) rw[ra,rb] at f exact ⟨g,f,c⟩ lemma Be (n:ℕ) (xw ww:ℕ->UInt32) (bw:UInt32) (l:List ℕ) (d:l.Nodup) (b:∀t∈l,tt∉l->wv (xw t)*wv (ww t)=0):Fd n xw ww bw=(l.map λt=>wv (xw t)*wv (ww t)).sum+wv bw:=by unfold Fd;congr 1;rw[<-List.sum_toFinset _ d];symm;apply Finset.sum_subset;. intro t a;simp only[List.mem_toFinset] at a;simpa using b t a . intro t a c;exact e t (by simpa using a) (by simpa using c) lemma Bf (n:ℕ) (xw ww:ℕ->UInt32) (bw:UInt32) (c:∀t,tFY (xw t)=true) (d:∀t,tFY (ww t)=true) (l:List ℕ) (e:l.Nodup) (a:∀t∈l,tt∉l->xw t&&&0x7FFFFFFF=0∨ww t&&&0x7FFFFFFF=0):Fd n xw ww bw=(l.map λt=>wv (xw t)*wv (ww t)).sum+wv bw:= Be n xw ww bw l e a λt b g=>by rcases f t b g with h | h . simp[Bb (xw t) (c t b) h] . simp[Bb (ww t) (d t b) h] lemma Bg (n:ℕ) (l:List ℕ) (c:l.Nodup) (a:∀t∈l,tFloat) (p:ℕ->ℝ) (b:Float) (bv:ℝ) (W:∀t∈ts,(g t).isFinite=true∧|R (g t)-p t| ≤1/2^53*(|p t| +Fg)∧ |p t| ≤2^256) (X:b.isFinite=true) (Z:R b=bv) (D: |bv| ≤2^128) (E:(2:ℝ)^(-127:ℤ)≤ |R (Fl (ts.map g++[b])+Fe n*Fl ((ts.map g++[b]).map Float.abs))|): R (Fl (ts.map g++[b])-Fe n*Fl ((ts.map g++[b]).map Float.abs))<(ts.map p).sum+bv∧ (ts.map p).sum+bv(W t F).2.1) have c:=BY ts (λt=>|p t|) _ (λt F=>(W t F).2.2) have r:=BN (ts.map g) b have s:=BO (ts.map g) b have al:=BM (ts.map g) have d:=BM (ts.map g++[b]) rw[Z] at r s have V:(ts.length:ℝ)<=n:=by exact_mod_cast C have G:(0:ℝ)<=ts.length:=Э _ have l:(n:ℝ)+1<=2^20:=by exact_mod_cast hn have j:=An have a:=Ao have ad:Fg<=1:=by have:(1/2^200*(1/2^200):ℝ)<=1:=ב linarith only [j,a] have ap:0<=(ts.map λt=>|p t|).sum:=List.sum_nonneg (by simp only[List.mem_map];rintro _ ⟨t,_,rfl⟩;exact П _) set A:=(ts.map λt=>|p t|).sum set k:ℝ:=(ts.length:ℝ) have H:k*Fg<=2^20:=by calc k*Fg<=k*1:=mul_le_mul_of_nonneg_left ad G _<=2^20:=by dsimp [k];linarith only [V,l] have aq:A<=2^20*2^256:=by refine c.trans (Б ?_ (by positivity)) linarith only [l,j,a,V] have u:=Aq have am:(2:ℝ)^20*2^256*3+2^128+2^20+2<=2^256*2^42/8:=by norm_num have an:Fm (ts.map g++[b])+Fg<=Fh/8:=by have hU:(1/2^53:ℝ)*(A+k*Fg)<=A+k*Fg:=by have:0<=A+k*Fg:=by positivity linarith only [o,ab] linarith only [D,r,l,j,a,V,o,c,H,u] have ar:(1:ℝ)<=Fh/8:=by have:(1:ℝ)<=2^256*2^42/8:=ב linarith only [j,a,u] have f:(ts.map g++[b]).length<=2^21:=by simp;omega obtain ⟨ae,v⟩:=BR _ m f ד obtain ⟨i,w⟩:=BW _ m obtain ⟨af,y⟩:=BR ((ts.map g++[b]).map Float.abs) (by intro q U obtain ⟨x,hx,rfl⟩:=List.mem_map.mp U exact (A0 x (m x hx)).1) (by simpa using f) (by rw[i];linarith only [D,r,l,j,a,V,o,c,H,u]) rw[i,w] at y have ag:(((ts.map g++[b]).length:ℕ):ℝ)=k+1:=by simp[k] have ah:(((ts.map g++[b]).map Float.abs).length:ℝ)=k+1:=by simp[k] rw[ag] at v rw[ah] at y generalize I:Fm (ts.map g++[b])=sa at* set Y:=sa+Fg with z have J:0<=Y:=by positivity have K:0<=(1/2^53:ℝ)*Y:=by positivity have B:2*(k+1)*(1/2^53*Y)<=Y/2^30:=by have h:k+1<=2^20:=ד have:=Б h K norm_num at this⊢ linarith only [j,d,this] have ai: |Fn (ts.map g++[b])| ≤ sa:=by rw[<-I];exact BQ _ obtain ⟨L,M⟩:=abs_le.mp v obtain ⟨N,O⟩:=abs_le.mp y refine BU n hn _ _ ae af _ Y J ד ?_ ?_ ?_ E . have au:sa+k*Fg<=(k+1)*Y:=by rw[z];linarith [Ь G d] have P:(1/2^53:ℝ)*(A+k*Fg)<=2*(k+1)*(1/2^53*Y):=by have h1:A+k*Fg<=2*(sa+k*Fg):=by linarith [П bv] have h2:A+k*Fg<=2*((k+1)*Y):=ד calc (1/2^53:ℝ)*(A+k*Fg)<=1/2^53*(2*((k+1)*Y)):= Й h2 ב _=_:=by ring have Q:4*(k+1)*(1/2^53*Y)<=4*((n:ℝ)+1)*(1/2^53*Y):=Б ד K;obtain ⟨S,T⟩:=abs_le.mp aa;apply abs_le.mpr;constructor<;>(first | linarith only [s,L,P,Q,S] | linarith only [s,M,P,Q,T] | linarith) . apply abs_le.mpr;constructor . have:(0:ℝ)<=1/2^250:=ב;have:Fg<=1/2^250:=by have:(1/2^200*(1/2^200):ℝ)<=1/2^250:=ב;linarith only [j,a] linarith only [j,a,B,N] . linarith only [j,a,B,O] . have e:R (Fl (ts.map g++[b]))=(R (Fl (ts.map g++[b]))-Fn (ts.map g++[b]))+Fn (ts.map g++[b]):=by ring have h1:=Ч (R (Fl (ts.map g++[b]))-Fn (ts.map g++[b])) (Fn (ts.map g++[b]));rw[<-e] at h1;have h2:Y/2^30<=Y:=by apply div_le_self J;norm_num linarith only [j,d,v,B,ai,h1] lemma Bi (n:Nat) (x:n<2^20) (xw ww:Nat->UInt32) (bw:UInt32) (m:∀t,tFY (xw t)=true) (o:∀t,tFY (ww t)=true) (u:FY bw=true) (l:List Nat) (v:l.Nodup) (a:∀t∈l,tt∉l->xw t&&&0x7FFFFFFF=0∨ww t&&&0x7FFFFFFF=0) (s e:Float) (z:let r:=l.foldl (λ(acc:F1) t=>let q:=dv (xw t)*dv (ww t) F1.mk (acc.s+q) (acc.t+q.abs)) ⟨0,0⟩;s=r.s+dv bw∧e=Fe n*(r.t+(dv bw).abs)) (b:(2:ℝ)^(-127:ℤ)≤ |R (s+e)|): R (s-e)Float:=λt=>dv (xw t)*dv (ww t) with C set p:ℕ->ℝ:=λt=>wv (xw t)*wv (ww t) with D have c:l.foldl (λ(acc:F1) t=>let q:=dv (xw t)*dv (ww t) F1.mk (acc.s+q) (acc.t+q.abs)) ⟨0,0⟩= ⟨(l.map g).foldl (.+·) 0,(l.map λt=>(g t).abs).foldl (.+·) 0⟩:= BV g (λt=>(g t).abs) l 0 0 obtain ⟨d,f⟩:=z rw[c] at d f have h:=Bg n l v a have i:∀t∈l,(g t).isFinite=true∧|R (g t)-p t| ≤1/2^53*(|p t| +Fg)∧ |p t| ≤2^256:=λt w=>Bd _ _ (m t (a t w)) (o t (a t w)) obtain ⟨j,k⟩:=BL bw u have A:s=Fl (l.map g++[dv bw]):=by rw[d,BP];rfl have B:e=Fe n*Fl ((l.map g++[dv bw]).map Float.abs):=by rw[f] congr 1 rw[List.map_append,List.map_map,List.map_singleton,BP] rfl rw[A,B] at b⊢ rw[Bf n xw ww bw m o l v a y] exact Bh n x l h g p (dv bw) (wv bw) i j k (Ba bw u) b lemma Bj (n:Nat) (c:n<2^20) (xw ww:Nat->UInt32) (bw:UInt32) (d:∀t,tFY (xw t)=true) (f:∀t,tFY (ww t)=true) (g:FY bw=true) (l:List Nat) (h:l.Nodup) (b:∀t∈l,tt∉l->xw t&&&0x7FFFFFFF=0) (s e:Float) (j:let r:=l.foldl (λ(acc:F1) t=>let q:=dv (xw t)*dv (ww t) F1.mk (acc.s+q) (acc.t+q.abs)) ⟨0,0⟩;s=r.s+dv bw∧e=Fe n*(r.t+(dv bw).abs)) (a:(2:ℝ)^(-127:ℤ)≤ |R (s+e)|): R (s-e)Or.inl (i t k m)) s e j a lemma Bk (H J Rj Rg Rt b z k:ℝ) (a:0<=H) (q:H<=2^128) (o:0<=J) (j:0<=b) (c:0<=z) (d:z<=1/2^200*(1/2^200)) (r:k<=2^20) (s: |Rj-J| ≤2*k*(1/2^53*(J+z))) (t: |Rg-H*Rj| ≤1/2^53*(|H*Rj| +z)) (u: |Rt-(Rg+b)| ≤1/2^53*(|Rg+b| +z)): |Rt-(H*J+b+z)| ≤(H*J+b+z)/2^30+1/2^250:=by have e1: |Rj-J| ≤(J+z)/2^32:=by refine s.trans ?_ have h:0<=(1/2^53:ℝ)*(J+z):=Ь ב (add_nonneg o c) have:=Б r h norm_num at this⊢ linarith only [this] have e2: |H*Rj-H*J| ≤(H*J+H*z)/2^32:=by rw[<-mul_sub,abs_mul,У a] calc H* |Rj-J| ≤H*((J+z)/2^32):=Й e1 a _=_:=by ring have e3:H*z<=1/2^250:=by calc H*z<=2^128*(1/2^200*(1/2^200)):= г q d c ב _<=1/2^250:=ב have e:0<=H*J:=Ь a o have v:0<=H*z:=Ь a c generalize H*J=W at* generalize H*z=Z at* generalize H*Rj=G at* obtain ⟨e2a,e2b⟩:=abs_le.mp e2 obtain ⟨f,g⟩:=abs_le.mp t obtain ⟨l,m⟩:=abs_le.mp u have i: |G| ≤W+(W+Z)/2^32:=by apply abs_le.mpr constructor<;>(first | linarith only [e,e2a] | linarith only [e2b] | linarith) have n: |Rg| ≤2*W+1/2^200:=by apply abs_le.mpr constructor<;>(first | linarith only [d,e,e3,e2a,f,i] | linarith only [d,e,e3,e2b,g,i] | linarith) have p: |Rg+b| ≤2*W+b+1/2^200:=by have:=Ч Rg b rw[У j] at this linarith only [n,this] apply abs_le.mpr constructor<;>(first | linarith only [j,d,e,e3,e2a,f,l,i,p] | linarith only [j,c,e,e3,e2b,g,m,i,p] | linarith) lemma Bl (ts:List ℕ) (f g:ℕ->ℝ) (H:ℝ) (h:∀t∈ts,f t<=H*g t):(ts.map f).sum<=H*(ts.map g).sum:=by induction ts with | nil=>simp | cons x ts ih=>have a:=ih (λt b=>h t (by simp[b]));have c:=h x ג;simp only[List.map_cons,List.sum_cons,mul_add];linarith only [a,c] lemma Bm (n:ℕ) (hn:n<2^20) (ts:List ℕ) (E:ts.length<=n) (g:ℕ->Float) (p:ℕ->ℝ) (b f a:Float) (bv H J K:ℝ) (hg:∀t∈ts,(g t).isFinite=true∧|R (g t)-p t| ≤1/2^53*(|p t| +Fg)) (s:(ts.map λt=>|p t|).sum<=H*J) (F:b.isFinite=true) (G:R b=bv) (ae: |bv| ≤2^128) (hf:f.isFinite=true) (hH:R f=H) (l:0<=H) (u:H<=2^128) (af:a.isFinite=true) (m:0<=J) (I:J<=2^149) (hK:K<=2^20) (L: |R a-J| ≤2*K*(1/2^53*(J+Fg))) (M:(2:ℝ)^(-127:ℤ)≤ |R (Fl (ts.map g++[b])+Fe n*(f*a+b.abs))|): R (Fl (ts.map g++[b])-Fe n*(f*a+b.abs))<(ts.map p).sum+bv∧(ts.map p).sum+bv(hg t ht).2) have v:=BN (ts.map g) b have w:=BO (ts.map g) b have a4:=BM (ts.map g++[b]) rw[G] at v w have hk:(ts.length:ℝ)<=n:=by exact_mod_cast E have ak:(0:ℝ)<=ts.length:=Э _ have a9:(n:ℝ)+1<=2^20:=by exact_mod_cast hn have d:=An have c:=Ao have ba:Fg<=1:=by have:(1/2^200*(1/2^200):ℝ)<=1:=ב linarith only [d,c] have o:0<=(ts.map λt=>|p t|).sum:=List.sum_nonneg (by simp only[List.mem_map];rintro _ ⟨t,_,rfl⟩;exact П _) set A:=(ts.map λt=>|p t|).sum set k:ℝ:=(ts.length:ℝ) have r:=Aq have bb:(1:ℝ)<=Fh/8:=by have:(1:ℝ)<=2^256*2^42/8:=ב linarith only [d,c,r] have al:k<=2^20:=ד have am:2*K*(1/2^53)<=1:=by norm_num at hK⊢ linarith only [d,c,hK] have O: |R a-J| ≤J+1:= calc |R a-J| ≤2*K*(1/2^53*(J+Fg)):=L _=(2*K*(1/2^53))*(J+Fg):=by ring _<=1*(J+Fg):=Б am ד _<=J+1:=ד have P: |R a| ≤2^151:=by have e:R a=(R a-J)+J:=by ring have j:=Ч (R a-J) J rw[<-e,У m] at j have:(2:ℝ)*2^149+1<=2^151:=ב linarith only [I,d,c,O,j] have Q:(2:ℝ)^151<=Fh:=by have:(2:ℝ)^151<=2^256*2^42:=ב linarith only [d,c,r] obtain ⟨an,x⟩:=Aw f a hf af (by rw[hH,У l];linarith [Bc]) (P.trans Q) rw[hH] at x have ao: |H*R a| ≤2^128*2^151:=by rw[abs_mul,У l] exact г u P (П _) ב have ap: |R (f*a)| ≤Fh:=by have e:R (f*a)=(R (f*a)-H*R a)+H*R a:=by ring have j:=Ч (R (f*a)-H*R a) (H*R a) rw[<-e] at j have:(2:ℝ)^128*2^151*2+1<=2^256*2^42:=ב have h2:(1/2^53:ℝ)*(|H*R a| +Fg)≤ |H*R a| +1:=by have:=П (H*R a) linarith only [d,c,this] linarith only [d,c,r,x,ao,j] obtain ⟨aq,y⟩:=A0 b F rw[G] at y obtain ⟨ar,S⟩:=Au (f*a) b.abs an aq ap (by rw[y,abs_abs];linarith [Bc]) rw[y] at S have key2:=Bk H J (R a) (R (f*a)) (R (f*a+b.abs)) |bv| Fg K l u m (П _) d.le c hK L x S have as:H*J<=2^128*2^149:=г u I m ב have a6:0<=H*J:=Ь l m have i:=П bv have T:k*Fg<=2^20*Fg:=Б al d.le have au:H*J+ |bv| +Fg<=Fh/8:=by have:(2:ℝ)^128*2^149+2^128+1<=2^256*2^42/8:=ב linarith only [ae,d,c,r,as] have U:Fm (ts.map g++[b])+Fg<=3/2*(H*J+ |bv| +Fg):=by linarith only [v,d,s,o,N,i,T] have z:(ts.map g++[b]).length<=2^21:=by simp;omega obtain ⟨av,B⟩:=BR _ ah z ד have aw:(((ts.map g++[b]).length:ℕ):ℝ)=k+1:=by simp[k] rw[aw] at B have ax:=BQ (ts.map g++[b]) set Y:=H*J+ |bv| +Fg with ay have V:0<=Y:=ד have W:0<=(1/2^53:ℝ)*Y:=Ь ב V have C:2*(k+1)*(1/2^53*(Fm (ts.map g++[b])+Fg))≤3*(k+1)*(1/2^53*Y):= calc 2*(k+1)*(1/2^53*(Fm (ts.map g++[b])+Fg)) <=2*(k+1)*(1/2^53*(3/2*Y)):=by apply Й _ ד exact Й U ב _=_:=by ring have D:A+k*Fg<=(k+1)*Y:=by have j:A+Fg<=Y:=ד have h2:=Й j (ד:0<=k+1) have h3:=Ь ak o linarith only [d,h2,h3] have bd:(1/2^53:ℝ)*(A+k*Fg)<=(k+1)*(1/2^53*Y):= calc (1/2^53:ℝ)*(A+k*Fg)<=1/2^53*((k+1)*Y):= Й D ב _=_:=by ring have X:4*(k+1)*(1/2^53*Y)<=4*((n:ℝ)+1)*(1/2^53*Y):=Б ד W have az:3*(k+1)*(1/2^53*Y)<=Y/2:=by have h:k+1<=2^20:=ד have:=Б h W norm_num at this⊢ linarith only [d,s,o,i,this] obtain ⟨Z,aa⟩:=abs_le.mp B obtain ⟨ab,ad⟩:=abs_le.mp aj refine BU n hn _ _ av ar _ Y V au ?_ key2 ?_ M . apply abs_le.mpr;constructor<;>(first | linarith only [w,C,D,X,Z,ab] | linarith only [w,C,D,X,aa,ad] | linarith) . have e:R (Fl (ts.map g++[b]))=(R (Fl (ts.map g++[b]))-Fn (ts.map g++[b]))+Fn (ts.map g++[b]):=by ring have j:=Ч (R (Fl (ts.map g++[b]))-Fn (ts.map g++[b])) (Fn (ts.map g++[b]));rw[<-e] at j;linarith only [v,d,s,o,N,i,T,B,ax,C,az,j] lemma Bn (n:ℕ) (M:n<2^20) (ts:List ℕ) (k:ts.length<=n) (g v:ℕ->Float) (p a:ℕ->ℝ) (b f:Float) (bv H:ℝ) (r:∀t∈ts,(g t).isFinite=true∧|R (g t)-p t| ≤1/2^53*(|p t| +Fg)∧ |p t| ≤H* |a t|) (s:∀t∈ts,(v t).isFinite=true∧R (v t)=a t∧|a t| ≤2^128) (u:b.isFinite=true) (w:R b=bv) (y: |bv| ≤2^128) (N:f.isFinite=true) (O:R f=H) (z:0<=H) (A:H<=2^128) (d:(2:ℝ)^(-127:ℤ)≤ |R (Fl (ts.map g++[b])+Fe n*(f*Fl (ts.map λt=>(v t).abs)+b.abs))|): R (Fl (ts.map g++[b])-Fe n*(f*Fl (ts.map λt=>(v t).abs)+b.abs))<(ts.map p).sum+bv∧ (ts.map p).sum+bv(v t).abs)+b.abs)):=by have e:(ts.length:ℝ)<=2^20:=by have:ts.length<=2^20:=א exact_mod_cast this have B:0<=(ts.map λt=>|a t|).sum:=List.sum_nonneg (by simp only[List.mem_map];rintro _ ⟨t,_,rfl⟩;exact П _) have l:=BY ts (λt=>|a t|) _ (λt c=>(s t c).2.2) have C:=Bl ts (λt=>|p t|) (λt=>|a t|) H (λt c=>(r t c).2.2) have D:(ts.map λt=>(v t).abs)=(ts.map v).map Float.abs:=by simp[List.map_map,Function.comp_def] have m:∀q∈ts.map v,q.isFinite=true:=by intro q E obtain ⟨t,c,rfl⟩:=List.mem_map.mp E exact (s t c).1 obtain ⟨h,o⟩:=BW (ts.map v) m have F:Fm (ts.map v)=(ts.map λt=>|a t|).sum:=by simp only[Fm,List.map_map] congr 1 apply List.map_congr_left intro t c simp[(s t c).2.1] rw[D] at d⊢ rw[F] at h o set J:=(ts.map λt=>|a t|).sum have G:J<=2^20*2^128:=l.trans (Б e ב) have I:=Aq have i:((ts.map v).map Float.abs).length<=2^21:=by simp;omega obtain ⟨K,j⟩:=BR ((ts.map v).map Float.abs) (by intro q E obtain ⟨x,P,rfl⟩:=List.mem_map.mp E exact (A0 x (m x P)).1) i (by rw[h] have:(2:ℝ)^20*2^128<=2^256*2^42/4:=ב linarith only [e,l,I]) rw[h,o] at j have L:(((ts.map v).map Float.abs).length:ℝ)=(ts.length:ℝ):=by simp rw[L] at j exact Bm n M ts k g p b f _ bv H J _ (λt c=>⟨(r t c).1,(r t c).2.1⟩) C u w y N O z A K B (G.trans ב) e j d lemma Bo (a:UInt32) (e:FY a=true) (g:a<=0x7FFFFFFF): 0<=wv a∧wv a<=2^128∧ ∀w,FY w=true->w&&&0x7FFFFFFF<=a->|wv w| ≤wv a:=by have d:a.toNat<2^31:=by have:=Ж.mp g change a.toNat<=2147483647 at this omega have b:wv a=Fk a.toNat:=by rw[BI a e,Г d] simp only[show¬2^31<=a.toNat by omega,↓reduceIte,one_mul] refine ⟨by rw[b];exact BH _,ظ (le_abs_self _) (Ba a e),?_⟩ intro w c i have f:=Ж.mp i rw[BA] at f rw[BZ _ c,b] apply BK _ _ f rcases BG _ c with h | h . exact Or.inl h . exact Or.inr h.1 lemma Bp (n:Nat) (I:n<2^20) (xw ww:Nat->UInt32) (bw b:UInt32) (i:∀t,tFY (xw t)=true) (f:∀t,tFY (ww t)=true) (F:FY bw=true) (G:FY b=true) (J:∀t,txw t&&&0x7FFFFFFF<=b) (K:b<=0x7FFFFFFF) (l:List Nat) (H:l.Nodup) (a:∀t∈l,tt∉l->xw t&&&0x7FFFFFFF=0∨ww t&&&0x7FFFFFFF=0) (s e:Float) (M:s=l.foldl (λ(acc:Float) t=>acc+dv (xw t)*dv (ww t)) 0+dv bw∧e=Fe n*(dv b*(l.foldl (λ(acc:Float) t=>acc+(dv (ww t)).abs) 0)+(dv bw).abs)) (d:(2:ℝ)^(-127:ℤ)≤ |R (s+e)|): R (s-e)Float:=λt=>dv (xw t)*dv (ww t) with j set p:ℕ->ℝ:=λt=>wv (xw t)*wv (ww t) with k set v:ℕ->Float:=λt=>dv (ww t) with m obtain ⟨o,q⟩:=M obtain ⟨r,u,w⟩:=Bo b G K obtain ⟨x,y⟩:=BL bw F obtain ⟨z,A⟩:=BL b G have B:∀t∈l,(g t).isFinite=true∧|R (g t)-p t| ≤1/2^53*(|p t| +Fg)∧ |p t| ≤wv b* |wv (ww t)|:=by intro t h have c:=a t h obtain ⟨C,D,-⟩:=Bd _ _ (i t c) (f t c) refine ⟨C,D,?_⟩ simp only[k,abs_mul] exact Б (w _ (i t c) (J t c)) (П _) have E:∀t∈l,(v t).isFinite=true∧R (v t)=wv (ww t)∧|wv (ww t)| ≤2^128:=by intro t h obtain ⟨C,D⟩:=BL _ (f t (a t h)) exact ⟨C,D,Ba _ (f t (a t h))⟩ have N:s=Fl (l.map g++[dv bw]):=by rw[o,BP] simp[Fl,List.foldl_map,j] have O:e=Fe n*(dv b*Fl (l.map λt=>(v t).abs)+(dv bw).abs):=by rw[q] simp[Fl,List.foldl_map,m] rw[N,O] at d⊢ rw[Bf n xw ww bw i f l H a L] exact Bn n I l (Bg n l H a) g v p (λt=>wv (ww t)) (dv bw) (dv b) (wv bw) (wv b) B E x y (Ba bw F) z A r u d end section open ExactRuntime FloatLib.Floats.Formats.BinaryInterchange FloatLib.Floats open FloatLib.Floats.ExecFloat.Binary section open Float.Model Float.Model.UnpackedFloat lemma Bq (m K:Nat): (ExtendedMantissa.ofMantissaAndAccuracy m .exact>>>(K+1))=⟨m/2^(K+1),(m/2^K)%2 !=0,decide (m%2^K≠0)⟩:=by show Nat.repeat ExtendedMantissa.shiftRightOne (K+1) _=_ induction K with | zero=> simp[Nat.repeat,ExtendedMantissa.shiftRightOne,ExtendedMantissa.ofMantissaAndAccuracy,Nat.mod_one] | succ K ih=> show ExtendedMantissa.shiftRightOne (Nat.repeat _ (K+1) _)=_ rw[ih] simp only[ExtendedMantissa.shiftRightOne,ExtendedMantissa.mk.injEq] refine ⟨?_,?_,?_⟩ . rw[ذ,<-Nat.pow_succ] . trivial . rw[Nat.mod_pow_succ];have h:0<2^K:=by positivity by_cases a:m%2^K=0<;>by_cases b:m/2^K%2=0<;>simp[a,b];omega lemma Br (H a b:Nat) (c:b>>(K+1)).roundedMantissa=r:=by rw[Bq,Nat.pow_succ];have j:0<2^K:=by positivity generalize 2^K=H at*;have a:=Nat.div_add_mod m (H*2);have b:m%(H*2) simp[ExtendedMantissa.roundedMantissa,ExtendedMantissa.accuracy,Accuracy.roundToNearestEven,d] . have k:H>>(K+1),T):=by unfold shiftToTargetExponent shiftToExponent simp only[a] have i:(T-e).toNat=K+1:=א rw[i,b] simp only[f,Nat.shiftLeft_zero,Int.natCast_zero,Int.sub_zero,g,Bs m K r c d] lemma Bw (r:Nat) (T:Int) (a:2^23<=r) (b:r<2^24) (e:-149<=T): shiftToTargetExponent Format.binary32 r T .exact=(ExtendedMantissa.ofMantissaAndAccuracy r .exact,T):=by have c:=Bu r 23 a b unfold shiftToTargetExponent shiftToExponent simp only[totalExponent,c,Bt] have d:max (((23:Nat):Int)+1+T-24) (-149)=T:=א simp only[d,sub_self,Int.toNat_zero,Int.natCast_zero,Int.add_zero] rfl lemma Bx (T:Int) (c:-150<=T): shiftToTargetExponent Format.binary32 (2^24) T .exact=(ExtendedMantissa.ofMantissaAndAccuracy (2^23) .exact,T+1):=by have a:(2^24:Nat).log2=24:=Bu _ 24 ב ב unfold shiftToTargetExponent shiftToExponent simp only[totalExponent,a,Bt] have b:max (((24:Nat):Int)+1+T-24) (-149)-T=1:=א rw[b] rfl lemma By (s:Sign) (P:Nat) (E:Int) (a:2^23<=P) (b:P<2^24) (d:-149<=E) (e:02*P*2^(g+2)<2*m+2^(g+2)) (c:P=2^23->33554431*2^(g+2)<4*m):UnpackedFloat.round Format.binary32 s m e=.finite s P E h:=by have e1:2^(g+2)=4*2^g:=by rw[ч];ring have e2:2^(g+1)=2*2^g:=by rw[Nat.pow_succ];ring have e3:2^(g+25)=2^25*2^g:=by rw[ч];ring have e4:2^(g+25+1)=2^26*2^g:=by rw[ч,ч];ring have e5:2^(g+24)=2^24*2^g:=by rw[ч];ring have u:0<2^g:=by positivity rw[e1] at b;by_cases i:2^(g+25)<=m . have j:m.log2=g+25:=by apply Bu m _ i;rw[e4];have:(2*P+1)*(4*2^g)<=(2^25-1)*(4*2^g):=З _ א;omega have d:Format.binary32.targetExponent (totalExponent m e)=E:=by simp only[totalExponent,j,Bt];omega rw[Bv s m e E (g+1) P d א ?_ ?_];. exact By s P E k l q h . rw[e2];by_cases f:P=2^23;. subst f;rw[e3] at i;omega . have:=a f;rw[e1] at this;linarith only [this] . rw[e2];linarith only [b] . have f:P=2^23:=by by_contra n;have o:=a n;rw[e1] at o;have v:2*(2^23+1)*(4*2^g)<=2*P*(4*2^g):=З _ א;rw[e3] at i;omega have o:=c f;subst f;rw[e1] at o;rw[e3] at i;have j:m.log2=g+24:=by apply Bu m _ (by rw[e5];omega);rw[show g+24+1=g+25 from rfl,e3];omega by_cases p:-148<=E . have d:Format.binary32.targetExponent (totalExponent m e)=E-1:=by simp only[totalExponent,j,Bt];omega rw[Bv s m e (E-1) g (2^24) d א א א];exact Bz s E p h . have r:E=-149:=א;have d:Format.binary32.targetExponent (totalExponent m e)=E:=by simp only[totalExponent,j,Bt];omega rw[Bv s m e E (g+1) (2^23) d א (by rw[e2];omega) (by rw[e2];omega)];exact By s _ E ב ב q h lemma B1 (neg:Bool) (m:Nat) (e:Int): Model.roundDyadic Fmt ⟨neg,m,e⟩=Model.ofModel Fmt (UnpackedFloat.round Format.binary32 (Model.modelSign neg) m e):=by simp[Model.roundDyadic,Model.ieeeRoundDyadic] rfl lemma B2 (s:Sign):s.toBitVec.toNat=if s=.negative then 1 else 0:=by cases s<;>rfl lemma B3 (s:Sign) (M:Nat) (E:Int) (h:0simp[Nat.shiftLeft_eq] omega lemma B4 (neg:Bool) (m:Nat) (e:Int) (P:Nat) (E:Int) (p:m≠0) (c:2^23<=P) (d:P<2^24) (q:-149<=E) (r:E+150<=254) (j:2*((m:ℝ)*2^e)<(2*P+1)*2^E) (f:P≠2^23->(2*P-1)*2^E<2*((m:ℝ)*2^e)) (h:P=2^23->33554431*2^E<4*((m:ℝ)*2^e)): toWord (Model.roundDyadic Fmt ⟨neg,m,e⟩)=UInt32.ofNat ((if neg then 2^31 else 0)+(E+150).toNat*2^23+P%2^23):=by have s:02*P*2^(g+2)<2*(m*2^k)+2^(g+2):=by intro b have i:=f b rw[n,a] at i have:(2:ℝ)*P*((2^(g+2):Nat):ℝ)<2*((m*2^k:Nat):ℝ)+((2^(g+2):Nat):ℝ):=я ד l.le exact_mod_cast this have i:P=2^23->33554431*2^(g+2)<4*(m*2^k):=by intro b have i:=h b rw[n,a] at i have:(33554431:ℝ)*((2^(g+2):Nat):ℝ)<4*((m*2^k:Nat):ℝ):=я ד l.le exact_mod_cast this rw[B1,<-ExactRuntime.round_scale _ _ m e k p,B0 _ (m*2^k) (e-k) P E g s c d q o t u i] simp only[toWord,Model.toNatBits,Model.ofModel,Model.ofModelBits] congr 1 show (UnpackedFloat.pack Format.binary32 _).toNat=_ rw[B3 _ _ _ _ c d א א] cases neg<;>simp[Model.modelSign] end abbrev Fo:=ExecFloat.Binary.format (exponentBits:=11) (fractionBits:=52) lemma B5 (f:Float):Model.expField (toModel (ofFloat f))=f.toBits.toNat/2^52%2^11:=by show ((f.toBits.toBitVec>>>52)&&&BitVec.ofNat 64 2047).toNat=_;rw[BitVec.toNat_and,BitVec.toNat_ushiftRight,BitVec.toNat_ofNat,Ю];exact В _ 11 lemma B6 (f:Float):Model.fracField (toModel (ofFloat f))=f.toBits.toNat%2^52:=by show (f.toBits.toBitVec&&&BitVec.ofNat 64 (2^52-1)).toNat=_;rw[BitVec.toNat_and,BitVec.toNat_ofNat];exact В _ 52 lemma B7 (f:Float):Model.signBit (toModel (ofFloat f))=decide (2^63<=f.toBits.toNat):=by rw[Model.signBit_eq_msb];show f.toBits.toBitVec.msb=_;rw[BitVec.msb_eq_decide];rfl lemma B8 (f:Float) (s:Bool) (E F:Nat) (m:1<=E) (n:E<2047) (g:F<2^52) (h:f.toBits.toNat=(if s then 2^63 else 0)+E*2^52+F):Model.toDyadic? (toModel (ofFloat f))=some ⟨s,2^52+F,(E:Int)-1075⟩:=by have i:=B5 f;have j:=B6 f;have k:=B7 f;have b:f.toBits.toNat/2^52%2^11=E:=by split at h<;>omega have c:f.toBits.toNat%2^52=F:=by split at h<;>omega have d:decide (2^63<=f.toBits.toNat)=s:=by cases s;. simp only[Bool.false_eq_true,ite_false] at h;simp;omega . simp only[ite_true] at h;simp;omega rw[b] at i;rw[c] at j;rw[d] at k;have l:=Model.ofFields_signBit_expField_fracField (toModel (ofFloat f));rw[i,j,k] at l;rw[<-l];have a:Model.isFinite (Model.ofFields Fo s E F)=true:=by rw[Model.isFinite_ofFields Fo _ _ _ (by show E<2^11;omega) g];show (E !=2047)=true;simp;omega rw[Model.toDyadic?_ofFields_of_isFinite Fo _ _ _ (by show E<2^11;omega) g a];have e:E≠0:=א;simp only[e,ite_false,show Fo.exponentBias=1023 from rfl,show Fo.fracWidth=52 from rfl];simp only[show Model.pow2 52=2^52 from rfl];congr 2;simp only[Int.ofNat_eq_natCast];push_cast;ring lemma B9 (f:Float) (d:FloatLib.Numerics.Dyadic) (h:Model.toDyadic? (toModel (ofFloat f))=some d):f.isFinite=true:=by rw[Model.toDyadic?_ieee_eq_model _ (by decide)] at h;show (Model.toModel (toModel (ofFloat f))).isFinite=true;revert h;generalize Model.toModel (toModel (ofFloat f))=u;cases u<;>simp[Model.unpackedToDyadic?,Float.Model.UnpackedFloat.isFinite] lemma CA (f:Float) (s:Bool) (E F:Nat) (a:1<=E) (c:E<2047) (d:F<2^52) (h:f.toBits.toNat=(if s then 2^63 else 0)+E*2^52+F): f.isFinite=true∧R f=(if s then -1 else 1)*((2^52+F:Nat):ℝ)*2^((E:Int)-1075):=by have b:=B8 f s E F a c d h refine ⟨B9 f _ b,?_⟩ rw[R,Model.toReal_eq,b] cases s<;>simp[FloatLib.Numerics.Dyadic.toReal,FloatLib.Numerics.Dyadic.signedSignificand] def Fp (A:Nat) (S:Bool) (ex fr:Nat):Prop:= ∃M,A=(if S then 2^63 else 0)+M∧(ex*2^23+fr)*2^29>>(29:UInt64)).toNat=(A.toNat+268435455)%2^64/2^29:=by rw[м,Ы];norm_num [Nat.shiftRight_eq_div_pow] lemma CD (x:UInt64):((x>>>(23:UInt64))&&&(0x7FF:UInt64)).toNat=x.toNat/2^23%2^11:=by rw[э,м];have:=В (x.toNat>>>23) 11;norm_num [Nat.shiftRight_eq_div_pow] at this⊢;exact this lemma CE (v:UInt64) (h:v-(897:UInt64)<(254:UInt64)):897<=v.toNat∧v.toNat<1151:=by rw[р,UInt64.toNat_sub] at h;have a:=v.toNat_lt;norm_num at h a;omega lemma CF (x:UInt64) (f:x.toNat<2^35) (g:897<=x.toNat/2^23%2^11) (a:x.toNat/2^23%2^11<1151): (((x>>>(34:UInt64))<<<(31:UInt64)) ||| ((x&&&(0x3FFFFFFFF:UInt64))-((896:UInt64)<<<(23:UInt64)))).toUInt32= UInt32.ofNat ((if decide (2^34<=x.toNat) then 2^31 else 0)+(x.toNat/2^23%2^11-896)*2^23+x.toNat%2^23):=by have b:((x>>>(34:UInt64))<<<(31:UInt64)).toNat=(x.toNat/2^34)*2^31:=by rw[UInt64.toNat_shiftLeft,м] norm_num [Nat.shiftRight_eq_div_pow,Nat.shiftLeft_eq] omega have c:((x&&&(0x3FFFFFFFF:UInt64))-((896:UInt64)<<<(23:UInt64))).toNat=x.toNat%2^34-896*2^23:=by have a:(x&&&(0x3FFFFFFFF:UInt64)).toNat=x.toNat%2^34:=by rw[э] exact В _ 34 have d:((896:UInt64)<<<(23:UInt64))=7516192768:=by decide rw[d,UInt64.toNat_sub_of_le] . rw[a];rfl . rw[UInt64.le_iff_toNat_le,a];norm_num;omega have e:(x.toNat/2^34)*2^31 ||| (x.toNat%2^34-896*2^23)=(x.toNat/2^34)*2^31+(x.toNat%2^34-896*2^23):=by rw[о (x.toNat/2^34)] exact (щ א _).symm apply И.mp rw[UInt64.toNat_toUInt32,UInt64.toNat_or,b,c,e,е] by_cases h:2^34<=x.toNat . simp only[h,decide_true,ite_true];omega . simp only[h,decide_false,Bool.false_eq_true,ite_false];omega lemma CG (s e:Float) (h:Fb s e≠0xFFFFFFFF): ∃(S:Bool) (ex fr:Nat),897<=ex∧ex<1151∧fr<2^23∧Fb s e=UInt32.ofNat ((if S then 2^31 else 0)+(ex-896)*2^23+fr)∧Fp (s+e).toBits.toNat S ex fr∧Fp (s-e).toBits.toNat S ex fr:=by unfold Fb at h⊢ dsimp only at h⊢ generalize (s+e).toBits=A at h⊢ generalize (s-e).toBits=B at h⊢ have b:=CC A have c:=CC B generalize (A+(0x0FFFFFFF:UInt64))>>>(29:UInt64)=x at h b⊢ generalize (B+(0x0FFFFFFF:UInt64))>>>(29:UInt64)=y at h c⊢ have d:=CD x generalize (x>>>(23:UInt64))&&&(0x7FF:UInt64)=ex at h d⊢ split at h . rename_i j;have k:=j;obtain ⟨a,j⟩:=у.mp j;have a:x=y:=by simpa using a obtain ⟨f,g⟩:=CE ex (by simpa using j);rw[d] at f g;subst a;have l:=A.toNat_lt;have m:=B.toNat_lt;have i:x.toNat<2^35:=א;simp only[k,ite_true];exact ⟨_,_,_,f,g,by omega,CF x i f g,CB A.toNat x.toNat l b f g,CB B.toNat x.toNat m c f g⟩ . exact absurd rfl h set_option maxRecDepth 8192 in lemma CH (f:Float) (S:Bool) (ex fr:Nat) (y:897<=ex) (z:ex<1151) (n:fr<2^23) (o:Fp f.toBits.toNat S ex fr): f.isFinite=true∧∃v:ℝ,R f=(if S then -v else v)∧v<=(2^53+fr*2^30+2^29)*2^((ex:Int)-1076)∧(fr≠0->(2^53+fr*2^30-2^29)*2^((ex:Int)-1076)simp;ring rcases q with rfl | ⟨rfl,rfl⟩ . have e:(2:ℝ)^((E:Int)-1075)=2*2^((E:Int)-1076):=by rw[show (E:Int)-1075=1+((E:Int)-1076) by ring,М С,zpow_one] rw[e];generalize (2:ℝ)^((E:Int)-1076)=b at a⊢;have i:(F:ℝ)<=fr*2^29+2^28:=by exact_mod_cast (by omega:F<=fr*2^29+2^28) have j:fr*2^29simp[abs_of_pos d] rwa [this] lemma CJ (w:UInt32) (h:expOf w≠255):wv w=(rationalWord w:ℝ):=by rw[wv,Model.toReal_eq,ofW,toDyadic_ofUInt32 w h];simp only[rationalWord,FloatLib.Numerics.Dyadic.cast_toRat] lemma CK (w:UInt32) (h:FY w=true):expOf w≠255:=by intro b;have c:w.toNat/2^23%2^8=255:=by have:=congrArg UInt32.toNat b;rw[expOf,О,л,show (255:UInt32).toNat=2^8-1 from rfl,В] at this;simpa [Nat.shiftRight_eq_div_pow] using this have a:(w&&&0x7FFFFFFF).toNat=w.toNat%2^31:=by rw[О,show (0x7FFFFFFF:UInt32).toNat=2^31-1 from rfl,В] simp only[FY,Bool.or_eq_true,beq_iff_eq,decide_eq_true_eq] at h;rcases h with h | h;. have:=congrArg UInt32.toNat h;rw[a] at this;have d:(0:UInt32).toNat=0:=rfl;omega . rw[Ж,UInt32.toNat_sub,a] at h;norm_num at h;omega lemma CL (a b:UInt32): ((sv a:ℚ)*sv b*(2:ℚ)^(idxOf a+idxOf b))*2^(-298:Int)=rationalWord a*rationalWord b:=by simp only[rationalWord,decodeD_toRat] rw[show (-298:Int)=-149+-149 by norm_num,М С] rw[zpow_sub₀ С,zpow_sub₀ С,Ц,Ц,pow_add] norm_num [zpow_neg,zpow_natCast] ring lemma CM (a b:Array UInt32) (start n:Nat): (dsum a b start n:ℚ)*2^(-298:Int)=∑j∈Finset.range n,rationalWord a[start+j]! *rationalWord b[start+j]!:=by induction n generalizing start with | zero=>simp[dsum] | succ n ih=> rw[dsum,Int.cast_add,Int.cast_mul,Int.cast_mul,Int.cast_pow,Int.cast_ofNat,add_mul,ih] conv_rhs=>rw[Finset.sum_range_succ'] simp only[Nat.add_zero] rw[CL] have c:(∑j∈Finset.range n,rationalWord a[start+1+j]! *rationalWord b[start+1+j]!)= ∑j∈Finset.range n,rationalWord a[start+(j+1)]! *rationalWord b[start+(j+1)]!:=by apply ы rfl intro j _ simp[Nat.add_comm,Nat.add_left_comm] rw[c] ring lemma CN (a b:Array UInt32) (o:a.size=b.size) (l:∀j,jexpOf a[j]!≠255∧expOf b[j]!≠255) (p:(dsum a b 0 a.size:ℚ)*2^(-298:Int)≠0): ∃d:FloatLib.Numerics.Dyadic,d.toRat=(dsum a b 0 a.size:ℚ)*2^(-298:Int)∧dotSpec a b=toWord (Model.roundDyadic Fmt d):=by let L:=a.map (Model.ofUInt32 (fmt:=Fmt)) let K:=b.map (Model.ofUInt32 (fmt:=Fmt)) have c:L.size=K.size:=by simp[L,K,o] have h:∀j (g:jUInt32) (g:∀j,jexpOf (fa j)≠255∧expOf (fb j)≠255) (h:(∑j∈Finset.range n,rationalWord (fa j)*rationalWord (fb j))≠0): ∃d:FloatLib.Numerics.Dyadic, d.toRat=(∑j∈Finset.range n,rationalWord (fa j)*rationalWord (fb j))∧dotOf n fa fb=toWord (Model.roundDyadic Fmt d):=by have b:(dsum (Array.ofFn (n:=n) λi=>fa i) (Array.ofFn (n:=n) λi=>fb i) 0 n:ℚ)*2^(-298:Int)=∑j∈Finset.range n,rationalWord (fa j)*rationalWord (fb j):=by rw[CM] apply ы rfl intro j c have a:=Finset.mem_range.mp c rw[К,AI n fa j a,AI n fb j a] have e:(Array.ofFn (n:=n) λi=>fa i).size=n:=by simp obtain ⟨d,f,k⟩:=CN (Array.ofFn (n:=n) λi=>fa i) (Array.ofFn (n:=n) λi=>fb i) ג (by intro j c have a:jUInt32) (bw:UInt32) (b:∀t,tFY (xw t)=true) (c:∀t,tFY (ww t)=true) (d:FY bw=true): ((∑j∈Finset.range (n+1),rationalWord (if jUInt32) (bw:UInt32) (H:∀t,tFY (xw t)=true) (I:∀t,tFY (ww t)=true) (J:FY bw=true) (s e:Float) (b:R (s-e)if tif t(2^53+fr*2^30-2^29)*2^((ex:Int)-1076)(lob1 h).trans b,lob.trans b⟩ . simp only[ite_true] at g b⊢;exact ⟨-V,by simp,by linarith only [z,b],λh=>by linarith [loa1 h],by linarith only [loa,g]⟩ have Q:0if tif tcases S<;> simp only[Bool.false_eq_true,ite_false,ite_true,Int.ofNat_eq_natCast,Int.cast_neg,Int.cast_natCast] at k a . exact ⟨by linarith only [k,a],rfl⟩ . exfalso;linarith only [i,c,p,k,a] . exfalso;linarith only [i,c,p,k,a] . exact ⟨by linarith only [k,a],rfl⟩ obtain ⟨d,rfl⟩:=d have X:m≠0:=by rintro rfl simp at d linarith only [i,c,d] have l:=B4 neg m q (2^23+fr) ((ex:Int)-1046) X א א א א (by rw[d,A];push_cast;linarith only [B]) (by intro G have r:fr≠0:=by intro N;exact G א have:=C r rw[d,A];push_cast;linarith only [this]) (by intro _ rw[d,A];linarith only [c]) have e1:((ex:Int)-1046+150).toNat=ex-896:=א have e2:(2^23+fr)%2^23=fr:=א rw[O,E,l,e1,e2] end section open ExactRuntime FloatLib.Floats.Formats.BinaryInterchange FloatLib.Floats open FloatLib.Floats.ExecFloat.Binary lemma CS (n:Nat) (f:n<2^20) (xw ww:Nat->UInt32) (bw:UInt32) (g:∀t,tFY (xw t)=true) (i:∀t,tFY (ww t)=true) (j:FY bw=true) (l:List Nat) (k:l.Nodup) (b:∀t∈l,tt∉l->xw t&&&0x7FFFFFFF=0∨ww t&&&0x7FFFFFFF=0) (s e:Float) (o:let r:=l.foldl (λ(acc:F1) t=>let q:=dv (xw t)*dv (ww t) F1.mk (acc.s+q) (acc.t+q.abs)) ⟨0,0⟩;s=r.s+dv bw∧e=Fe n*(r.t+(dv bw).abs)) (h:Fb s e≠0xFFFFFFFF): Fb s e=dotOf (n+1) (λt=>if tif tUInt32) (bw a:UInt32) (i:∀t,tFY (xw t)=true) (j:∀t,tFY (ww t)=true) (k:FY bw=true) (m:FY a=true) (o:∀t,txw t&&&0x7FFFFFFF<=a) (p:a<=0x7FFFFFFF) (l:List Nat) (q:l.Nodup) (c:∀t∈l,tt∉l->xw t&&&0x7FFFFFFF=0∨ww t&&&0x7FFFFFFF=0) (s e:Float) (u:s=l.foldl (λ(acc:Float) t=>acc+dv (xw t)*dv (ww t)) 0+dv bw∧e=Fe n*(dv a*(l.foldl (λ(acc:Float) t=>acc+(dv (ww t)).abs) 0)+(dv bw).abs)) (h:Fb s e≠0xFFFFFFFF): Fb s e=dotOf (n+1) (λt=>if tif tsimp lemma CZ (a:Array UInt32) (i:USize) (v:UInt32) (q:Nat) (d:a.size<2^32) (f:i.toNatsimp[e,eq_comm] . have c:¬q<(a.uset i v (AV a i h)).size:=by simpa using b rw[б _ q c,б a q b,Д א] def Fq (N:Nat) (sp:Nat->Word) (S:Nat->Prop) (out:Array Word):Prop:= out.size=N∧∀q,qS q->out[q]! =sp q lemma Ca {N:Nat} {sp:Nat->Word} {S:Nat->Prop} {out:Array Word} (i:N<2^32) (h:Fq N sp S out) {u:USize} {p:Nat} {v:Word} (a:u.toNat=p) (j:pq=p∨S q) (FW out u v):=by obtain ⟨c,d⟩:=h;refine ⟨by rw[CY,c],λq f g=>?_⟩;rw[CZ _ _ _ _ א א,a];by_cases e:q=p;. rw[Л e,e,b] . rw[Д e];exact d q f (g.resolve_left e) lemma Cb {N:Nat} {sp:Nat->Word} {S S':Nat->Prop} {out:Array Word} (h:Fq N sp S out) (b:∀q,qS' q->S q):Fq N sp S' out:=⟨h.1,λq a c=>h.2 q a (b q a c)⟩ lemma Cc {N:Nat} {sp:Nat->Word} {S:Nat->Prop} {out:Array Word} (h:Fq N sp S out) (b:∀q,qS q):out=Array.ofFn (n:=N) λq=>sp q.val:=by obtain ⟨c,d⟩:=h;apply ъ;. simp[c] . intro q e f;have a:qa (И.mp h);omega rw[Ж,س _ _ d] at b;rw[п] at c;have e:(0x00800000:UInt32)<=v:=by rw[Ж];omega simp only[Bool.or_eq_true,decide_eq_true_eq];right;rw[Ж,س _ _ e];omega lemma Ce (c u lo:UInt32) (h:c<=if uomega lemma Cf (c v a:UInt32) (h:(if aomega lemma Cg (w:UInt32) (h:FY w=true):FY (w&&&0x7FFFFFFF)=true:=by have e:(w&&&0x7FFFFFFF)&&&0x7FFFFFFF=w&&&0x7FFFFFFF:=by rw[UInt32.and_assoc,UInt32.and_self] unfold FY at h⊢;simpa only [e] using h lemma Ch {h:UInt32} (a:h<0x7F800000):h<=0x7FFFFFFF:=by have a1:(0x7F800000:UInt32).toNat=0x7F800000:=rfl;have a2:(0x7FFFFFFF:UInt32).toNat=0x7FFFFFFF:=rfl;rw[п] at a;rw[Ж];omega def Fr (A:Array Word) (h:Word):Prop:= FY h=true∧h<=0x7FFFFFFF∧(∀k,kFY A[k]! =true)∧ ∀k,kA[k]! &&&0x7FFFFFFF<=h lemma Ci (r v a:UInt32) (h:(if aomega lemma Cj (A:Array UInt32) (n:USize) (b:n.toNat<=A.size) (d:Nat): ∀(i:USize) (lo a:UInt32),i.toNat+d=n.toNat->FZ A n i b lo a≠0xFFFFFFFF→ (0x7FFFFF:UInt32)<=lo∧a<0x7F800000∧a<=FZ A n i b lo a∧FZ A n i b lo a<0x7F800000∧(FY a=true->FY (FZ A n i b lo a)=true)∧ ∀k,i.toNat<=k->k intro i lo a s h have e:FZ A n i b lo a=if 0x007FFFFF<=lo∧a<0x7F800000 then a else 0xFFFFFFFF:=by rw[FZ,Х (by rw[А];omega)] rw[e] at h⊢ by_cases c:0x007FFFFF<=lo∧a<0x7F800000 . rw[Л c];exact ⟨c.1,c.2,UInt32.le_refl _,c.2,id,λk p q=>by omega⟩ . rw[Д c] at h;exact absurd rfl h | succ d ih=> intro i lo a s h have f:iv ?_,λk B o=>?_⟩ . split;. exact Cg _ r . exact g0 . by_cases e2:k=i.toNat;. subst e2;rw[Е A i.toNat g];exact ⟨r,l⟩ . exact w k (by rw[AS i n f];omega) o lemma Ck (A:Array UInt32) (c:A.size<2^32) (h:FZ A A.usize 0 (AZ A) 0xFFFFFFFF 0≠0xFFFFFFFF):Fr A (FZ A A.usize 0 (AZ A) 0xFFFFFFFF 0):=by have e:=CW A c;have d:(0:USize).toNat=0:=rfl;obtain ⟨-,-,-,f,g,i⟩:=Cj A A.usize (AZ A) A.size 0 _ _ (by rw[d,e];omega) h;have b:∀k,kFY A[k]! =true∧A[k]! &&&0x7FFFFFFF<=FZ A A.usize 0 (AZ A) 0xFFFFFFFF 0:=λk a=>i k א א;exact ⟨g rfl,Ch f,λk a=>(b k a).1,λk a=>(b k a).2⟩ lemma Cl (w:UInt32):w&&&0x7FFFFFFF<=0x7FFFFFFF:=by rw[Ж,О];exact Nat.and_le_right def Fs (w:Nat->Word) (t:Nat) (h:Word):Prop:= FY h=true∧(∀k,kw k&&&0x7FFFFFFF<=h)∧h<=0x7FFFFFFF lemma Cm {w:Nat->Word} {t:Nat} {h:Word} (b:FY (w t)=true) (H:Fs w t h):Fs w (t+1) (mx h (w t)):=by obtain ⟨c,a,d⟩:=H;have f:=Cg _ b;unfold mx;dsimp only;by_cases e:w t&&&0x7FFFFFFF<=h . rw[Л e];refine ⟨c,λk g=>?_,d⟩;by_cases e2:k=t;. rw[e2];exact e . exact a k א . rw[Д e];refine ⟨f,λk g=>?_,Cl _⟩;by_cases e2:k=t;. rw[e2];exact UInt32.le_refl _ . have i:=a k א;simp only[UInt32.le_iff_toNat_le] at*;omega lemma Cn {w:Nat->Word} {t:Nat} {h:Word} (a:w t&&&0x7FFFFFFF=0) (H:Fs w t h):Fs w (t+1) h:=by obtain ⟨b,c,d⟩:=H;refine ⟨b,λk e=>?_,d⟩;by_cases e2:k=t;. rw[e2,a,Ж];exact Nat.zero_le _ . exact c k א lemma Co {rows inW i t:Nat} (a:isimp[e,eq_comm] . have d:¬q<(ds.set i.toNat v b).size:=by simpa using c rw[б _ q d,б ds q c,Д א] def Ft (xw:Nat->Word) (t:Nat):List Nat:= (List.range t).filter (λp=>xw p&&&0x7FFFFFFF !=0) lemma Cu (xw:Nat->Word) (t:Nat):(Ft xw t).length<=t:=by have h:=List.length_filter_le (λp=>xw p&&&0x7FFFFFFF !=0) (List.range t);simpa [Ft] using h lemma Cv (xw:Nat->Word) (t:Nat) (h:xw t&&&0x7FFFFFFF=0):Ft xw (t+1)=Ft xw t:=by simp[Ft,List.range_succ,List.filter_append,h] lemma Cw (xw:Nat->Word) (t:Nat) (h:¬xw t&&&0x7FFFFFFF=0):Ft xw (t+1)=Ft xw t++[t]:=by simp[Ft,List.range_succ,List.filter_append,h] def Fu (xw:Nat->Word) (sz t:Nat) (ix:Array UInt32) (buf:FloatArray) (c:USize) (hh:Word):Prop:= c.toNat=(Ft xw t).length∧ix.size=sz∧buf.size=sz∧ (∀k p:Nat,(Ft xw t)[k]?=some p→ (ix[k]! :UInt32).toNat=p∧buf.data[k]! =dv (xw p))∧Fs xw t hh lemma Cx {X:Array UInt32} {o n:USize} (xw:Nat->Word) (y:n.toNat<2^32) (g:∀t:USize,tFU X (o+t)=xw t.toNat) (u:∀t,tFY (xw t)=true) (d:Nat): ∀(t:USize) (ix:Array UInt32) (buf:FloatArray) (c:USize) (b:Word),t.toNat+d=n.toNat->Fu xw n.toNat t.toNat ix buf c b→ Fu xw n.toNat n.toNat (Fc X o n t ix buf c b).ix (Fc X o n t ix buf c b).buf (Fc X o n t ix buf c b).c (Fc X o n t ix buf c b).hi:=by induction d with | zero=> intro t ix buf c b v H rw[Fc,Х (by rw[А];omega)] have e:t.toNat=n.toNat:=א rw[e] at H;exact H | succ d ih=> intro t ix buf c b v H have h:t?_,Cm (u _ א) s⟩;. rw[AT _ _ (by rw[Щ];omega),Щ,i];simp . rw[CZ _ _ _ _ א א,Ct _ _ _ _ א א];rw[List.getElem?_append,<-i] at a;by_cases e:k=c.toNat;. subst e;simp at a;subst a;simp;omega . rw[Д e,Д e];by_cases e2:kintro k a c;rw[Fa,Х (by rw[А];omega)];rfl | succ d ih=> intro k a c;have b:kWord} {p:Nat} {out:Array Word} (a:N<2^32) (h:Fq N sp (λq=>qq(by omega:q=p∨qif tif tmax m v.toNat) 0:=by have key:∀(l:List UInt32) (i:Nat),i<=l.foldl (λm v=>max m v.toNat) i∧ ∀v∈l,v.toNat<=l.foldl (λm v=>max m v.toNat) i:=by intro l;induction l with | nil=>intro i;simp | cons x l ih=>intro i;obtain ⟨c,b⟩:=ih (max i x.toNat);simp only[List.foldl_cons,List.mem_cons,forall_eq_or_imp];exact ⟨by omega,by omega,b⟩ rw[<-Array.foldl_toList];exact (key a.toList 0).2 _ ג lemma C5 {n m:Nat} (d:Nat) (off:Array UInt32) (f:n<2^32) (a:∀j (h:jmax m v.toNat) 0 if h:r.c.toNat<=t.off.size∧r.c.toNat<=r.buf.size then let c:D_P:=⟨g,r.buf,t.off,r.c,(g.xd.size-(m+0)).toUSize, (g.xd.size-(m+3)).toUSize,dv g.hi*t.a,dv (FU g.b o.toUSize),0,h.1,h.2,hs, C5 0 t.off hs (C4 t.off),C5 3 t.off hs (C4 t.off),rfl⟩ GD g hs (o+1) (q+(g.ho*g.wo).toUSize) r.ix t.off r.buf (GB c (g.xd.size-(m+7)).toUSize (C5 7 t.off hs (C4 t.off)) o 0 q out) else out else out termination_by g.C-o def GE (s:ConvShape) (X:Array Word) (hs:X.size<2^32):FloatArray:= if s.pad==0 then Fx X 0 X.usize 0 hs (by simpa only[USize.toNat_zero,Nat.zero_add] using AZ X) (FloatArray.emptyWithCapacity X.size) else Fy s X hs (dv 0) (s.cin*(s.h+2*s.pad)) 0 (FloatArray.emptyWithCapacity (s.cin*(s.h+2*s.pad)*(s.w+2*s.pad))) def GF (dw:Bool) (s:ConvShape) (relu:Bool) (X W b:Array UInt32) (k C:Nat): Array UInt32:= let hp:=s.h+2*s.pad let wp:=s.w+2*s.pad let rx:=Fv X X.usize 0 (AZ X) 0xFFFFFFFF 0 if hg:X.size<2^32∧0x007FFFFF<=rx.lo∧rx.hi<0x7F800000∧X.size=s.cin*s.h*s.w∧ W.size=C*k∧b.size=C∧0>>(23:UInt32))-((rx.lo+1)>>>(23:UInt32))>20 let R:=s.cin*hp let xd:=GE s X hg.1 if hs:xd.size<2^32 then let g:D_C:=⟨dw,relu,s.stride==1,s,X,W,b,k,C,s.ho,s.wo,wp, s.stride.toUSize,rx.hi,xd,(k.toUInt64+8).toFloat*Float.ofBits 0x3CC0000000000000, Array.ofFn (n:=k) λt=>(Fz s t.val).toUInt32⟩ GD g hs 0 0 (Array.replicate k 0) (Array.replicate k 0) (Fa k.toUSize 0 (FloatArray.emptyWithCapacity k)) (Array.replicate (C*(s.ho*s.wo)) 0) else if dw then depthwiseWith FP s relu X W b else conv2dWith FP s relu X W b else if dw then depthwiseWith FP s relu X W b else conv2dWith FP s relu X W b def GG (s:ConvShape) (relu:Bool) (X W b:Array UInt32):Array UInt32:= GF false s relu X W b (s.cin*s.kh*s.kw) s.cout def GH (s:ConvShape) (relu:Bool) (X W b:Array UInt32):Array UInt32:= GF true s relu X W b (s.kh*s.kw) s.cin def GI (s:ConvShape) (X:Array Word) (c yy xx:Nat):Word:= if yyFloat) (m:Nat) (a:FloatArray):Prop:= a.size=m∧∀q,q< m->a.data[q]! =F q lemma C6 {F:Nat->Float} {m:Nat} {a:FloatArray} {v:Float} (h:GK F m a) (b:v=F m):GK F (m+1) (a.push v):=by refine ⟨by rw[Cy,h.1],λq c=>?_⟩;rw[C1,h.1];by_cases e:q=m;. rw[Л e,e,b] . rw[Д e];exact h.2 q א lemma C7 {F:Nat->Float} {v:Float} {n:USize} (d:Nat): ∀(k:USize) (m:Nat) (a:FloatArray),k.toNat+d=n.toNat->GK F m a→(∀i,m<=i->i< m+d->F i=v)->GK F (m+d) (Fw v n k a):=by induction d with | zero=> intro k m a e H _ rw[Fw,Х (by rw[А];omega)];exact H | succ d ih=> intro k m a e H b have c:kb i א א) lemma C8 {F:Nat->Float} {X:Array UInt32} {o n:USize} (e:X.size<2^32) (f:o.toNat+n.toNat<=X.size) (d:Nat): ∀(t:USize) (m:Nat) (a:FloatArray),t.toNat+d=n.toNat->GK F m a→(∀j,jF (m+j)=dv X[o.toNat+t.toNat+j]!)→GK F (m+d) (Fx X o n t e f a):=by induction d with | zero=> intro t m a g H _ rw[Fx,Х (by rw[А];omega)];exact H | succ d ih=> intro t m a g H c have b:t?_) . rw[Cr,AT _ _ א,e1] . have:=c (j+1) א;rw[AS t n b,show m+1+j=m+(j+1) by omega,show o.toNat+(t.toNat+1)+j=o.toNat+t.toNat+(j+1) by omega];exact this lemma C9 {c:Nat} (a:Nat) {b:Nat} (h:b intro r a A H rw[Fy,Х א] rw[(א:R=r)];exact H | succ d ih=> intro r a A H have f:rby rw[q,e] at f;simp at f) have j:r/(s.h+2*s.pad)GJ s X (r*(s.w+2*s.pad)+i)=dv (GI s X (r/(s.h+2*s.pad)) (r%(s.h+2*s.pad)) i):=λi l=>DA s X r l have g:∀i,i(r%(s.h+2*s.pad)(r/(s.h+2*s.pad)*s.h+(r%(s.h+2*s.pad)-s.pad))*s.w+s.w<=X.size:=λg1=>by rw[y];exact Cp (Co j g1) (le_refl _) have c:(r+1)*(s.w+2*s.pad)=r*(s.w+2*s.pad)+s.pad+s.w+s.pad:=by rw[ф,ц];omega rw[Fy,Р f] dsimp only split . rename_i o;obtain ⟨g1,g2,g3⟩:=o;have b:=t g2;apply ih (r+1) _ א;rw[c];generalize G:r*(s.w+2*s.pad)=m at H k g have P1:=C7 (F:=GJ s X) (v:=dv 0) (n:=s.pad.toUSize) s.pad 0 m a (by rw[e0,ep,К]) H (λi b x=>by obtain ⟨u,rfl⟩:=ь b exact g u א (Or.inr (Or.inl א))) have P2:=C8 (F:=GJ s X) p g3 s.w 0 _ _ (by rw[e0,ew,К]) P1 (λj I=>by rw[з m,k _ א,GI,Д א,e0,Я,CU _ א,Nat.add_sub_cancel_left]) exact C7 (F:=GJ s X) (v:=dv 0) (n:=s.pad.toUSize) s.pad 0 _ _ (by rw[e0,ep,К]) P2 (λi b x=>by obtain ⟨u,rfl⟩:=ь b;rw[з m,з m] exact g _ א (Or.inr (Or.inr (Or.inr א)))) . rename_i o;apply ih (r+1) _ א;have C:r%(s.h+2*s.pad)by obtain ⟨u,rfl⟩:=ь b exact g u א א) lemma DC (s:ConvShape) (X:Array Word) (c:s.pad=0) (q:Nat) (b:qby rw[Nat.zero_mul] at f;omega⟩ def GM (g:D_C) (o:Nat):Nat:=if g.dw then o*g.k else 0 def GN (g:D_C) (o y x t:Nat):Word:=windowAt g.s g.X y x (GM g o+t) def GO (g:D_C) (o y x:Nat):Word:= act g.relu (dotOf (g.k+1) (λt=>if tif tg.s.stride=1 p0:0(Fz g.s t.val).toUInt32 lemma DG {A:Array Word} {h:Word}:FY (0:Word)=true∧(0:Word)&&&0x7FFFFFFF<=h:=by refine ⟨rfl,?_⟩;rw[Ж];exact Nat.le_trans (Nat.le_of_eq rfl) (Nat.zero_le _) lemma DH {A:Array Word} (H:∀k:Nat,kFY A[k]! =true) (q:Nat):FY A[q]! =true:=by by_cases h:qby rw[e] at d;simp at d) have f:0Float) (L:List Nat):∀(i:USize) (a t:Float),i.toNat+L.length=e.toNat→ (∀j p:Nat,L[j]?=some p->xd.data[b.toNat+(off[i.toNat+j]! :UInt32).toNat]! =xf p∧wd.data[i.toNat+j]! =wf p)→ F2 xd wd off b e i o r u k a t=L.foldl (λ(acc:F1) p=>let q:=xf p*wf p F1.mk (acc.s+q) (acc.t+q.abs)) ⟨a,t⟩:=by induction L with | nil=> intro i a t d _ rw[F2,Х (by rw[А];simp at d;omega)] rfl | cons p L ih=> intro i a t d H simp only[List.length_cons] at d have f:iacc+xf 0 p*wf p) a0, L.foldl (λacc p=>acc+xf 1 p*wf p) a1, L.foldl (λacc p=>acc+xf 2 p*wf p) a2, L.foldl (λacc p=>acc+xf 3 p*wf p) a3⟩:=by induction L with | nil=> intro i a0 a1 a2 a3 c _ rw[F0,Х (by rw[А];simp at c;omega)] rfl | cons p L ih=> intro i a0 a1 a2 a3 c H simp only[List.length_cons] at c have f:i?_ have:=H (j+1) q (by simpa using u) rw[AS i e f,show i.toNat+1+j=i.toNat+(j+1) by omega] exact this lemma DP {xd wd:FloatArray} {off:Array UInt32} {b e:USize} (n:e.toNat<=off.size) (o:e.toNat<=wd.size) (r:xd.size<2^32) (l:∀j (h:jacc+xf 0 p*wf p) a0, L.foldl (λacc p=>acc+xf 1 p*wf p) a1, L.foldl (λacc p=>acc+xf 2 p*wf p) a2, L.foldl (λacc p=>acc+xf 3 p*wf p) a3, L.foldl (λacc p=>acc+xf 4 p*wf p) a4, L.foldl (λacc p=>acc+xf 5 p*wf p) a5, L.foldl (λacc p=>acc+xf 6 p*wf p) a6, L.foldl (λacc p=>acc+xf 7 p*wf p) a7⟩:=by induction L with | nil=> intro i a0 a1 a2 a3 a4 a5 a6 a7 c _ rw[F9,Х (by rw[А];simp at c;omega)] rfl | cons p L ih=> intro i a0 a1 a2 a3 a4 a5 a6 a7 c H simp only[List.length_cons] at c have f:i?_ have:=H (j+1) q (by simpa using u) rw[AS i e f,show i.toNat+1+j=i.toNat+(j+1) by omega] exact this structure D_PO (c:D_P) (o:Nat) (L:List Nat):Prop where ok:D_Ok c.g hC:ot∉L->c.g.W[o*c.g.k+t]! &&&0x7FFFFFFF=0 rd:∀j p:Nat,L[j]?=some p→ (c.off[j]! :UInt32).toNat=Fz c.g.s (GM c.g o+p)∧ c.wd.data[j]! =dv c.g.W[o*c.g.k+p]! e0:c.e0=dv c.g.hi*L.foldl (λacc t=>acc+(dv c.g.W[o*c.g.k+t]!).abs) 0 bv:c.bv=dv c.g.b[o]! lemma DQ {c:D_P} {o:Nat} {L:List Nat} (h:D_PO c o L) {j p:Nat} (a:L[j]?=some p):pdv (GN c.g o y x p)) (λp=>dv c.g.W[o*c.g.k+p]!) L 0 0 0 (by rw[show (0:USize).toNat=0 from rfl,К];exact h.len.symm) (λj p d=>by have f:=h.rd j p d;rw[show (0:USize).toNat=0 from rfl,К,f.1,m] exact ⟨(DL h.ok h.hC i l (DQ h d)).2,f.2⟩) dsimp only;rw[c.hz,e,h.bv,h.ok.nf] by_cases a:Fb ((L.foldl (λ(acc:F1) p=>let q:=dv (GN c.g o y x p)*dv c.g.W[o*c.g.k+p]! F1.mk (acc.s+q) (acc.t+q.abs)) ⟨0,0⟩).s+dv c.g.b[o]!) (Fe c.g.k*((L.foldl (λ(acc:F1) p=> let q:=dv (GN c.g o y x p)*dv c.g.W[o*c.g.k+p]! F1.mk (acc.s+q) (acc.t+q.abs)) ⟨0,0⟩).t+(dv c.g.b[o]!).abs))=0xFFFFFFFF . rw[Л (by simpa using a)];exact DF _ _ _ _ . rw[Д (by simpa using a)];unfold GO;congr 1;exact CS c.g.k h.ok.nk (GN c.g o y x) (λt=>c.g.W[o*c.g.k+t]!) c.g.b[o]! (λt _=>(DI h.ok.Hx _ _ _).1) (λt _=>h.ok.HW _) (h.ok.Hb _) L h.nd h.lt (λt r u=>Or.inr (h.hz t r u)) _ _ ⟨rfl,rfl⟩ a . exact DF _ _ _ _ lemma DS {c:D_P} {o:Nat} {L:List Nat} (h:D_PO c o L) {y x:Nat} {b:USize} (e:yacc+dv (GN c.g o y x t)*dv c.g.W[o*c.g.k+t]!) 0):F5 c o y x b a=GO c.g o y x:=by unfold F5;dsimp only;rw[h.bv,h.ok.nf,h.e0];by_cases d:Fb (a+dv c.g.b[o]!) (Fe c.g.k*(dv c.g.hi*L.foldl (λacc t=>acc+(dv c.g.W[o*c.g.k+t]!).abs) 0+(dv c.g.b[o]!).abs))=0xFFFFFFFF;. rw[Л (by simpa using d)];exact DR h e f i . rw[Д (by simpa using d)];unfold GO;congr 1;exact CT c.g.k h.ok.nk (GN c.g o y x) (λt=>c.g.W[o*c.g.k+t]!) c.g.b[o]! c.g.hi (λt _=>(DI h.ok.Hx _ _ _).1) (λt _=>h.ok.HW _) (h.ok.Hb _) h.ok.Hx.1 (λt _=>(DI h.ok.Hx _ _ _).2) h.ok.Hx.2.1 L h.nd h.lt (λt l m=>Or.inr (h.hz t l m)) _ _ ⟨by rw[j],rfl⟩ d lemma DT {xd wd:FloatArray} {off:Array UInt32} {b e:USize} (o:e.toNat<=off.size) (r:e.toNat<=wd.size) (s:xd.size<2^32) (k:∀j (h:jFloat) (L:List Nat):∀(i:USize) (a:Float),i.toNat+L.length=e.toNat→ (∀j p:Nat,L[j]?=some p->xd.data[b.toNat+(off[i.toNat+j]! :UInt32).toNat]! =xf p∧wd.data[i.toNat+j]! =wf p)→ F6 xd wd off b e i o r s k a=L.foldl (λacc p=>acc+xf p*wf p) a:=by induction L with | nil=> intro i a d _ rw[F6,Х (by rw[А];simp at d;omega)] rfl | cons p L ih=> intro i a d H simp only[List.length_cons] at d have f:idv (GN c.g o y x p)) (fun p=>dv c.g.W[o*c.g.k+p]!) L 0 c.ze (by rw[show (0:USize).toNat=0 from rfl,К];exact h.len.symm) (fun j p i=>by have l:=h.rd j p i rw[show (0:USize).toNat=0 from rfl,К,l.1,f] exact ⟨(DL h.ok h.hC a d (DQ h i)).2,l.2⟩) rw[e,c.hz] exact DS h a d f rfl ·exact DF _ _ _ _ def GQ (g:D_C) (q:Nat):Word:= GO g (q/(g.ho*g.wo)) (q/g.wo%g.ho) (q%g.wo) lemma DV (g:D_C) {o y x:Nat} (a:yb.toNat=GP c.g y x)->q.toNat=Q+x->rr.size=4→Fq (c.g.C*(c.g.ho*c.g.wo)) (GQ c.g) (λp=>pp intro x b q rr out M D i w H have sN:=h.ok.sN have l:∀x',x'GO c.g o y x'=GQ c.g (Q+x'):=by intro x' E;rw[I];exact DV c.g m E have l2:(2:USize).toNat=2:=uk 2 ב have l3:(3:USize).toNat=3:=uk 3 ב have l4:(4:USize).toNat=4:=uk 4 ב by_cases u:x+4<=c.g.wo∧c.g.f4=true∧bDW h.ok h.hC m F;have b0:=bB 3 א;rw[n] at b0;have a1:(b+1).toNat=GP c.g y (x+1):=by rw[n,AT _ _ (by rw[Щ];omega),f,Щ] have a2:(b+2).toNat=GP c.g y (x+2):=by rw[n,AT _ _ (by rw[l2];omega),f,l2] have a3:(b+3).toNat=GP c.g y (x+3):=by rw[n,AT _ _ (by rw[l3];omega),f,l3] have R:=DO c.he c.hw c.hs (c.h4 b u.2.2) (λk p=>dv (GN c.g o y (x+k) p)) (λp=>dv c.g.W[o*c.g.k+p]!) L 0 0 0 0 0 (by rw[show (0:USize).toNat=0 from rfl,К];exact h.len.symm) (λj p z=>by have r:=h.rd j p z;rw[show (0:USize).toNat=0 from rfl,К,r.1];refine ⟨r.2,λk F=>?_⟩;rw[show b.toNat+Fz c.g.s (GM c.g o+p)+k=GP c.g y (x+k)+Fz c.g.s (GM c.g o+p) by rw[n,f];omega] exact (DL h.ok h.hC m א (DQ h z)).2) have o0:F5 c o y x b (L.foldl (λacc p=>acc+dv (GN c.g o y (x+0) p)*dv c.g.W[o*c.g.k+p]!) 0)=GO c.g o y x:=DS h m א f rfl have o1:=DS h m (א:x+1acc+dv (GN c.g o y (x+1) p)*dv c.g.W[o*c.g.k+p]!) 0)) rfl have o2:=DS h m (א:x+2acc+dv (GN c.g o y (x+2) p)*dv c.g.W[o*c.g.k+p]!) 0)) rfl have o3:=DS h m (א:x+3acc+dv (GN c.g o y (x+3) p)*dv c.g.W[o*c.g.k+p]!) 0)) rfl rw[F8,Р u];dsimp only;rw[c.hz,R];dsimp only;rw[o0,o1,o2,o3];refine ih (d-4) א (x+4) _ _ _ _ א ?_ ?_ w ?_;. intro A;have t:=DW h.ok h.hC m A;rw[n] at t⊢;rw[AT _ _ (by rw[l4];omega),f,l4] . rw[AT _ _ (by rw[l4,i];omega),i,l4];omega . have q1:(q+1).toNat=Q+x+1:=by rw[AT _ _ (by rw[Щ,i];omega),i,Щ] have q2:(q+2).toNat=Q+x+1+1:=by rw[AT _ _ (by rw[l2,i];omega),i,l2] have q3:(q+3).toNat=Q+x+1+1+1:=by rw[AT _ _ (by rw[l3,i];omega),i,l3] have s1:GO c.g o y (x+1)=GQ c.g (Q+x+1):=by rw[з];exact l _ א have s2:GO c.g o y (x+2)=GQ c.g (Q+x+1+1):=by rw[show Q+x+1+1=Q+(x+2) by omega];exact l _ א have s3:GO c.g o y (x+3)=GQ c.g (Q+x+1+1+1):=by rw[show Q+x+1+1+1=Q+(x+3) by omega];exact l _ א rw[show Q+(x+4)=Q+x+1+1+1+1 by omega];exact C0 sN (C0 sN (C0 sN (C0 sN H i א (l _ א)) q1 א s1) q2 א s2) q3 א s3 . by_cases v:x+3<=c.g.wo∧c.g.f4=true∧bu ⟨A,v.2⟩ have G:x+3=c.g.wo:=by omega have st1:=h.ok.f4 v.2.1 have f:=D (by omega) have n:∀k,GP c.g y (x+k)=GP c.g y x+k:=by intro k;unfold GP;rw[st1];simp only[Nat.mul_one];omega have b0:=DW h.ok h.hC m (by omega:x+2if d<3 then dv (GN c.g o y (x+d) p) else c.g.xd.data[b.toNat+Fz c.g.s (GM c.g o+p)+d]!) (fun p=>dv c.g.W[o*c.g.k+p]!) L 0 0 0 0 0 (by rw[show (0:USize).toNat=0 from rfl,К];exact h.len.symm) (by intro j p z have r:=h.rd j p z rw[show (0:USize).toNat=0 from rfl,К,r.1] refine ⟨r.2,?_⟩ intro d N by_cases B:d<3 ·rw[if_pos B] rw[show b.toNat+Fz c.g.s (GM c.g o+p)+d=GP c.g y (x+d)+Fz c.g.s (GM c.g o+p) by rw[n,f];omega] exact (DL h.ok h.hC m (by omega) (DQ h z)).2 ·rw[if_neg B]) have o0:F5 c o y x b (L.foldl (fun acc p=>acc+dv (GN c.g o y (x+0) p)*dv c.g.W[o*c.g.k+p]!) 0)=GO c.g o y x:=DS h m (by omega) f rfl have o1:=DS h m (by omega:x+1acc+dv (GN c.g o y (x+1) p)*dv c.g.W[o*c.g.k+p]!) 0) rfl have o2:=DS h m (by omega:x+2acc+dv (GN c.g o y (x+2) p)*dv c.g.W[o*c.g.k+p]!) 0) rfl rw[F8,dif_neg u,dif_pos v] dsimp only rw[c.hz,R] dsimp only simp only[show (0:Nat)<3 by decide,show (1:Nat)<3 by decide,show (2:Nat)<3 by decide,ite_true] rw[o0,o1,o2] have q1:(q+1).toNat=Q+x+1:=by rw[AT _ _ (by rw[Щ,i];omega),i,Щ] have q2:(q+2).toNat=Q+x+1+1:=by rw[AT _ _ (by rw[l2,i];omega),i,l2] have s1:GO c.g o y (x+1)=GQ c.g (Q+x+1):=by rw[з];exact l _ (by omega) have s2:GO c.g o y (x+2)=GQ c.g (Q+x+1+1):=by rw[show Q+x+1+1=Q+(x+2) by omega];exact l _ (by omega) rw[show Q+c.g.wo=Q+x+1+1+1 by omega] exact C0 sN (C0 sN (C0 sN H i (by omega) (l _ (by omega))) q1 (by omega) s1) q2 (by omega) s2 . by_cases r:xpp intro x b q rr out D z f n H have sN:=h.ok.sN have i:∀x',x'dv (GN c.g o y (x+k) p)) (λp=>dv c.g.W[o*c.g.k+p]!) L 0 0 0 0 0 0 0 0 0 (by rw[show (0:USize).toNat=0 from rfl,К];exact h.len.symm) (λj p r=>by have A:=h.rd j p r rw[show (0:USize).toNat=0 from rfl,К,A.1] refine ⟨A.2,λk F=>?_⟩ rw[show b.toNat+Fz c.g.s (GM c.g o+p)+k= GP c.g y (x+k)+Fz c.g.s (GM c.g o+p) by rw[l,a];omega] exact (DL h.ok h.hC e (by omega) (DQ h r)).2) have eq0:F5 c o y x b (L.foldl (λacc p=>acc+dv (GN c.g o y x p)*dv c.g.W[o*c.g.k+p]!) 0)= GO c.g o y x:=by apply DS h e (by omega) (by simpa using a) rfl have l1:(1:USize).toNat=1:=uk 1 ב have eq1:F5 c o y (x+1) (b+1) (L.foldl (λacc p=>acc+dv (GN c.g o y (x+1) p)*dv c.g.W[o*c.g.k+p]!) 0)= GO c.g o y (x+1):=by apply DS h e (by omega) (by rw[l,AT _ _ (by rw[l1];have:=DW h.ok h.hC e (show x+1acc+dv (GN c.g o y (x+2) p)*dv c.g.W[o*c.g.k+p]!) 0)= GO c.g o y (x+2):=by apply DS h e (by omega) (by rw[l,AT _ _ (by rw[l2];have:=DW h.ok h.hC e (show x+2acc+dv (GN c.g o y (x+3) p)*dv c.g.W[o*c.g.k+p]!) 0)= GO c.g o y (x+3):=by apply DS h e (by omega) (by rw[l,AT _ _ (by rw[l3];have:=DW h.ok h.hC e (show x+3acc+dv (GN c.g o y (x+4) p)*dv c.g.W[o*c.g.k+p]!) 0)= GO c.g o y (x+4):=by apply DS h e (by omega) (by rw[l,AT _ _ (by rw[l4];have:=DW h.ok h.hC e (show x+4acc+dv (GN c.g o y (x+5) p)*dv c.g.W[o*c.g.k+p]!) 0)= GO c.g o y (x+5):=by apply DS h e (by omega) (by rw[l,AT _ _ (by rw[l5];have:=DW h.ok h.hC e (show x+5acc+dv (GN c.g o y (x+6) p)*dv c.g.W[o*c.g.k+p]!) 0)= GO c.g o y (x+6):=by apply DS h e (by omega) (by rw[l,AT _ _ (by rw[l6];have:=DW h.ok h.hC e (show x+6acc+dv (GN c.g o y (x+7) p)*dv c.g.W[o*c.g.k+p]!) 0)= GO c.g o y (x+7):=by apply DS h e (by omega) (by rw[l,AT _ _ (by rw[l7];have:=DW h.ok h.hC e (show x+7ppppppppp<(o*c.g.ho+y)*c.g.wo) out→ Fq (c.g.C*(c.g.ho*c.g.wo)) (GQ c.g) (λp=>p<(o*c.g.ho+c.g.ho)*c.g.wo) (GB c l8 n o y q out):=by induction d with | zero=> intro y q out t _ H rw[GB,Д א] rw[(א:y=c.g.ho)] at H;exact H | succ d ih=> intro y q out t i H have k:yby rw[e] at r;simp at r) exact к m have:=h.ok.kw omega have e1:GP c.g y 0=y*c.g.s.stride*c.g.wp:=by unfold GP;simp rw[e1] at bB have A:y*c.g.s.stride<=y*c.g.s.stride*c.g.wp:=й _ l have eS:(y.toUSize*c.g.step).toNat=y*c.g.s.stride:=by rw[CV _ _ (by rw[eY,h.ok.st];omega),eY,h.ok.st] have eP:c.g.wp.toUSize.toNat=c.g.wp:=CU _ h.ok.wp2 have ebase:(y.toUSize*c.g.step*c.g.wp.toUSize).toNat=GP c.g y 0:=by rw[CV _ _ (by rw[eS,eP];exact bB),eS,eP,e1] rw[GB,Л k] refine ih (y+1) _ _ א ?_ ?_ . rw[AT _ _ (by rw[eW,i];omega),i,eW,f] . rw[f];refine DY h k rfl א l8 n c.g.wo 0 _ _ _ _ (К _) (λ_=>ebase) (by rw[Я];exact i) ?_ (by rw[Я];exact H);rw[Cz 4 4 0 _ (by rw[show (0:USize).toNat=0 from rfl,К];exact (uk 4 ב).symm)];rfl lemma Da {g:D_C} {c:D_P} {o:Nat} {L:List Nat} (d:c.g=g) (h:D_PO c o L) (e:(o*g.ho+g.ho)*g.wo<=g.C*(g.ho*g.wo)) {l8:USize} {a:∀b:USize,bp<(o*g.ho+0)*g.wo) out): Fq (g.C*(g.ho*g.wo)) (GQ g) (λp=>p<(o*g.ho+g.ho)*g.wo) (GB c l8 a o 0 q out):=by subst d exact DZ h e l8 a c.g.ho 0 q out (К _) f H lemma Db (s:ConvShape) (o:Nat) {p:Nat} (c:pFloat) (n:∀p∈L,p(ix[j]! :UInt32).toNat=p∧buf.data[j]! =wf p) (d:Nat): ∀(i:USize) (off:Array UInt32) (a:Float),i.toNat+d=e.toNat→Fq N (GR g o L) (λq=>q< i.toNat) off→ Fq N (GR g o L) (λq=>qacc+(wf t).abs) a:=by induction d with | zero=> intro i off a w H rw[GC,Х (by rw[А];omega)] rw[(א:i.toNat=e.toNat)] at H⊢ exact ⟨H,by rw[List.drop_eq_nil_of_le א];rfl⟩ | succ d ih=> intro i off a w H have f:iq.toNat=o*(g.ho*g.wo)->ix.size=g.k->off.size=g.k->buf.size=g.k→Fq (g.C*(g.ho*g.wo)) (GQ g) (λp=>pp intro o q ix off buf out w _ _ _ _ H rw[GD,Д א] rw[(א:o=g.C)] at H;exact H | succ d ih=> intro o q ix off buf out w h z A B H have i:og.W[o*g.k+p]!) (by rw[ek];exact e) (λt f=>by have G:=А.mp f rw[ek] at G rw[CX _ _ sW2,AT _ _ (by rw[eo];omega),eo]) (λt _=>ok.HW _) g.k 0 ix buf 0 0 (by rw[show (0:USize).toNat=0 from rfl,ek,К]) ⟨by simp[Ft],by rw[ek];exact z,by rw[ek];exact B,λk p t=>by simp[Ft] at t,rfl,λk t=>absurd t (Nat.not_lt_zero _),(by decide)⟩ rw[ek] at D obtain ⟨d1,d2,d3,d4,-⟩:=D rw[GD,Л i] dsimp only have c:=Cu (λp=>g.W[o*g.k+p]!) g.k have T:=De ok o (N:=g.k) (L:=Ft (λp=>g.W[o*g.k+p]!) g.k) (λp=>dv g.W[o*g.k+p]!) (λt f=>н.mp (ش.mp f).1) e א א d1 א א d4 (Ft (λp=>g.W[o*g.k+p]!) g.k).length 0 off 0 (by rw[show (0:USize).toNat=0 from rfl,К];exact d1.symm) ⟨A,λq _ h=>absurd h (Nat.not_lt_zero _)⟩ obtain ⟨⟨T1,T3⟩,T2⟩:=T rw[Р (by rw[T1,d3,d1];exact ⟨c,c⟩)] refine ih (o+1) _ _ _ _ _ א ?_ d2 T1 d3 ?_ . rw[AT _ _ (by rw[eH,h];omega),h,eH,r] . have E:(o+1)*(g.ho*g.wo)=(o*g.ho+g.ho)*g.wo:=by ring rw[E] refine Da (L:=Ft (λp=>g.W[o*g.k+p]!) g.k) rfl ⟨ok,i,d1,(List.nodup_range).filter _,λt f=>н.mp (ش.mp f).1,λt f I=>?_,λj p m=>?_,?_,?_⟩ (by rw[<-E];exact F) (by rw[Я,h];ring) (by rw[show (o*g.ho+0)*g.wo=o*(g.ho*g.wo) by ring];exact H) . by_contra J;exact I (ش.mpr ⟨н.mpr f,by simpa using J⟩) . have K:j<(Ft (λp=>g.W[o*g.k+p]!) g.k).length:=(List.getElem?_eq_some_iff.mp m).1;have u:pdv g.hi*a) T2 . show dv (FU g.b o.toUSize)=_;rw[CX _ _ ok.sb,eOo] lemma Dg (A:Array UInt32) (n:USize) (b:n.toNat<=A.size) (d:Nat): ∀(i:USize) (lo a:UInt32),i.toNat+d=n.toNat->FZ A n i b lo a= if 0x007FFFFF<=(Fv A n i b lo a).lo∧(Fv A n i b lo a).hi<0x7F800000 then (Fv A n i b lo a).hi else 0xFFFFFFFF:=by induction d with | zero=> intro i lo a c have h:¬i intro i lo a c have h:i?_⟩) (λq h=>h)).trans ?_ . rw[Cz g.k.toUSize g.k 0 _ (by rw[e,show (0:USize).toNat=0 from rfl,К])];exact К _ . rw[Nat.zero_mul] at h;exact absurd h (Nat.not_lt_zero _) . obtain ⟨dw,relu,f4,s,X,W,b,k,C,c,wo,wp,step,l,xd,nf,tab⟩:=g;have d:k=if dw then s.kh*s.kw else s.cin*s.kh*s.kw:=ok.hk;have f:C=if dw then s.cin else s.cout:=ok.hC;have i:c=s.ho:=ok.ho;have j:wo=s.wo:=ok.wo;subst d f i j;cases dw;. refine congrArg (Array.ofFn (n:=s.cout*(s.ho*s.wo))) (funext λq=>?_);simp[GQ,GO,GN,GM] . refine congrArg (Array.ofFn (n:=s.cin*(s.ho*s.wo))) (funext λq=>?_);simp[GQ,GO,GN,GM] lemma Di (dw:Bool) (s:ConvShape) (relu:Bool) (X W b:Array UInt32) {k C:Nat} (c:k=if dw then s.kh*s.kw else s.cin*s.kh*s.kw) (d:C=if dw then s.cin else s.cout): GF dw s relu X W b k C=if dw then depthwiseSpec s relu X W b else conv2dSpec s relu X W b:=by have a:(if dw then depthwiseWith FP s relu X W b else conv2dWith FP s relu X W b)=if dw then depthwiseSpec s relu X W b else conv2dSpec s relu X W b:=by rw[AJ];rfl unfold GF dsimp only rw[<-a] generalize (if dw then depthwiseWith FP s relu X W b else conv2dWith FP s relu X W b)=R at a⊢ split . rename_i f;split . rename_i g;obtain ⟨g1,g2,g3,g4,g5,g6,g7,g8,g9,g10,g11,g12,g13,g14,g15,g16,g17,g18,g19,g20⟩:=f;have e:=Dg X X.usize (AZ X) (X.usize.toNat) 0 0xFFFFFFFF 0 (by rw[show (0:USize).toNat=0 from rfl,К]);rw[Л ⟨g2,g3⟩] at e;have Hx:=Ck X g1 (by rw[e];intro h;rw[h] at g3;exact absurd g3 (by decide));rw[e] at Hx;refine (Dh ?_ _).trans a.symm exact ⟨c,d,rfl,rfl,rfl,CU _ g8,rfl,λh=>beq_iff_eq.mp h,g7,g9,g10,g11,g12, DE s X g1 g4 g13 g14, g,Hx,DH (Ck W g15 g19).2.2.1,DH (Ck b g16 g20).2.2.1, g5,g15,g16,g17,g14,rfl⟩ . rfl . rfl lemma Dj:GG=conv2dSpec:=by funext s relu X W b;exact Di false s relu X W b rfl rfl lemma Dk:GH=depthwiseSpec:=by funext s relu X W b;exact Di true s relu X W b rfl rfl end section open ExactRuntime FloatLib.Floats.Formats.BinaryInterchange FloatLib.Floats open FloatLib.Floats.ExecFloat.Binary open Float.Model Float.Model.UnpackedFloat lemma Dl (s:Sign) (m:Nat) (e T:Int) (K r:Nat) (a:Format.binary32.targetExponent (totalExponent m e)=T) (b:T=e+(K+1:Nat)) (c:(ExtendedMantissa.ofMantissaAndAccuracy m .exact>>>(K+1)).roundedMantissa=r): UnpackedFloat.round Format.binary32 s m e=let p:=shiftToTargetExponent Format.binary32 r T .exact if h:p.1.mantissa=0 then .zero s else .finite s p.1.mantissa p.2 (Н h):=by unfold UnpackedFloat.round decreaseExponent roundWithAccuracy simp only[a] have d:(e-T).toNat=0:=א have f:shiftToTargetExponent Format.binary32 m e .exact=(ExtendedMantissa.ofMantissaAndAccuracy m .exact>>>(K+1),T):=by unfold shiftToTargetExponent shiftToExponent simp only[a] have g:(T-e).toNat=K+1:=א rw[g,b] simp only[d,Nat.shiftLeft_zero,Int.natCast_zero,Int.sub_zero,f,c] def GS (N:Nat):Nat:= N/2^39+if 2^38>>(38+1)).roundedMantissa=GS N:=by rw[Bq];have d:=Nat.div_add_mod N (2^39);have l:N%2^39<2^39:=Ъ _ ב;unfold GS;simp[ExtendedMantissa.roundedMantissa,ExtendedMantissa.accuracy,Accuracy.roundToNearestEven];generalize a:(N/274877906944%2==1)=b;generalize e:(!decide (N%274877906944=0))=c;cases b<;>cases c<;>simp at a e⊢<;>(try split_ifs)<;>omega lemma Dn (neg:Bool) (N:Nat) (e':Int) (b:2^62<=N) (c:N<2^63) (j:-148<=e'+39) (k:e'+39+150<=253): toWord (Model.ofModel Fmt (UnpackedFloat.round Format.binary32 (Model.modelSign neg) N e'))=UInt32.ofNat ((if neg then 2^31 else 0)+(e'+39+149).toNat*2^23+GS N):=by have a:2^23<=GS N:=by unfold GS;have:2^23<=N/2^39:=א split<;>omega have d:GS N<=2^24:=by unfold GS;have:N/2^39<2^24:=א split<;>omega have f:N.log2=62:=Bu N 62 b c have g:Format.binary32.targetExponent (totalExponent N e')=e'+39:=by simp only[totalExponent,f,Bt];omega rw[Dl _ N e' _ 38 _ g (by push_cast;ring) (Dm N)] by_cases h:GS N=2^24 . rw[h,show e'+39=e'+40-1 by ring,Bz _ (e'+40) א (by norm_num:0<2^23)];simp only[toWord,Model.toNatBits,Model.ofModel,Model.ofModelBits];congr 1;show (UnpackedFloat.pack Format.binary32 _).toNat=_;rw[B3 _ _ _ _ ב ב א א];have e:(e'+40+150).toNat=(e'+40-1+149).toNat+2:=א;rw[e];cases neg<;>simp[Model.modelSign]<;>omega . have i:0simp[Model.modelSign]<;>omega @[inline] def GT (neg:Bool) (mag e0 L:UInt64):UInt32:= let n:=mag<<<(62-L) let q:=n>>>39 let rm:=n&&&0x7FFFFFFFFF let w:=((e0+L-24)<<<23)+q+ (if rm>0x4000000000 || (rm==0x4000000000&&q&&&1==1) then 1 else 0) (if neg then w ||| 0x80000000 else w).toUInt32 lemma Do (neg:Bool) (mag e0:UInt64) (d:mag.toNat≠0) (l:mag.toNat<2^63) (m:24>>39).toNat=N/2^39:=by rw[м,a1];simp[Nat.shiftRight_eq_div_pow] have a3:(n&&&0x7FFFFFFFFF).toNat=N%2^39:=by rw[э,a1];exact В N 39 generalize n>>>39=q at a2;generalize n&&&0x7FFFFFFFFF=rm at a3;have a4:(q&&&1).toNat=q.toNat%2:=by rw[э];exact В _ 1 have a5:(e0+mag.log2-24).toNat=e0.toNat+L-24:=by rw[UInt64.toNat_sub_of_le _ _ (UInt64.le_iff_toNat_le.2 (by rw[Ы,eL,Г א];show 24<=_;omega)), Ы,eL,Г א] rfl have a6:((e0+mag.log2-24)<<<23).toNat=(e0.toNat+L-24)*2^23:=by rw[UInt64.toNat_shiftLeft,a5,т];show _*2^23%_=_;rw[Г א] generalize (e0+mag.log2-24)<<<23=g at a6;have h:(decide (rm>0x4000000000) || (rm==0x4000000000&&q&&&1==1))=decide (2^38omega omega apply И.mp;rw[е];cases neg;. simp only[Bool.false_eq_true,ite_false,UInt64.toNat_toUInt32,Nat.zero_add,k] . simp only[ite_true,UInt64.toNat_toUInt32,UInt64.toNat_or];have r:w.toNat ||| (2147483648:UInt64).toNat=2^31+w.toNat:=by have:=щ i 1;simp only[Nat.mul_one] at this;rw[this,Nat.or_comm];rfl rw[r];congr 1;omega lemma Dp (w:UInt32) (h:(w&&&0x7FFFFFFF)=0):rationalWord w=0:=by have a:=BA w;rw[h] at a;have d:=w.toNat_lt have b:w=0∨w=0x80000000:=by have:w.toNat=0∨w.toNat=2147483648:=by simp at a;omega rcases this with e | e;. exact Or.inl (И.mp (by simpa using e)) . exact Or.inr (И.mp (by simpa using e)) have c:expOf w=0∧fracOf w=0:=by rcases b with rfl | rfl<;>decide simp[rationalWord,decodeD,c,FloatLib.Numerics.Dyadic.toRat_eq_zero_iff] @[inline] def GU (w:UInt32):UInt64:= if w&&&0x7FFFFFFF==0 then 255 else (expOf w).toUInt64 @[inline] def GV (w:UInt32):UInt64:= if w&&&0x7FFFFFFF==0 then 0 else (fracOf w+0x800000).toUInt64 @[inline] def GW (e0:UInt64) (w:UInt32):UInt64:=GV w<<<(GU w-e0) @[inline] def GX (e0:UInt64) (w:UInt32):Bool:= FY w&&(w&&&0x7FFFFFFF==0 || (e0<=GU w&&GU w-e0<=37)) @[inline] def GY (e0:UInt64) (w:UInt32) (p:UInt64):UInt64:= if signOf w then p else p+GW e0 w @[inline] def GZ (e0:UInt64) (w:UInt32) (n:UInt64):UInt64:= if signOf w then n+GW e0 w else n lemma Dq (e0:UInt64) (w:UInt32) (h:GX e0 w=true): (GW e0 w).toNat<2^61∧rationalWord w= (if signOf w then -((GW e0 w).toNat:ℚ) else ((GW e0 w).toNat:ℚ))*2^((e0.toNat:Int)-150):=by unfold GX at h simp only[Bool.and_eq_true,Bool.or_eq_true,beq_iff_eq,decide_eq_true_eq] at h obtain ⟨f,i⟩:=h by_cases c:w&&&0x7FFFFFFF=0 . have j:GW e0 w=0:=by unfold GW GV;simp[c] rw[j,Dp w c];simp . obtain ⟨d,k⟩:=i.resolve_left c;have g:=BG w f;have a0:(w&&&0x7FFFFFFF).toNat≠0:=λe=>c (И.mp (by simpa using e));rw[BA] at a0;have l:=BD w;have m:(fracOf w).toNat=w.toNat%2^23:=BB w;have n:=w.toNat_lt;have x1:1<=(expOf w).toNat:=א;have x2:(expOf w).toNat<=254:=א;have f1:(fracOf w).toNat<2^23:=א;have ee:(GU w).toNat=(expOf w).toNat:=by unfold GU;simp[c] have em:(GV w).toNat=2^23+(fracOf w).toNat:=by unfold GV;simp only[c,beq_iff_eq,if_false,UInt32.toNat_toUInt64];rw[UInt32.toNat_add,Г (by show _+8388608<_;omega)];show _+8388608=_;omega have l1:=UInt64.le_iff_toNat_le.1 d;have l2:=UInt64.le_iff_toNat_le.1 k;rw[UInt64.toNat_sub_of_le _ _ d,ee] at l2;rw[ee] at l1;have l3:(expOf w).toNat-e0.toNat<=37:=l2 have es:(GW e0 w).toNat=(2^23+(fracOf w).toNat)*2^((expOf w).toNat-e0.toNat):=by unfold GW;have sh:(GU w-e0).toNat%64=(expOf w).toNat-e0.toNat:=by rw[UInt64.toNat_sub_of_le _ _ d,ee];exact Г א rw[UInt64.toNat_shiftLeft,em,sh,т];apply Г;have:2^((expOf w).toNat-e0.toNat)<=2^37:=д ב l3;have:(2^23+(fracOf w).toNat)*2^((expOf w).toNat-e0.toNat)<=2^24*2^37:=Nat.mul_le_mul א this;omega refine ⟨?_,?_⟩;. have a:2^((expOf w).toNat-e0.toNat)<=2^37:=д ב l3;have b:(2^23+(fracOf w).toNat)*2^((expOf w).toNat-e0.toNat)<=(2^24-1)*2^37:=Nat.mul_le_mul א a;rw[es];omega . have nz:expOf w≠0:=λe=>by rw[e] at x1;simp at x1 have ew:(2:ℚ)^(((expOf w).toNat:Int)-150)=2^((expOf w).toNat-e0.toNat)*2^((e0.toNat:Int)-150):=by rw[<-Ц,<-М С];congr 1;omega rw[es];simp only[rationalWord,decodeD,nz,ite_false,FloatLib.Numerics.Dyadic.toRat,FloatLib.Numerics.Dyadic.signedSignificand,ew];cases signOf w<;>simp<;>ring lemma Dr (e0:UInt64) (w:UInt32) (p n:UInt64) (V:ℚ) (B C:Nat) (d:C=2^61-1) (f:B+C<2^63) (a:GX e0 w=true) (g:p.toNat<=B) (h:n.toNat<=B) (b:V=((p.toNat:ℚ)-n.toNat)*2^((e0.toNat:Int)-150)): (GY e0 w p).toNat<=B+C∧(GZ e0 w n).toNat<=B+C∧ V+rationalWord w=(((GY e0 w p).toNat:ℚ)-(GZ e0 w n).toNat)*2^((e0.toNat:Int)-150):=by obtain ⟨i,c⟩:=Dq e0 w a have j:(GW e0 w).toNat<=C:=א unfold GY GZ rw[c,b] cases signOf w . simp only[Bool.false_eq_true,ite_false];have e:(p+GW e0 w).toNat=p.toNat+(GW e0 w).toNat:=by rw[Ы];exact Г א rw[e];refine ⟨by omega,by omega,?_⟩;push_cast;ring . simp only[ite_true];have e:(n+GW e0 w).toNat=n.toNat+(GW e0 w).toNat:=by rw[Ы];exact Г א rw[e];refine ⟨by omega,by omega,?_⟩;push_cast;ring @[inline] def Ga (p n e0:UInt64) (f:Unit->UInt32):UInt32:= if p==n then f () else let mag:=if pUInt32) (t:p.toNat<2^63) (u:n.toNat<2^63) (v:e0.toNat<=255) (R:UInt32) (l:f ()=R) (b:p≠n->∃d:FloatLib.Numerics.Dyadic, d.toRat=((p.toNat:ℚ)-n.toNat)*2^((e0.toNat:Int)-150)∧R=toWord (Model.roundDyadic Fmt d)):Ga p n e0 f=R:=by unfold Ga split . exact l . rename_i g;have a:p≠n:=λe=>g (by simp[e]);have i:p.toNat≠n.toNat:=λe=>a (UInt64.toNat_inj.mp e);obtain ⟨d,o,b⟩:=b a;dsimp only;obtain ⟨mag,j⟩:∃m,m=if pb1 (UInt64.le_iff_toNat_le.2 h);have b4:¬(277:UInt64).toNat<=(e0+mag.log2).toNat:=λh=>b2 (UInt64.le_iff_toNat_le.2 h);rw[eA] at b3 b4;have t1:(24:UInt64).toNat=24:=rfl;have t2:(277:UInt64).toNat=277:=rfl;rw[Do _ _ _ m0 m1 א א,b];congr 1 have s0:d.significand≠0:=by intro s;have:d.toRat=0:=(а d).2 s;rw[o] at this;have q:(p.toNat:ℚ)-n.toNat≠0:=by rw[sub_ne_zero];exact_mod_cast i exact (mul_ne_zero q (zpow_ne_zero _ С)) this refine roundDyadic_congr Fmt (by decide) _ _ m0 s0 ?_;rw[o,<-m2];simp only[FloatLib.Numerics.Dyadic.toRat,FloatLib.Numerics.Dyadic.signedSignificand];cases decide (psimp lemma Dt (w:UInt32):(GU w).toNat<=255:=by unfold GU;split;. decide . have:=BD w;simp only[UInt32.toNat_toUInt64];omega @[inline] def Gb (x y:UInt64):UInt64:=if xArray UInt32->Array UInt32} (f:USize->UInt32->UInt32) {e:USize} (c:∀i x,L i x=if ie.toNat<=x.size->x.size<2^32→ (L i x).size=x.size∧∀q,(L i x)[q]! =if i.toNat<=q∧q intro i x j _ _ rw[c,if_neg (by rw[А];omega)] exact ⟨rfl,λq=>(Д א).symm⟩ | succ d ih=> intro i x j n g have a:i?_⟩ rw[m,CZ _ _ _ _ g א,AS i e a,CX _ _ g] by_cases h:q=i.toNat . subst h;rw[if_neg א,if_pos rfl,if_pos ⟨Nat.le_refl _,by omega⟩,USize.ofNat_toNat] . rw[if_neg h];by_cases b:i.toNat+1<=q∧qX[b.toNat+(t/k*w+t%k)]!) (λ_=>oneW) def Gg (X:Array UInt32) (b:USize) (k w n t:Nat) (e:UInt64):UInt64:= if tsimp only[Bool.false_eq_true,ite_false,ite_true,ep,eq]<;>push_cast<;>ring lemma D1 (X:Array UInt32) (b:USize) (k w n:Nat):∀d t (e p q P Q:UInt64), n-t=d→p.toNat<2^63→q.toNat<2^63→Gh X b k w n t e p q=some (P,Q)→ P.toNat<2^63∧Q.toNat<2^63∧ (∀j,t<=j→j intro t e p q P Q C v x a by_cases m:t intro t e c by_cases a:t0&&k*k<=1024 then let e:=Gg X b k w (k*k) 0 255 match Gh X b k w (k*k) 0 e 0 0 with | none=>Gf X b k w | some (p,q)=>Ga p q e (fun _=>Gf X b k w) else Gf X b k w lemma D3 (X:Array UInt32) (b:USize) (k w:Nat):Gj X b k w=Gf X b k w:=by unfold Gj split ·dsimp only generalize i:Gg X b k w (k*k) 0 255=e generalize l:Gh X b k w (k*k) 0 e 0 0=r cases r with | none=>rfl | some pq=> obtain ⟨P,Q⟩:=pq obtain ⟨m,n,a,c⟩:=D1 X b k w (k*k) (k*k) 0 e 0 0 P Q (by omega) (by decide) (by decide) l have o:e.toNat<=255:=by rw[←i] exact D2 X b k w (k*k) (k*k) 0 255 (by omega) have g:Gi X b k w (k*k) 0=((P.toNat:ℚ)-Q.toNat)*2^((e.toNat:Int)-150):=by simpa only[UInt64.toNat_zero,Nat.cast_zero,sub_self,zero_mul,zero_add] using c.symm have h:(∑j∈Finset.range (k*k),rationalWord X[b.toNat+(j/k*w+j%k)]!*rationalWord oneW)= Gi X b k w (k*k) 0:=by simp only[Gi,Nat.sub_zero,Nat.zero_add,CP,mul_one] apply Ds P Q e _ m n o _ rfl intro f obtain ⟨d,p,q⟩:=CO (k*k) (fun j=>X[b.toNat+(j/k*w+j%k)]!) (fun _=>oneW) (fun j s=>⟨a j (by omega) s,by decide⟩) (by rw[h,g] exact mul_ne_zero (sub_ne_zero.mpr (by intro t exact f (UInt64.toNat_inj.mp (Nat.cast_injective t)))) (zpow_ne_zero _ (by decide))) refine ⟨d,?_,?_⟩ ·rw[p,h];exact g ·unfold Gf rw[AJ] exact q ·rfl section open ExactRuntime FloatLib.Floats.Formats.BinaryInterchange FloatLib.Floats open FloatLib.Floats.ExecFloat.Binary open Float.Model Float.Model.UnpackedFloat def Gk (X:Array UInt32) (b:USize) (k w:Nat):UInt32:= if k=2 then let i:=b.toNat let a0:=X[i]! let a1:=X[i+1]! let a2:=X[i+w]! let a3:=X[i+(w+1)]! let e0:=Gb (Gb (GU a0) (GU a1)) (Gb (GU a2) (GU a3)) if GX e0 a0&&GX e0 a1&&GX e0 a2&&GX e0 a3 then Ga (GY e0 a3 (GY e0 a2 (GY e0 a1 (GY e0 a0 0)))) (GZ e0 a3 (GZ e0 a2 (GZ e0 a1 (GZ e0 a0 0)))) e0 λ_=>Gj X b k w else Gj X b k w else Gj X b k w lemma D4 (X:Array UInt32) (b:USize) (k w:Nat):Gk X b k w=Gf X b k w:=by unfold Gk;simp only[D3];split . rename_i hk;subst hk;split . rename_i hc;simp only[Bool.and_eq_true] at hc;obtain ⟨⟨⟨h0,h1⟩,h2⟩,h3⟩:=hc;generalize hi:b.toNat=i at*;obtain ⟨p1,n1,v⟩:=Dv _ _ _ h0 h1;obtain ⟨p2,n2,v2⟩:=Dw _ _ _ _ _ _ p1 n1 v h2 h3;refine Ds _ _ _ _ p2 n2 ((Du _ _).trans ((Du _ _).trans (Dt _))) _ rfl λhne=>?_;have q0:b.toNat+(0/2*w+0%2)=i:=by simp[hi] have q1:b.toNat+(1/2*w+1%2)=i+1:=by simp[hi] have q2:b.toNat+(2/2*w+2%2)=i+w:=by simp[hi] have q3:b.toNat+(3/2*w+3%2)=i+(w+1):=by simp[hi] have hsum:(∑j∈Finset.range (2*2),rationalWord X[b.toNat+(j/2*w+j%2)]! * rationalWord oneW)=rationalWord X[i]! +rationalWord X[i+1]! +rationalWord X[i+w]! +rationalWord X[i+(w+1)]!:=by rw[show 2*2=4 from rfl] simp only[Finset.sum_range_succ,Finset.sum_range_zero,CP,mul_one,zero_add,q0,q1,q2,q3] have o:expOf oneW≠255:=by decide have hf:∀j,j<2*2->expOf X[b.toNat+(j/2*w+j%2)]!≠255∧expOf oneW≠255:=by intro j hj;rcases (by omega:j=0∨j=1∨j=2∨j=3) with rfl | rfl | rfl | rfl;. rw[q0];exact ⟨Dx _ _ h0,o⟩ . rw[q1];exact ⟨Dx _ _ h1,o⟩ . rw[q2];exact ⟨Dx _ _ h2,o⟩ . rw[q3];exact ⟨Dx _ _ h3,o⟩ obtain ⟨d,h4,h5⟩:=CO (2*2) (λj=>X[b.toNat+(j/2*w+j%2)]!) (λ_=>oneW) hf (by rw[hsum,v2] exact mul_ne_zero (sub_ne_zero.2 λe=>hne (UInt64.toNat_inj.mp (Nat.cast_injective e))) (zpow_ne_zero _ С)) refine ⟨d,?_,?_⟩;. rw[h4,hsum];exact v2 . unfold Gf;rw[AJ];exact h5 . rfl . rfl end @[noinline] def Gl (n:Nat) (s:UInt32):UInt32:= toWord (Model.div (ofW s) (ofW (natW n))) @[inline] def Gm (n:Nat) (j s:UInt32):UInt32:= if jUInt32) (sx:USize) (W x:Nat) (b q:USize) (out:Array UInt32):Array UInt32:= if xUInt32) (sy sx:USize) (W H y:Nat) (b q:USize) (out:Array UInt32):Array UInt32:= if yUInt32) (sc sy sx:USize) (W H c ch:Nat) (b q:USize) (out:Array UInt32):Array UInt32:= if ch(t.val/k*w+t.val%k).toUInt32 @[noinline] def Gt (c h w k n:Nat) (X off:Array UInt32) (j z:UInt32) (u nf zb zr:Float): Array UInt32:= Gr (λb=>Go X off k w n j z u nf zb b n.toUSize 0 zr zr 0) (h*w).toUSize (k*w).toUSize k.toUSize (w/k) (h/k) c 0 0 0 (Array.replicate (c*(h/k*(w/k))) 0) def Gu (c h w k:Nat) (X:Array UInt32):Array UInt32:= if c*h*w<=X.size∧X.size<2^32∧k*k<2^20∧ FZ X X.usize 0 (AZ X) 0xFFFFFFFF 0≠0xFFFFFFFF then let n:=k*k let off:=Gs k w let j:UInt32:=if n=4 then 2 else if n=64 then 6 else 255 let z:=Gl n (FP n (λ_=>0) (λ_=>oneW)) Gt c h w k n X off j z (dv oneW) (Fe n) (dv 0) 0 else avgpoolSpec c h w k X lemma D5 (s e:Float) (V:ℝ) (a:R (s-e)UInt32) (bw:UInt32) (hx:∀t,tFY (xw t)=true) (hw:∀t,tFY (ww t)=true) (hb:FY bw=true) (s e:Float) (d:FloatLib.Numerics.Dyadic) (hd:(d.toRat:ℝ)=Fd n xw ww bw) (hlo:R (s-e)hV (by rw[<-hc,(а c).mpr h0,ع]) obtain ⟨d',hd',hw'⟩:=CO (n+1) (λt=>if tif tby by_cases hj:jhV (by rw[<-hsum,h0,ع])) rw[CR n hn xw ww bw hx hw hb s e hlo hhi h,hw',roundDyadic_congr Fmt (by decide) d' d (e0 d' (by rw[hd',hsum])) (e0 d hd) (Rat.cast_injective (α:=ℝ) (by rw[hd',hsum,hd]))] def Gv (x y z:UInt32):FloatLib.Numerics.Dyadic:= Model.addDyadic ⟨Bool.xor (decodeD x).negative (decodeD y).negative, (decodeD x).significand*(decodeD y).significand, (decodeD x).exponent+(decodeD y).exponent⟩ (decodeD z) lemma D7 (x y z:UInt32) (a:expOf x≠255) (b:expOf y≠255) (c:expOf z≠255):Model.fma (ofW x) (ofW y) (ofW z)=Model.roundDyadic Fmt (Gv x y z):=by rw[Model.Proof.fma_eq_spec];have e:=toDyadic_ofUInt32 x a;have f:=toDyadic_ofUInt32 y b;have g:=toDyadic_ofUInt32 z c have o:Model.chooseNaN3 (Model.ofUInt32 x:Model Fmt) (Model.ofUInt32 y) (Model.ofUInt32 z)=none:=(Model.chooseNaN3_eq_none_iff _ _ _).2 ⟨Model.isNaN_eq_false_of_toDyadic?_some e,Model.isNaN_eq_false_of_toDyadic?_some f,Model.isNaN_eq_false_of_toDyadic?_some g⟩ simp only[Model.Spec.fma,ofW,o,Model.isInf_eq_false_of_toDyadic?_some e,Model.isInf_eq_false_of_toDyadic?_some f,Model.isInf_eq_false_of_toDyadic?_some g,Bool.or_false,Bool.false_eq_true,ite_false,e,f,g];rfl @[noinline] def Gw (relu:Bool) (x y z:UInt32):UInt32:= if h:expOf x≠255∧expOf y≠255∧expOf z≠255 then act relu (toWord (Model.roundDyadic Fmt (Gv x y z))) else Gd relu x y z lemma D9 (relu:Bool) (x y z:UInt32):Gw relu x y z=Gd relu x y z:=by unfold Gw split ·rename_i h rw[←D7 x y z h.1 h.2.1 h.2.2] rfl ·rfl lemma EA (x y z:UInt32) (a:expOf x≠255) (b:expOf y≠255) (c:expOf z≠255):((Gv x y z).toRat:ℝ)=wv x*wv y+wv z:=by have j:=FloatLib.Numerics.Dyadic.mul_toRat (decodeD x) (decodeD y);simp only[FloatLib.Numerics.Dyadic.mul,FloatLib.Numerics.Dyadic.mulFields] at j;rw[Gv,Model.addDyadic,FloatLib.Numerics.Dyadic.add_toRat,j,CJ x a,CJ y b,CJ z c];simp only[rationalWord,Rat.cast_add,Rat.cast_mul] lemma EB (relu:Bool) (r:UInt32) (a:expOf r≠255):Ge relu r=act relu r:=by cases relu;. rfl . show (if signOf r then 0 else r)=if signOf r&& !(expOf r=255&&fracOf r !=0) then 0 else r;simp only[a,decide_false,Bool.false_and,Bool.not_false,Bool.and_true] lemma EC (w:UInt32):toWord (ofW w)=w:=by apply И.mp;simp only[toWord,ofW,Model.toNatBits,ofUInt32_bits,UInt32.toNat_ofNat'];exact Г w.toBitVec.isLt lemma ED (w:UInt32) (h:expOf w≠255):Model.toReal (ofW w)=(sv w:ℝ)*2^((idxOf w:ℤ)-149):=by rw[show Model.toReal (ofW w)=wv w from rfl,CJ w h,rationalWord,decodeD_toRat];push_cast;rfl lemma EE (s j:UInt32) (b:j.toNat<=6) (a:j.toNat<(expOf s).toNat): (expOf (s-(j<<<(23:UInt32)))).toNat=(expOf s).toNat-j.toNat∧fracOf (s-(j<<<(23:UInt32)))=fracOf s∧signOf (s-(j<<<(23:UInt32)))=signOf s:=by rw[BD] at a have c:=s.toNat_lt have e:(j<<<(23:UInt32)).toNat=j.toNat*2^23:=by rw[UInt32.toNat_shiftLeft,т] exact Г (by simp;omega) have f:j<<<(23:UInt32)<=s:=by rw[Ж,e];omega have d:(s-(j<<<(23:UInt32))).toNat=s.toNat-j.toNat*2^23:=by rw[س _ _ f,e] refine ⟨?_,?_,?_⟩ . rw[BD,BD,d];omega . apply И.mp;rw[fracOf,fracOf,BB,BB,d];omega . rw[BE,BE,d];simp;omega lemma EF (s y j:UInt32) (f:j.toNat<=6) (a:expOf s≠255) (b:j.toNat<(expOf s).toNat) (d:expOf y≠255) (g:signOf y=false) (e:mantOf y=2^23) (k:idxOf y=126+j.toNat):toWord (Model.div (ofW s) (ofW y))=s-(j<<<(23:UInt32)):=by have A:sv y=2^23:=by unfold sv;rw[g,e];rfl have B:Model.isZero (ofW y)=false:=by rw[ofW,Model.isZero_eq_beq_zero_of_toDyadic?_some (toDyadic_ofUInt32 y d),decodeD_sig_zero,e];decide obtain ⟨C,D,E⟩:=EE s j f b;generalize s-(j<<<(23:UInt32))=r at C D E⊢;have N:=expOf_toNat_lt s;have O:(expOf s).toNat≠255:=λF=>a (И.mp (by simpa using F));have l:expOf r≠255:=by intro h;have n:=congrArg UInt32.toNat h;simp at n;omega have q:expOf r≠0:=by intro h;have n:=congrArg UInt32.toNat h;simp at n;omega have t:expOf s≠0:=by intro h;rw[h] at b;simp at b have G:sv r=sv s:=by unfold sv mantOf;rw[E,D,if_neg q,if_neg t] have H:(idxOf r:ℤ)=(idxOf s:ℤ)-j.toNat:=by unfold idxOf;rw[if_neg q,if_neg t,C];omega have o:Model.isFinite (ofW s)=true:=by simp[ofW,isFinite_ofUInt32,a] have u:Model.isFinite (ofW y)=true:=by simp[ofW,isFinite_ofUInt32,d] have v:Model.isFinite (ofW r)=true:=by simp[ofW,isFinite_ofUInt32,l] have x:Model.toReal (ofW y)=2^j.toNat:=by rw[ED _ d,A,k];push_cast;rw[show ((126:ℤ)+j.toNat-149)=(j.toNat:ℤ)+(-23) by ring,М С,Ц];field_simp;norm_num have I:Model.toReal (ofW r)=Model.toReal (ofW s)/2^j.toNat:=by rw[ED _ l,ED _ a,G,H,show ((idxOf s:ℤ)-j.toNat-149)=((idxOf s:ℤ)-149)+-(j.toNat:ℤ) by ring,М С,zpow_neg,Ц];field_simp have J: |Model.toReal (ofW s)/Model.toReal (ofW y)| ≤Model.toReal (Model.posMaxFinite Fmt):=by rw[x,abs_div,abs_of_pos (by positivity:(0:ℝ)<2^j.toNat)];exact (div_le_self (П _) (one_le_pow₀ ב)).trans (Model.abs_toReal_le_posMaxFinite_of_isIEEE_of_isFinite _ (by decide) o) have z:Model.isFinite (Model.div (ofW s) (ofW y))=true:=Model.isFinite_div_of_abs_div_le_posMaxFinite _ _ (by decide) o u B J;have p:=Model.toReal_div_eq_roundAt _ _ (by decide) o u B z;rw[x,<-I,Model.roundAt_toReal_eq _ v] at p have K:Model.toReal (Model.div (ofW s) (ofW y))≠0:=by rw[p,ED _ l];apply mul_ne_zero _ (zpow_ne_zero _ С);have:sv r≠0:=by unfold sv mantOf;split<;>omega exact_mod_cast this rw[Model.eq_of_toReal_eq_of_nonzero z v p K,EC] lemma EG (n:Nat) (j s:UInt32) (c:j=255∨(j=2∧n=4)∨(j=6∧n=64)):Gm n j s=Gl n s:=by unfold Gm;split . rename_i h;obtain ⟨a,b⟩:=h;have d:=expOf_toNat_lt s;rw[п] at a;rcases c with rfl | ⟨rfl,rfl⟩ | ⟨rfl,rfl⟩;. exfalso;simp at a;omega . exact (EF s _ 2 (by decide) b a (by decide) (by decide) (by decide) (by decide)).symm . exact (EF s _ 6 (by decide) b a (by decide) (by decide) (by decide) (by decide)).symm . rfl def Gx (xw:Nat->UInt32) (l:List Nat) (c:F1):F1:= l.foldl (λ(acc:F1) t=>let q:=dv (xw t)*dv oneW F1.mk (acc.s+q) (acc.t+q.abs)) c lemma EH (X off:Array UInt32) (k w n:Nat) (j z:UInt32) (nf zb:Float) (b m:USize) (xw:Nat->UInt32) (f:∀t:USize,t< m->FU X (b+(FU off t).toUSize)=xw t.toNat) (d:Nat):∀(t:USize) (s a:Float) (o:UInt32),t.toNat+d=m.toNat→ Go X off k w n j z (dv oneW) nf zb b m t s a o=Gn X b k w n j z nf zb (Gx xw (List.range' t.toNat d) ⟨s,a⟩).s (Gx xw (List.range' t.toNat d) ⟨s,a⟩).t ((List.range' t.toNat d).foldl (λc i=>c ||| xw i) o):=by induction d with | zero=> intro t s a o h rw[Go,Х (by rw[А];omega)] rfl | succ d ih=> intro t s a o h have e:t< m:=by rw[А];omega rw[Go,Р e] dsimp only rw[f t e,ih (t+1) _ _ _ (by rw[AS t m e];omega),AS t m e,List.range'_succ] rfl lemma EI (xw:Nat->UInt32) (l:List Nat):∀o:UInt32,l.foldl (λc i=>c ||| xw i) o=0->o=0∧∀i∈l,xw i=0:=by induction l with | nil=>exact λo h=>⟨h,by simp⟩ | cons i l ih=>intro o h;obtain ⟨a,b⟩:=ih _ h;obtain ⟨d,e⟩:=UInt32.or_eq_zero_iff.mp a;exact ⟨d,List.forall_mem_cons.mpr ⟨e,b⟩⟩ lemma EJ (n:Nat) (g:n<2^20) (xw:Nat->UInt32) (f:∀t,tFY (xw t)=true) (r:Fb ((Gx xw (List.range n) ⟨0,0⟩).s+dv 0) (Fe n*((Gx xw (List.range n) ⟨0,0⟩).t+(dv 0).abs))≠0xFFFFFFFF): Fb ((Gx xw (List.range n) ⟨0,0⟩).s+dv 0) (Fe n*((Gx xw (List.range n) ⟨0,0⟩).t+(dv 0).abs))=dotOf n xw (λ_=>oneW):=by obtain ⟨-,-,b⟩:=CI _ _ r obtain ⟨c,e⟩:=Bj n g xw (λ_=>oneW) 0 f (λ_ _=>by decide) (by decide) (List.range n) List.nodup_range ג (λt i k=>absurd (н.mpr i) k) _ _ ⟨rfl,rfl⟩ b have a:((∑j∈Finset.range n,rationalWord (xw j)*rationalWord oneW:ℚ):ℝ)=Fd n xw (λ_=>oneW) 0:=by rw[Fd,Bb 0 (by decide) (by decide),add_zero,Rat.cast_sum] refine ы rfl λt l=>?_ rw[Rat.cast_mul,CJ _ (CK _ (f t (Finset.mem_range.mp l))),CJ oneW (by decide)] obtain ⟨d,m,o⟩:=CO n xw (λ_=>oneW) (λj p=>⟨CK _ (f j p),by decide⟩) λh=>D5 _ _ _ c e r (by rw[<-a,h,ع]) rw[o] exact D6 n g xw (λ_=>oneW) 0 f (λ_ _=>by decide) (by decide) _ _ d (by rw[m,a]) c e r lemma EK (X:Array UInt32) (b:USize) (k w n:Nat) (a:n<2^20) (j:UInt32) (d:j=255∨(j=2∧n=4)∨(j=6∧n=64)) (xw:Nat->UInt32) (f:∀t,tFY (xw t)=true) (g:Gf X b k w=dotOf n xw (λ_=>oneW)): Gn X b k w n j (Gl n (FP n (λ_=>0) (λ_=>oneW))) (Fe n) (dv 0) (Gx xw (List.range n) ⟨0,0⟩).s (Gx xw (List.range n) ⟨0,0⟩).t ((List.range n).foldl (λc i=>c ||| xw i) 0)=Gl n (dotOf n xw (λ_=>oneW)):=by unfold Gn split . rename_i l;obtain ⟨-,m⟩:=EI xw _ _ l;have e:dotOf n xw (λ_=>oneW)=dotOf n (λ_=>0) (λ_=>oneW):=by unfold dotOf;congr 2;funext i;exact m _ (н.mpr i.isLt) rw[e,AJ] . dsimp only;rw[EG _ _ _ d];congr 1;split;. rw[D4];exact g . rename_i o;exact EJ _ a xw f (λh=>o (beq_iff_eq.mpr h)) lemma EL {c h w k ch y x t:Nat} (d:chUInt32) (out:Array UInt32) (p:Nat):Prop:= out.size=N∧N<2^32∧∀i,iout[i]! =sp i lemma EM {N p:Nat} {sp:Nat->UInt32} {out:Array UInt32} (h:Gy N sp out p) (f:p?_⟩;rw[CZ _ _ _ _ א א,a];by_cases e:i=p;. rw[if_pos e,e] . rw[if_neg e];exact d i א lemma EN (a s i:Nat):(a+(i+1)*s).toUSize=(a+i*s).toUSize+s.toUSize:=by rw[show a+(i+1)*s=a+i*s+s by ring];simp only[Nat.toUSize_eq,USize.ofNat_add] lemma EO {L:Nat->USize->USize->Array UInt32->Array UInt32} {g:USize->USize->Array UInt32->Array UInt32} {sb S n N q0 b0:Nat} {sp:Nat->UInt32} (c:∀i b q o,L i b q o=if iGy N sp o (q0+i*S)→Gy N sp (g (b0+i*sb).toUSize (q0+i*S).toUSize o) (q0+(i+1)*S)) (d:Nat): ∀i o,i+d=n->Gy N sp o (q0+i*S)→Gy N sp (L i (b0+i*sb).toUSize (q0+i*S).toUSize o) (q0+n*S):=by induction d with | zero=> intro i o e a rw[c,if_neg א,<-e] exact a | succ d ih=> intro i o e a rw[c,if_pos א,<-EN,<-EN] exact ih (i+1) _ א (f i o א a) lemma EP {f:USize->UInt32} {sc sy sx W H c N:Nat} {sp:Nat->UInt32} (a:c*(H*W)=N) (d:∀ch y t,chytby rw[Gr]) (λch o a1 h=>by have j:(ch+1)*(H*W)<=N:=a▸З _ a1 have:=EO (L:=Gq f sy.toUSize sx.toUSize W H) (sb:=sy) (S:=W) (n:=H) (N:=N) (q0:=ch*(H*W)) (b0:=ch*sc) (sp:=sp) (λ_ _ _ _=>by rw[Gq]) (λy o a2 h=>by have k:(y+1)*W<=H*W:=З _ a2 rw[ر] at j k have:=EO (L:=Gp f sx.toUSize W) (g:=λb q o=>FW o q (f b)) (sb:=sx) (S:=1) (n:=W) (N:=N) (q0:=ch*(H*W)+y*W) (b0:=ch*sc+y*sy) (sp:=sp) (λ_ _ _ _=>by rw[Gp];rfl) (λi o a3 h=>by have e1:ch*(H*W)+y*W+(i+1)*1=ch*(H*W)+y*W+i*1+1:=א have e2:ch*(H*W)+y*W+i=ch*(H*W)+y*W+i*1:=א rw[e1,d ch y i a1 a2 a3,e2] exact EM h א _ (CU _ (by have:=h.2.1;omega))) W 0 o א (by simpa using h) simpa [Nat.succ_mul,Nat.add_assoc] using this) H 0 o א (by simpa using h) simpa [Nat.succ_mul,Nat.add_assoc] using this) c 0 o א (by simpa using e) simp only[Nat.zero_mul,Nat.zero_add,Nat.add_zero,a] at this exact this lemma EQ {c H W q:Nat} (b:qUInt32) (c h w k:Nat) (g:c*h*w<2^32): Gr f (h*w).toUSize (k*w).toUSize k.toUSize (w/k) (h/k) c 0 0 0 (Array.replicate (c*(h/k*(w/k))) 0)= Array.ofFn (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) f ((ch*h+y*k)*w+x*k).toUSize:=by have j:c*(h/k*(w/k))<2^32:=by have a:h/k*(w/k)<=h*w:=Nat.mul_le_mul (Nat.div_le_self _ _) (Nat.div_le_self _ _) exact в ((Nat.mul_le_mul_left c a).trans (Nat.mul_assoc c h w).symm.le) g generalize m:h/k=H at* generalize o:w/k=W at* have d:=EP (f:=f) (sc:=h*w) (sy:=k*w) (sx:=k) (W:=W) (H:=H) (c:=c) (sp:=λq=>f ((q/(H*W)*h+q/W%H*k)*w+q%W*k).toUSize) rfl (λch y t a b l=>by obtain ⟨d1,d2⟩:=Br W (H*ch+y) t l obtain ⟨d3,d4⟩:=Br H ch y b have e:ch*(H*W)+y*W+t=W*(H*ch+y)+t:=by ring rw[e,d2,о H W,<-ذ,d1,d3,d4] congr 2 ring) (Array.replicate (c*(H*W)) 0) ⟨by simp,j,by simp⟩ apply ъ (by rw[d.1,Array.size_ofFn]) intro i a b rw[<-Е _ i a,d.2.2 i (by simpa using b),Array.getElem_ofFn] lemma ES {c h w k ch y x:Nat} {X:Array UInt32} (l:c*h*w<2^32) (b:X.size<2^32) (d:k*k<2^32) (e:ch(t/k*w+t%k).toUInt32) _ a,CX _ _ b] have e1:((t.toNat/k*w+t.toNat%k).toUInt32.toUSize).toNat=t.toNat/k*w+t.toNat%k:=by rw[Т,Nat.toUInt32_eq,е] exact Г א have e2:((ch*h+y*k)*w+x*k).toUSize.toNat=(ch*h+y*k)*w+x*k:=CU _ א show _=X[(ch*h+y*k+t.toNat/k)*w+x*k+t.toNat%k]! rw[AT _ _ (by rw[e1,e2];omega),e1,e2,e0] lemma ET {c h w k ch y x:Nat} {X:Array UInt32} (r:c*h*w<=X.size) (m:X.size<2^32) (n:k*k<2^20) (o:∀i,iFY X[i]! =true) (d:ch0) (λ_=>oneW))) (dv oneW) (Fe (k*k)) (dv 0) ((ch*h+y*k)*w+x*k).toUSize (k*k).toUSize 0 0 0 0= Gl (k*k) (dotOf (k*k) (poolAt h w k X ch y x) (λ_=>oneW)):=by have f:(k*k).toUSize.toNat=k*k:=CU _ א have q:0(ch*h+y*k+t/k)*w+x*k+t%kEL d b e a have e2:((ch*h+y*k)*w+x*k).toUSize.toNat=(ch*h+y*k)*w+x*k:=CU _ (by have:=l 0 q;simp at this;omega) rw[EH X _ k w (k*k) j _ _ _ _ _ (poolAt h w k X ch y x) (λt a=>ES א m א d b e t (by rw[А,f] at a;exact a)) (k*k) 0 0 0 0 (by rw[f,show (0:USize).toNat=0 from rfl,К]), show (0:USize).toNat=0 from rfl,<-List.range_eq_range'] refine EK X _ k w _ n j p _ (λt a=>o _ (by have:=l t a;omega)) ?_ unfold Gf rw[AJ] congr 1 funext t rw[e2] show _=X[(ch*h+y*k+t/k)*w+x*k+t%k]! congr 1 ring lemma EU:Gu=avgpoolSpec:=by funext c h w k X;unfold Gu;split . rename_i b;obtain ⟨d,a,e,f⟩:=b;simp only[avgpoolSpec,avgpoolWith];rw[Gt,ER _ c h w k א];apply congrArg Array.ofFn;funext ⟨q,g⟩;obtain ⟨a1,a2,a3⟩:=EQ g;dsimp only;refine ET d a e (Ck X a f).2.2.1 a1 a2 a3 _ ?_;split_ifs with e1 e2;. exact Or.inr (Or.inl ⟨rfl,e1⟩) . exact Or.inr (Or.inr ⟨rfl,e2⟩) . exact Or.inl rfl . rfl end section open ExactRuntime def Gz (rows inW outW:Nat) (relu:Bool) (X W b:Array UInt32):Array UInt32:= if rows=1 then GG ⟨inW,1,1,outW,1,1,1,0⟩ relu X W b else linearWith FP rows inW outW relu X W b lemma EV (inW outW:Nat) (relu:Bool) (X W b:Array UInt32):linearSpec 1 inW outW relu X W b=conv2dSpec ⟨inW,1,1,outW,1,1,1,0⟩ relu X W b:=by simp only[linearSpec,linearWith,conv2dSpec,conv2dWith,ConvShape.ho,ConvShape.wo];apply ъ;. simp . intro q c d;have a:q>>(31:UInt32)==0 then 0x80000000+m else 0x80000000-m @[inline] def G1 (a b:Word):Word:= if a&&&0x7F800000==0x7F800000 || b&&&0x7F800000==0x7F800000 then FR a b else let p:=G0 a let q:=G0 b if p?_;unfold G2;by_cases a:m%2^23+1<2^23 . rw[show (m+1)/2^23=m/2^23 by omega,show (m+1)%2^23=m%2^23+1 by omega];split;. omega . exact Ш א (Nat.two_pow_pos _) . rw[show (m+1)/2^23=m/2^23+1 by omega,show (m+1)%2^23=0 by omega,show m%2^23=2^23-1 by omega];cases m/2^23 with | zero=>norm_num | succ e=>have:=Nat.two_pow_pos e;rw[Д א,Д א,Nat.add_sub_cancel,Nat.add_sub_cancel,pow_succ];omega lemma EY (w:Word):(w&&&0x7FFFFFFF).toNat=w.toNat%2^31∧(expOf w).toNat=w.toNat%2^31/2^23∧(fracOf w).toNat=w.toNat%2^31%2^23:=by have h:w.toNat<2^32:=w.toNat_lt;have a1:(0x7FFFFFFF:UInt32).toNat=2^31-1:=rfl;have a2:(0xFF:UInt32).toNat=2^8-1:=rfl;have a3:(0x7FFFFF:UInt32).toNat=2^23-1:=rfl;have a4:(23:UInt32).toNat%32=23:=rfl;unfold expOf fracOf;rw[О,О,О,л,a1,a2,a3,a4,В,В,В,Ю];omega lemma EZ (w:Word):signOf w=true↔2^31<=w.toNat:=by have h:w.toNat<2^32:=w.toNat_lt;have a1:(0x80000000:UInt32).toNat=2^31:=rfl;unfold signOf;rw[bne_iff_ne,ne_eq,<-И,О,a1,Nat.and_two_pow,Nat.testBit_eq_decide_div_mod_eq];by_cases c:w.toNat/2^31%2=1;. rw[decide_eq_true c];simp only[Bool.toNat_true,UInt32.toNat_zero];omega . rw[decide_eq_false c];simp only[Bool.toNat_false,UInt32.toNat_zero];omega lemma Ea (w:Word):mantOf w<<< idxOf w=G2 (w.toNat%2^31):=by obtain ⟨-,a,b⟩:=EY w;unfold mantOf idxOf G2;rw[т];by_cases h:expOf w=0;. rw[Л h,Л h,Л (by rw[<-a,h];rfl),b,pow_zero,Nat.mul_one] . rw[Д h,Д h,Д (λe=>h (И.mp (by rw[a,e];rfl))),a,b] lemma Eb (w:Word):FQ w=if w.toNat<2^31 then (G2 (w.toNat%2^31):Int) else -(G2 (w.toNat%2^31):Int):=by unfold FQ;rw[Ea];by_cases c:w.toNat<2^31;. rw[Л c,Д (λe=>by have:=(EZ w).mp e;omega)] . rw[Д c,Л ((EZ w).mpr א)] lemma Ec (w:Word):(G0 w).toNat=if w.toNat<2^31 then 2^31+w.toNat%2^31 else 2^31-w.toNat%2^31:=by have h:w.toNat<2^32:=w.toNat_lt;have a1:(0x80000000:UInt32).toNat=2^31:=rfl;have a2:(31:UInt32).toNat%32=31:=rfl;have e:(w>>>(31:UInt32)).toNat=w.toNat/2^31:=by rw[л,a2,Ю] have a:=(EY w).1;unfold G0;dsimp only;by_cases c:w.toNat<2^31;. have e0:w>>>(31:UInt32)=0:=И.mp (by rw[e,UInt32.toNat_zero];omega);rw[e0,Л (show ((0:UInt32)==0)=true from rfl),Л c,UInt32.toNat_add,a,a1];omega . have e0:(w>>>(31:UInt32)==0)=false:=by rw[beq_eq_false_iff_ne];intro b;rw[b,UInt32.toNat_zero] at e;omega rw[e0,Д ג,Д c,UInt32.toNat_sub,a,a1];omega lemma Ed (a b:Word) (h:G0 a0by have:=EX c;omega by_cases c1:a.toNat<2^31<;>by_cases c2:b.toNat<2^31<;>simp only[c1,c2,ite_true,ite_false] at d⊢;. have:=EX (א:a.toNat%2^31>>n)&&&m)<<decide . rw[Д (by simpa using b)];exact AK a lemma Ei (a b:Word):G1 a b=FR a b:=by unfold G1;by_cases g:(a&&&0x7F800000==0x7F800000 || b&&&0x7F800000==0x7F800000)=true;. rw[Л g] . rw[Д g];simp only[Bool.or_eq_true,not_or] at g;have f:=Ef a g.1;have c:=Ef b g.2;have d:¬(expOf a=255∨expOf b=255):=by simp[f,c] dsimp only;by_cases p:G0 aG3 inp off b (k*k).toUSize 0 (FU inp b)) (h*w).toUSize (k*w).toUSize k.toUSize (w/k) (h/k) c 0 0 0 (Array.replicate (c*(h/k*(w/k))) 0) else FS c h w k inp lemma Ej (X off:Array UInt32) (b m:USize) (xw:Nat->UInt32) (e:∀t:USize,t< m->FU X (b+(FU off t).toUSize)=xw t.toNat) (d:Nat): ∀(t:USize) (a:UInt32),t.toNat+d=m.toNat→G3 X off b m t a=(List.range' t.toNat d).foldl (λa i=>G1 a (xw i)) a:=by induction d with | zero=> intro t a h rw[G3,Х (by rw[А];omega)] rfl | succ d ih=> intro t a h have c:t< m:=by rw[А];omega rw[G3,Р c,e t c,ih (t+1) _ (by rw[AS t m c];omega),AS t m c,List.range'_succ,List.foldl_cons] lemma Ek:G4=maxpoolSpec:=by rw[<-AR];funext c h w k inp;unfold G4;split . rename_i j;obtain ⟨a,b,d⟩:=j;rw[ER _ c h w k a];simp only[FS];apply congrArg Array.ofFn;funext ⟨q,l⟩;obtain ⟨a1,a2,a3⟩:=EQ l;dsimp only;have f:(k*k).toUSize.toNat=k*k:=CU _ d have e:∀{ch y x:Nat},chyxES a b d a1 a2 a3 t (by rw[А,f] at i;exact i)) (k*k) 0 _ (by rw[f,show (0:USize).toNat=0 from rfl,К]),show (0:USize).toNat=0 from rfl,<-List.range_eq_range'];simp only[Ei] . rfl end end Submission namespace Submission open ExactRuntime lemma El (c h w k:Nat) (X:Array Word) (a:c*h*w≤X.size) (b:X.size<2^32) (d:k*k<2^20) (e:∀i,i0) (fun _=>oneW))) (dv oneW) (Fe (k*k)) (dv 0) 0=avgpoolSpec c h w k X:=by unfold avgpoolSpec avgpoolWith rw [Gt,ER _ c h w k (lt_of_le_of_lt a b)] apply congrArg Array.ofFn funext ⟨q,f⟩ obtain ⟨a1,a2,a3⟩:=EQ f dsimp only refine ET a b d e a1 a2 a3 _ ?_ split_ifs with e1 e2 ·exact Or.inr (Or.inl ⟨rfl,e1⟩) ·exact Or.inr (Or.inr ⟨rfl,e2⟩) ·exact Or.inl rfl end Submission namespace Submission open ExactRuntime def G5:Array Word:=Array.ofFn (n:=16) fun k=> Gl (k.val*k.val) (FP (k.val*k.val) (fun _=>0) (fun _=>oneW)) def G6 (k:Nat):Word:= if h:k<16 then G5[k]'(by simp [G5];exact h) else Gl (k*k) (FP (k*k) (fun _=>0) (fun _=>oneW)) lemma Em (k:Nat):G6 k=Gl (k*k) (FP (k*k) (fun _=>0) (fun _=>oneW)):=by unfold G6 split ·simp only [G5,Array.getElem_ofFn] ·rfl def G7 (c h w k:Nat) (X:Array Word):Array Word:= if c*h*w<=X.size&&X.size<2^32&&k*k<2^20&&X.all FY then let n:=k*k let j:UInt32:=if n=4 then 2 else if n=64 then 6 else 255 let z:=G6 k Gt c h w k n X (Gs k w) j z (dv oneW) (Fe n) (dv 0) 0 else Gu c h w k X @[inline] def G8 (a b:Word):Word:=if asimp_all only[UInt32.le_iff_toNat_le,UInt32.lt_iff_toNat_lt]<;>omega lemma Eo (a:Word):G8 a a=a:=by simp[G8] lemma Ep (a b c:Word):G8 (G8 a b) c=G8 a (G8 b c):=by unfold G8 split_ifs<;>apply UInt32.toNat_inj.mp<;> simp_all only[UInt32.lt_iff_toNat_lt]<;>omega lemma Eq (a b:Word) (m:a<0x7F800000) (n:b<0x7F800000):G1 a b=G8 a b:=by have d:=UInt32.lt_iff_toNat_lt.mp m norm_num only [UInt32.reduceToNat] at d have f:=UInt32.lt_iff_toNat_lt.mp n norm_num only [UInt32.reduceToNat] at f have i:a.toNat<2^31:=by omega have j:b.toNat<2^31:=by omega have nmask (w:Word) (o:w.toNat<0x7F800000):w&&&0x7F800000≠0x7F800000:=by intro h have l:(w&&&0x7F800000).toNat≤w.toNat:=by rw[UInt32.toNat_and];exact Nat.and_le_left rw[h] at l norm_num only [UInt32.reduceToNat] at l omega have g:(a&&&0x7F800000==0x7F800000 || b&&&0x7F800000==0x7F800000)=false:=by simp[nmask a d,nmask b f] have oa:(G0 a).toNat=2^31+a.toNat:=by rw[Ec,if_pos i,Nat.mod_eq_of_lt i] have ob:(G0 b).toNat=2^31+b.toNat:=by rw[Ec,if_pos j,Nat.mod_eq_of_lt j] rw[G1,g] simp only[Bool.false_eq_true,ite_false] by_cases c:asimp_all only[UInt32.le_iff_toNat_le,UInt32.lt_iff_toNat_lt]<;>omega have f:a<0x7F800000:=by simp only[UInt32.le_iff_toNat_le,UInt32.lt_iff_toNat_lt] at*;omega have i:b<0x7F800000:=by simp only[UInt32.le_iff_toNat_le,UInt32.lt_iff_toNat_lt] at*;omega have j:c<0x7F800000:=by simp only[UInt32.le_iff_toNat_le,UInt32.lt_iff_toNat_lt] at*;omega have k:d<0x7F800000:=by simp only[UInt32.le_iff_toNat_le,UInt32.lt_iff_toNat_lt] at*;omega have g:G8 a b<0x7F800000:=by simp only[UInt32.le_iff_toNat_le,UInt32.lt_iff_toNat_lt] at*;omega have e:G8 (G8 a b) c<0x7F800000:=by simp only[UInt32.le_iff_toNat_le,UInt32.lt_iff_toNat_lt] at*;omega rw[Eq a a f f,Eo,Eq a b f i,Eq (G8 a b) c g j, Eq (G8 (G8 a b) c) d e k,Ep] @[inline] def G9 (inp:Array UInt32) (w:Nat) (b:USize):UInt32:= let v0:=FU inp b let v1:=FU inp (b+1) let v2:=FU inp (b+w.toUInt32.toUSize) let v3:=FU inp (b+(w+1).toUInt32.toUSize) G1 (G1 (G1 (G1 v0 v0) v1) v2) v3 @[inline] def HA (inp:Array UInt32) (w:Nat) (b:USize):UInt32:= let v0:=FU inp b let v1:=FU inp (b+1) let v2:=FU inp (b+w.toUInt32.toUSize) let v3:=FU inp (b+(w+1).toUInt32.toUSize) let z:=G8 (G8 v0 v1) (G8 v2 v3) if z<0x7F800000 then z else G9 inp w b lemma Es (inp:Array UInt32) (w:Nat) (b:USize):HA inp w b=G9 inp w b:=by unfold HA dsimp only split ·rename_i h exact (Er _ _ _ _ h).symm ·rfl def HB (c h w k:Nat) (inp:Array UInt32):Array UInt32:= if k==2&&c*h*w<2^32&&inp.size<2^32 then Gr (HA inp w) (h*w).toUSize (2*w).toUSize 2 (w/2) (h/2) c 0 0 0 (Array.replicate (c*(h/2*(w/2))) 0) else G4 c h w k inp private theorem four_mod:4 % 2^System.Platform.numBits=4:=by have hs:2^32≤USize.size:=USize.le_size change 2^32≤2^System.Platform.numBits at hs apply Nat.mod_eq_of_lt omega private theorem small_mod (n:Nat) (h:n≤4):n % 2^System.Platform.numBits=n:=by have hs:2^32≤USize.size:=USize.le_size change 2^32≤2^System.Platform.numBits at hs apply Nat.mod_eq_of_lt omega private theorem add11:(1:USize)+1=2:=by apply USize.toNat_inj.mp norm_num [USize.toNat_add,USize.toNat_ofNat',small_mod] private theorem add21:(2:USize)+1=3:=by apply USize.toNat_inj.mp norm_num [USize.toNat_add,USize.toNat_ofNat',small_mod] lemma Et (w:Nat):FU (Gs 2 w) 0=0:=by simp [Gs,FU] lemma Eu (w:Nat):FU (Gs 2 w) 1=1:=by simp [Gs,FU,USize.lt_iff_toNat_lt,four_mod] lemma Ev (w:Nat):FU (Gs 2 w) 2=w.toUInt32:=by simp [Gs,FU,USize.le_iff_toNat_le,four_mod] lemma Ew (w:Nat):FU (Gs 2 w) 3=(w+1).toUInt32:=by simp [Gs,FU,USize.le_iff_toNat_le,four_mod] lemma Ex (inp:Array UInt32) (w:Nat) (b:USize): HA inp w b= G3 inp (Gs 2 w) b (4:USize) 0 (FU inp b):=by set_option maxHeartbeats 1000000 in rw[Es] simp [G9,G3,Et,Eu,Ev,Ew, USize.lt_iff_toNat_lt,four_mod,small_mod,add11,add21] lemma Ey (c h w k:Nat) (inp:Array UInt32): HB c h w k inp=G4 c h w k inp:=by unfold HB split ·rename_i a simp only [Bool.and_eq_true,beq_iff_eq,decide_eq_true_eq] at a obtain ⟨⟨f,d⟩,e⟩:=a subst k unfold G4 simp only [d,e,show 2*2<2^32 by norm_num,and_self,↓reduceIte] congr 1 funext b exact Ex inp w b ·rfl lemma Ez:G7=avgpoolSpec:=by funext c h w k X unfold G7 split ·rename_i b simp only[Bool.and_eq_true,decide_eq_true_eq] at b obtain ⟨⟨⟨e,f⟩,g⟩,j⟩:=b have a: ∀i,i>>23&&&255)=255 conv_lhs=>rw [show (255:Nat)=2^8-1 from rfl,Nat.and_two_pow_sub_one_eq_mod,Nat.shiftRight_eq_div_pow] exact a lemma E1 (w:Word) (a:expOf w≠255):(Float32.ofBits w).toBits=w:=by change UInt32.ofBitVec (pack Float.Model.Format.binary32 (unpack Float.Model.Format.binary32 w.toBitVec))=w rw [Model.pack_unpack_eq] have b:=E0 w a rw [if_neg (by intro h;exact b h.1)] lemma finite (w:Word) (a:expOf w≠255):(Float32.ofBits w).isFinite=true:=by change (unpack Float.Model.Format.binary32 (Float32.ofBits w).toBits.toBitVec).isFinite=true rw [E1 w a] simp only [unpack,E0 w a,ite_false] split ·split<;>rfl ·rfl end RootNativeFinite namespace FastResidual open FloatLib.Floats.Formats.BinaryInterchange FloatLib.Floats.ExecFloat lemma E2 (z:Float32): Model.ofFloat32Model z.toModel= (Model.ofUInt32 z.toBits:Model ExactRuntime.Fmt):=by change Model.ofModelBits (fmt:=ExactRuntime.Fmt) (z.toBits.toBitVec)= (Model.ofNatBits z.toBits.toNat:Model ExactRuntime.Fmt) unfold Model.ofModelBits Model.ofNatBits Model.ofBits FloatFormat.ofWordNat congr 1 change z.toBits.toBitVec=BitVec.ofNat 32 z.toBits.toNat exact (BitVec.ofNat_toNat 32 z.toBits.toBitVec).symm lemma E3 (w:UInt32) (a:(Float32.ofBits w).toBits=w): Model.ofFloat32Model (Float32.ofBits w).toModel= (Model.ofUInt32 w:Model ExactRuntime.Fmt):=by rw [E2,a] lemma E4 (w:UInt32): ExactRuntime.toWord (Model.ofUInt32 w:Model ExactRuntime.Fmt)=w:=by change UInt32.ofNat (w.toNat % 2^32)=w rw [Nat.mod_eq_of_lt (by simpa using w.toNat_lt_size)] exact UInt32.ofNat_toNat lemma E5 (x y:UInt32) (g:(Float32.ofBits x).isFinite=true) (i:(Float32.ofBits y).isFinite=true) (a:(Float32.ofBits x).toBits=x) (b:(Float32.ofBits y).toBits=y): (Float32.ofBits x+Float32.ofBits y).toBits= ExactRuntime.toWord (Model.add (ExactRuntime.ofW x) (ExactRuntime.ofW y)):=by let fx:=Float32.ofBits x let fy:=Float32.ofBits y have c:(Model.toModel (Model.ofFloat32Model fx.toModel)).isFinite=true:=by change fx.toModel.unpack.isFinite=true exact g have d:(Model.toModel (Model.ofFloat32Model fy.toModel)).isFinite=true:=by change fy.toModel.unpack.isFinite=true exact i have e:fx.toModel.unpack=(ExactRuntime.ofW x).toModel:=by exact congrArg (fun z:Model ExactRuntime.Fmt=>z.toModel) (E3 x a) have f:fy.toModel.unpack=(ExactRuntime.ofW y).toModel:=by exact congrArg (fun z:Model ExactRuntime.Fmt=>z.toModel) (E3 y b) have j:Model.ofFloat32Model (fx+fy).toModel= Model.add (ExactRuntime.ofW x) (ExactRuntime.ofW y):=by change Model.ofFloat32Model (Float32.Model.add fx.toModel fy.toModel)=_ rw [Float32.Model.add,Model.ofFloat32Model_pack] rw [e,f] have h:=Model.add_eq_ofModel_add_of_isFinite (fmt:=ExactRuntime.Fmt) (by decide) (Model.ofFloat32Model fx.toModel) (Model.ofFloat32Model fy.toModel) c d rw [E3 x a,E3 y b] at h exact h.symm have k:=congrArg ExactRuntime.toWord j simpa only [E2,E4] using k end FastResidual namespace NativeBitsOneFile open ExactRuntime @[inline] def HC (relu:Bool) (x y:UInt32):UInt32:= if hx:expOf x≠255∧expOf y≠255 then act relu (Float32.ofBits x+Float32.ofBits y).toBits else Submission.Gc relu x y def HD (relu:Bool) (b:Array Word) (e i:USize) (a:Array Word):Array Word:= if h:iHC relu w (Submission.FU b i)) (by intro i x;rw [HD];rfl) a.size 0 a (by rw [k];simp) (by rw [k]) c apply Array.ext ·rw [l.1];simp [addReluSpec] ·intro i n o have j:iby omega local notation"ב"=>by norm_num local notation"ג"=>by simp local notation"ד"=>by linarith local notation"А"=>USize.lt_iff_toNat_lt local notation"Б"=>mul_le_mul_of_nonneg_right local notation"В"=>Nat.and_two_pow_sub_one_eq_mod local notation"Г"=>Nat.mod_eq_of_lt local notation"Д"=>ite_eq_right local notation"Е"=>getElem!_pos local notation"Ж"=>UInt32.le_iff_toNat_le local notation"З"=>Nat.mul_le_mul_right local notation"И"=>UInt32.toNat_inj local notation"Й"=>mul_le_mul_of_nonneg_left local notation"К"=>Nat.zero_add local notation"Л"=>ite_eq_left local notation"М"=>zpow_add₀ local notation"Н"=>abs_nonneg local notation"О"=>Nat.pos_of_ne_zero local notation"П"=>Nat.cast_nonneg local notation"Р"=>abs_of_nonneg local notation"С"=>UInt32.toNat_and local notation"Т"=>two_ne_zero local notation"У"=>zpow_le_zpow_right₀ local notation"Ф"=>dite_eq_left local notation"Х"=>UInt32.toNat_toUSize local notation"Ц"=>abs_add_le local notation"Ч"=>dite_eq_right local notation"Ш"=>mul_nonneg local notation"Щ"=>mul_lt_mul_of_pos_right local notation"Ъ"=>UInt64.toNat_add local notation"Ы"=>Nat.mod_lt local notation"Ь"=>USize.toNat_one local notation"Э"=>zpow_natCast local notation"Ю"=>FloatLib.Numerics.Dyadic.cast_toRat local notation"Я"=>Nat.shiftRight_eq_div_pow local notation"а"=>Nat.add_zero local notation"б"=>FloatLib.Numerics.Dyadic.toRat_eq_zero_iff local notation"в"=>getElem!_neg local notation"г"=>mul_le_mul local notation"д"=>Nat.add_assoc local notation"е"=>Nat.pow_le_pow_right local notation"ж"=>Nat.lt_or_eq_of_le local notation"з"=>Nat.le_mul_of_pos_right local notation"и"=>Nat.pos_of_mul_pos_left local notation"й"=>UInt32.toNat_shiftRight local notation"к"=>UInt64.toNat_shiftRight local notation"л"=>List.mem_range local notation"м"=>Nat.mul_comm local notation"н"=>UInt32.lt_iff_toNat_lt local notation"о"=>UInt64.lt_iff_toNat_lt local notation"п"=>zpow_pos local notation"р"=>Nat.div_eq_of_lt local notation"с"=>Nat.shiftLeft_eq local notation"т"=>Bool.and_eq_true_iff local notation"у"=>Nat.add_mul local notation"ф"=>Nat.div_lt_of_lt_mul local notation"х"=>Nat.one_mul local notation"ц"=>Nat.pow_add local notation"ч"=>Nat.lt_succ_iff local notation"ш"=>UInt32.toNat_ofNat' local notation"щ"=>Nat.two_pow_add_eq_or_of_lt local notation"ъ"=>Array.ext local notation"ы"=>Finset.sum_congr local notation"ь"=>Nat.exists_eq_add_of_le local notation"э"=>UInt64.toNat_and local notation"ю"=>lt_of_mul_lt_mul_right local notation"я"=>Nat.div_div_eq_div_mul local notation"ذ"=>Nat.succ_mul local notation"ر"=>Nat.succ_pos local notation"ز"=>UInt32.toNat_sub_of_le local notation"س"=>List.mem_filter local notation"ش"=>Nat.mod_add_div local notation"ص"=>Array.getElem_push_eq local notation"ض"=>Array.getElem_push_lt local notation"ط"=>le_trans local notation"ظ"=>Rat.cast_zero open ExactRuntime FloatLib.Floats.Formats.BinaryInterchange FloatLib.Floats section open FloatLib.Numerics end @[inline] def HF (A B:UInt64):UInt32:= let x:UInt64:=(A+(0x0FFFFFFF:UInt64))>>>(29:UInt64) let y:UInt64:=(B+(0x0FFFFFFF:UInt64))>>>(29:UInt64) let ex:UInt64:=(x>>>(23:UInt64))&&&(0x7FF:UInt64) if x==y&&ex-(897:UInt64)<(254:UInt64) then (((x>>>(34:UInt64))<<<(31:UInt64)) ||| ((x&&&(0x3FFFFFFFF:UInt64))-((896:UInt64)<<<(23:UInt64)))).toUInt32 else 0xFFFFFFFF @[inline] def HG (s:Float):UInt32:= let a:=s.toBits HF (a+2) (a-2) section open ExactRuntime FloatLib.Floats.Formats.BinaryInterchange FloatLib.Floats open FloatLib.Floats.ExecFloat.Binary noncomputable def R (f:Float):ℝ:=Model.toReal (toModel (ofFloat f)) lemma Ac (x:Float):R x=Model.toReal (Submission.Ff x):=rfl lemma B5 (x y:Float) (c:x.isFinite=true) (d:y.isFinite=true) (e: |R x| + |R y| ≤2^(1000:ℤ)): (x+y).isFinite=true∧R (x+y)=Model.roundAt FloatFormat.binary64 (R x+R y):=by have f:Submission.Ff (x+y)=Model.add (Submission.Ff x) (Submission.Ff y):=toModel_ofFloat_add_of_isFinite x y c d have a:Model.isFinite (Submission.Ff x)=true:=by rw[Submission.Ad,c] have b:Model.isFinite (Submission.Ff y)=true:=by rw[Submission.Ad,d] constructor . rw[<-Submission.Ad,f];exact Model.isFinite_add_of_abs_add_le_posMaxFinite _ _ Submission.Aa a b (e.trans Submission.Af) . rw[Ac,f];exact Model.toReal_add_eq_roundAt_of_abs_add_le_posMaxFinite _ _ Submission.Aa a b (e.trans Submission.Af) open Float.Model.UnpackedFloat in open Float.Model.UnpackedFloat in open Float.Model.UnpackedFloat in open Float.Model.UnpackedFloat in lemma CO (x y:Float) (c:x.isFinite=true) (d:y.isFinite=true) (e: |R x| * |R y| ≤2^(1000:ℤ)): (x*y).isFinite=true∧R (x*y)=Model.roundAt FloatFormat.binary64 (R x*R y):=by have f:Submission.Ff (x*y)=Model.mul (Submission.Ff x) (Submission.Ff y):=Submission.Al x y c d have a:Model.isFinite (Submission.Ff x)=true:=by rw[Submission.Ad,c] have b:Model.isFinite (Submission.Ff y)=true:=by rw[Submission.Ad,d] constructor . rw[<-Submission.Ad,f];exact Model.isFinite_mul_of_abs_mul_le_posMaxFinite _ _ Submission.Aa a b (e.trans Submission.Af) . rw[Ac,f];exact Model.toReal_mul_eq_roundAt_of_abs_mul_le_posMaxFinite _ _ Submission.Aa a b (e.trans Submission.Af) noncomputable def Fg:ℝ:=2^(-1021:ℤ) noncomputable def Fh:ℝ:=2^(300:ℤ) lemma Bf:0(Model.modelSignBit s==decide (256<=i))&&m==2^52&& e==((i%256:ℕ):ℤ)-202&&(i%256 !=0) | .zero _=>i%256==0 | _=>false lemma Bs:∀i,i<512->Fj i=true:=by decide+kernel lemma BS (i:ℕ) (d:i<512): (Submission.FX i).isFinite=true∧R (Submission.FX i)=if i%256=0 then 0 else (if 256<=i then -1 else 1)*2^(((i%256:ℕ):ℤ)-150):=by have a:=Bs i d rw[Submission.A6] have c:(Float.ofBits (Submission.Fi i)).toModel.unpack=Float.Model.UnpackedFloat.unpack Float.Model.Format.binary64 (Submission.Fi i).toBitVec:=Model.unpack_pack_unpack _ _ unfold Fj at a rw[CG,c] change (Float.ofBits (Submission.Fi i)).toModel.unpack.isFinite=true∧_ rw[c] cases b:Float.Model.UnpackedFloat.unpack Float.Model.Format.binary64 (Submission.Fi i).toBitVec with | notANumber=>rw[b] at a;simp at a | infinity s=>rw[b] at a;simp at a | zero s=> rw[b] at a simp only[beq_iff_eq] at a refine ⟨rfl,?_⟩ simp[a] | finite s m e h=> rw[b] at a simp only[Bool.and_eq_true,beq_iff_eq,bne_iff_ne] at a obtain ⟨⟨⟨f,g⟩,j⟩,k⟩:=a refine ⟨rfl,?_⟩ have e:((2^52:ℕ):ℝ)*2^(((i%256:ℕ):ℤ)-202)=2^(((i%256:ℕ):ℤ)-150):=by rw[Nat.cast_pow,Nat.cast_ofNat,<-Э,<-М ב] congr 1 push_cast ring rw[Model.unpackedToReal_finite,Submission.Ae,j,f,g,mul_assoc,e] simp only[decide_eq_true_eq,k,↓reduceIte] noncomputable def Fk (v:ℕ):ℝ:= if v=0 then 0 else ((2^23+v%2^23:ℕ):ℝ)*2^(((v/2^23:ℕ):ℤ)-150) lemma CI (w:UInt32) (e:Submission.FY w=true):Submission.wv w=(if 2^31<=w.toNat then -1 else 1)*Fk (w.toNat%2^31):=by have i:=w.toNat_lt;have f:=Submission.BG w e;have a:=Submission.BD w;have c:(fracOf w).toNat=w.toNat%2^23:=Submission.BB w;have b:expOf w≠255:=by intro h;rw[h] at a;change 255=_ at a;omega have g:Submission.wv w=(decodeD w).toReal:=by unfold Submission.wv ofW;rw[Model.toReal_eq,toDyadic_ofUInt32 w b] rw[g];unfold decodeD Fk;by_cases d:w.toNat%2^31=0 . have e0:expOf w=0:=by apply И.mp;rw[a];show _=0;omega have f0:fracOf w=0:=by apply И.mp;rw[c];show _=0;omega simp only[e0,f0,d,↓reduceIte];simp[FloatLib.Numerics.Dyadic.toReal,FloatLib.Numerics.Dyadic.signedSignificand] . have e0:expOf w≠0:=by intro h;rw[h] at a;change 0=_ at a;omega simp only[e0,d,↓reduceIte];have f1:w.toNat%2^31%2^23=(fracOf w).toNat:=by rw[c];omega have f2:w.toNat%2^31/2^23=(expOf w).toNat:=by rw[a];omega rw[f1,f2];simp only[FloatLib.Numerics.Dyadic.toReal,FloatLib.Numerics.Dyadic.signedSignificand,Submission.BE];simp;split_ifs<;>ring lemma Af (w:UInt32) (j:Submission.FY w=true):(Submission.dv w).isFinite=true∧R (Submission.dv w)=Submission.wv w:=by have r:=w.toNat_lt;have b:=Submission.BG w j;have c:=Submission.BF w;have d:=Ei ((w&&&0x7FFFFF) ||| 0x800000) (by rw[c];omega);have m:(w>>>(23:UInt32)).toUSize.toNat=w.toNat/2^23:=by rw[Х,Submission.BC] have e:=BS (w.toNat/2^23) א;unfold Submission.dv;rw[Submission.A9,m];have f: |R ((w&&&0x7FFFFF) ||| 0x800000).toFloat| ≤2^24:=by rw[d.2,c,Р (П _)];have:2^23+w.toNat%2^23<=2^24:=א;exact_mod_cast this have g: |R (Submission.FX (w.toNat/2^23))| ≤2^106:=by rw[e.2];split_ifs;. simp all_goals simp only[abs_mul,abs_neg,abs_one,one_mul];rw[abs_of_pos (by positivity)];have:(2:ℝ)^(((w.toNat/2^23%256:ℕ):ℤ)-150)<=2^(106:ℤ):=У ב א;simpa using this have n: |R ((w&&&0x7FFFFF) ||| 0x800000).toFloat| * |R (Submission.FX (w.toNat/2^23))| ≤2^(1000:ℤ):=by have h:=Ay;have e1:(2:ℝ)^24<=2^256*2^42:=ב;have e2:(2:ℝ)^106<=2^256*2^42:=ב;exact (г (f.trans (e1.trans h)) (g.trans (e2.trans h)) (Н _) Bf.le).trans ED obtain ⟨o,p⟩:=CO _ _ d.1 e.1 n;refine ⟨o,?_⟩;rw[p,d.2,e.2,CI w j,c];rcases b with q | ⟨h,s⟩;. have e0:w.toNat/2^23%256=0:=א;rw[q];simp only[e0,↓reduceIte,mul_zero,Model.roundAt_zero];simp[Fk] . have e0:¬w.toNat/2^23%256=0:=א;have e1:w.toNat%2^31/2^23=w.toNat/2^23%256:=א;have e2:w.toNat%2^31%2^23=w.toNat%2^23:=א;have e3:(256<=w.toNat/2^23)↔2^31<=w.toNat:=א;unfold Fk;rw[e1,e2];simp only[e0,e3,show¬w.toNat%2^31=0 by omega,↓reduceIte];have i:-1074<=((w.toNat/2^23%256:ℕ):ℤ)-150:=א;have a:2^23+w.toNat%2^23<2^53:=א;generalize ((w.toNat/2^23%256:ℕ):ℤ)-150=k at i⊢;generalize 2^23+w.toNat%2^23=M at a⊢;by_cases l:2^31<=w.toNat;. have:=Submission.Ax (-(M:ℤ)) k (by simpa using a) i;simp only[l,↓reduceIte];push_cast at this;rw[show (M:ℝ)*(-1*2^k)=-(M:ℝ)*2^k by ring,show -1*((M:ℝ)*2^k)=-(M:ℝ)*2^k by ring];exact this . have:=Submission.Ax (M:ℤ) k (by simpa using a) i;simp only[l,↓reduceIte,one_mul];push_cast at this;exact this lemma Ax:(2:ℝ)^128<=Fh:=by have h:(2:ℝ)^128<=2^256*2^42:=ב;linarith [Ay] lemma E9 (a b:UInt32) (d:Submission.FY a=true) (e:Submission.FY b=true): (Submission.dv a*Submission.dv b).isFinite=true∧ |R (Submission.dv a*Submission.dv b)-Submission.wv a*Submission.wv b| ≤1/2^53*(|Submission.wv a*Submission.wv b| +Fg)∧ |Submission.wv a*Submission.wv b| ≤2^256:=by obtain ⟨fa,ra⟩:=Af a d obtain ⟨fb,rb⟩:=Af b e have la:=Submission.Ba a d have lb:=Submission.Ba b e have c: |Submission.wv a*Submission.wv b| ≤2^256:=by rw[abs_mul] calc |Submission.wv a| * |Submission.wv b| ≤2^128*2^128:=г la lb (Н _) (by positivity) _=2^256:=ב obtain ⟨g,f⟩:=E8 _ _ fa fb (by rw[ra];exact la.trans Ax) (by rw[rb];exact lb.trans Ax) rw[ra,rb] at f exact ⟨g,f,c⟩ end section open ExactRuntime FloatLib.Floats.Formats.BinaryInterchange FloatLib.Floats open FloatLib.Floats.ExecFloat.Binary section open Float.Model Float.Model.UnpackedFloat end lemma CA (f:Float) (s:Bool) (E F:Nat) (a:1<=E) (c:E<2047) (d:F<2^52) (h:f.toBits.toNat=(if s then 2^63 else 0)+E*2^52+F): f.isFinite=true∧R f=(if s then -1 else 1)*((2^52+F:Nat):ℝ)*2^((E:Int)-1075):=by have b:=Submission.B8 f s E F a c d h refine ⟨Submission.B9 f _ b,?_⟩ rw[R,Model.toReal_eq,b] cases s<;>simp[FloatLib.Numerics.Dyadic.toReal,FloatLib.Numerics.Dyadic.signedSignificand] lemma BE (A B:UInt64) (h:HF A B≠0xFFFFFFFF): ∃(S:Bool) (ex fr:Nat),897<=ex∧ex<1151∧fr<2^23∧HF A B=UInt32.ofNat ((if S then 2^31 else 0)+(ex-896)*2^23+fr)∧Submission.Fp A.toNat S ex fr∧Submission.Fp B.toNat S ex fr:=by unfold HF at h⊢ dsimp only at h⊢ have b:=Submission.CC A have c:=Submission.CC B generalize (A+(0x0FFFFFFF:UInt64))>>>(29:UInt64)=x at h b⊢ generalize (B+(0x0FFFFFFF:UInt64))>>>(29:UInt64)=y at h c⊢ have d:=Submission.CD x generalize (x>>>(23:UInt64))&&&(0x7FF:UInt64)=ex at h d⊢ split at h . rename_i i;have j:=i;obtain ⟨a,i⟩:=т.mp i;have a:x=y:=by simpa using a obtain ⟨e,f⟩:=Submission.CE ex (by simpa using i);rw[d] at e f;subst a;have k:=A.toNat_lt;have l:=B.toNat_lt;have g:x.toNat<2^35:=א;simp only[j,ite_true];exact ⟨_,_,_,e,f,by omega,Submission.CF x g e f,Submission.CB A.toNat x.toNat k b e f,Submission.CB B.toNat x.toNat l c e f⟩ . exact absurd rfl h set_option maxRecDepth 8192 in end section open ExactRuntime FloatLib.Floats.Formats.BinaryInterchange FloatLib.Floats open FloatLib.Floats.ExecFloat.Binary end section open ExactRuntime FloatLib.Floats.Formats.BinaryInterchange FloatLib.Floats open FloatLib.Floats.ExecFloat.Binary end section open ExactRuntime FloatLib.Floats.Formats.BinaryInterchange FloatLib.Floats open FloatLib.Floats.ExecFloat.Binary open Float.Model Float.Model.UnpackedFloat end section open ExactRuntime FloatLib.Floats.Formats.BinaryInterchange FloatLib.Floats open FloatLib.Floats.ExecFloat.Binary open Float.Model Float.Model.UnpackedFloat end section open ExactRuntime FloatLib.Floats.Formats.BinaryInterchange FloatLib.Floats open FloatLib.Floats.ExecFloat.Binary lemma FA (A P Q T g:Nat) (a:g=0∨g=2^63) (b:A<2^64) (e1:(A+2)%2^64=g+P) (e2:(2^64-2+A)%2^64=g+Q) (t1:2^61<=T) (t2:T<2^63-2^60) (l1:Tsimp) s.toBits.toNat_lt e1 e2 א א l1 u1 l2 u2 exact ⟨S,ex,fr,Q+2,d,e,f,g,a,b,c⟩ lemma Cf (v W z u:ℝ) (c:0linarith [b.1,b.2] set_option maxRecDepth 8192 in lemma Dm (ex fr E F:Nat) (y:897<=ex) (z:ex<1151) (o:fr<2^23) (p:F<2^52) (m:(ex*2^23+fr)*2^29+2(2^53+fr*2^30-2^29)*2^((ex:Int)-1076)(2^53+fr*2^30-2^29)*2^((ex:Int)-1076)cases S<;> simp only[Bool.false_eq_true,ite_false,ite_true,Int.ofNat_eq_natCast,Int.cast_neg,Int.cast_natCast] at b . exact ⟨by linarith only [b],rfl⟩ . exfalso;linarith only [c,e,g,b] . exfalso;linarith only [c,e,g,b] . exact ⟨by linarith only [b],rfl⟩ obtain ⟨a,rfl⟩:=a have s:m≠0:=by rintro rfl simp at a linarith only [c,e,a] have f:=Submission.B4 neg m q (2^23+fr) ((ex:Int)-1046) s א א א א (by rw[a,k];push_cast;linarith only [i]) (by intro n have h:fr≠0:=by intro w;exact n א have:=j h rw[a,k];push_cast;linarith only [this]) (by intro _ rw[a,k];linarith only [c]) have e1:((ex:Int)-1046+150).toNat=ex-896:=א have e2:(2^23+fr)%2^23=fr:=א rw[f,e1,e2] lemma Az (s:Float) (d:FloatLib.Numerics.Dyadic) (e: |R s-(d.toRat:ℝ)| ≤1/2^53*(|(d.toRat:ℝ)| +Fg)) (h:HG s≠0xFFFFFFFF):HG s=toWord (Model.roundDyadic Fmt d):=by obtain ⟨S,ex,fr,M,j,k,l,m,n,q,r⟩:=EJ s h;have f:M=(M/2^52)*2^52+M%2^52:=א;have g:M%2^52<2^52:=Ы _ ב;generalize M/2^52=E at f;generalize M%2^52=F at f g;subst f;obtain ⟨-,o⟩:=CA s S E F א א g (by rw[n,д]);rw[o] at e obtain ⟨W,i,p⟩:∃W:ℝ,(d.toRat:ℝ)=(if S then -W else W)∧ |((2^52+F:Nat):ℝ)*2^((E:Int)-1075)-W| ≤1/2^53*(|W| +Fg):=by cases S . simp only[Bool.false_eq_true,ite_false,one_mul] at e⊢;exact ⟨_,rfl,e⟩ . simp only[ite_true] at e⊢;refine ⟨-(d.toRat:ℝ),by simp,?_⟩;rw[abs_neg,show ((2^52+F:Nat):ℝ)*2^((E:Int)-1075) - -(d.toRat:ℝ)=-(-1*((2^52+F:Nat):ℝ)*2^((E:Int)-1075)-(d.toRat:ℝ)) by ring,abs_neg];exact e obtain ⟨a,b,c⟩:=Dm ex fr E F j k l g א א W p;rw[m];exact (Cc d S ex fr j k l W i a b c).symm lemma CV (w:UInt32) (e:Submission.FY w=true): ∃(m k:ℤ),Submission.wv w=(m:ℝ)*2^k∧m.natAbs<2^25∧-160<=k:=by have f:=w.toNat_lt;rw[CI w e];unfold Fk;by_cases c:w.toNat%2^31=0;. exact ⟨0,0,by rw[if_pos c];simp,by norm_num,by norm_num⟩ . simp only[c,ite_false];have a:-160<=(((w.toNat%2^31/2^23:ℕ):ℤ)-150):=א;have b:2^23+w.toNat%2^31%2^23<2^25:=א;generalize ((w.toNat%2^31/2^23:ℕ):ℤ)-150=k at a⊢;generalize 2^23+w.toNat%2^31%2^23=M at b⊢;by_cases d:2^31<=w.toNat;. exact ⟨-(M:ℤ),k,by rw[if_pos d];push_cast;ring,by simpa using b,a⟩ . exact ⟨(M:ℤ),k,by rw[if_neg d];push_cast;ring,by simpa using b,a⟩ lemma Dh (a b:UInt32) (c:Submission.FY a=true) (d:Submission.FY b=true):(Submission.dv a*Submission.dv b).isFinite=true∧R (Submission.dv a*Submission.dv b)=Submission.wv a*Submission.wv b:=by obtain ⟨fa,ra⟩:=Af a c;obtain ⟨fb,rb⟩:=Af b d;have la:=(Submission.Ba a c).trans Ax;have lb:=(Submission.Ba b d).trans Ax obtain ⟨f,g⟩:=CO _ _ fa fb (by rw[ra,rb] exact (г la lb (Н _) Bf.le).trans ED) refine ⟨f,?_⟩;obtain ⟨m,k,e1,h,j⟩:=CV a c;obtain ⟨n,l,e2,i,o⟩:=CV b d;have e:Submission.wv a*Submission.wv b=((m*n:ℤ):ℝ)*2^(k+l):=by rw[e1,e2,М Т];push_cast;ring rw[g,ra,rb,e];refine Submission.Ax _ _ ?_ א;rw[Int.natAbs_mul];have:=Nat.mul_lt_mul'' h i;omega lemma FB (x y z:UInt32) (b:Submission.FY x=true) (c:Submission.FY y=true) (e:Submission.FY z=true) (d:FloatLib.Numerics.Dyadic) (g:(d.toRat:ℝ)=Submission.wv x*Submission.wv y+Submission.wv z): |R (Submission.dv x*Submission.dv y+Submission.dv z)-(d.toRat:ℝ)| ≤1/2^53*(|(d.toRat:ℝ)| +Fg):=by obtain ⟨f1,r1⟩:=Dh x y b c obtain ⟨-,-,l⟩:=E9 x y b c obtain ⟨f2,r2⟩:=Af z e have a:(2:ℝ)^256<=Fh:=by have:(2:ℝ)^256<=2^256*2^42:=ב linarith [Ay] obtain ⟨-,f⟩:=BI _ _ f1 f2 (by rw[r1];exact l.trans a) (by rw[r2];exact (Submission.Ba z e).trans Ax) rw[r1,r2] at f rw[g] exact f end section open ExactRuntime FloatLib.Floats.Formats.BinaryInterchange FloatLib.Floats open FloatLib.Floats.ExecFloat.Binary @[inline] def HH (relu g:Bool) (sw tw:UInt32) (y z:Float) (w:UInt32):UInt32:= if g&&Submission.FY w then let r:=HG (Submission.dv w*y+z) if r==0xFFFFFFFF then Submission.Gw relu w sw tw else Submission.Ge relu r else Submission.Gw relu w sw tw @[specialize] def HI (f:UInt32->UInt32) (e i:USize) (x:Array UInt32):Array UInt32:= if h:iUInt32) (e i:USize) (x:Array UInt32) (he:e.toNat<=x.size):Array UInt32:= if h:iUInt32) (e:USize): ∀d (i:USize) (x:Array UInt32) (b:e.toNat<=x.size) (a:x.sizeHJ f e i x b=HI f e i x:=by intro d;induction d with | zero=> intro i x b a g have h:¬i intro i x b a g have h:iUInt32) (e i:USize) (x:Array UInt32):Array UInt32:= if he:e.toNat<=x.size∧x.sizeUInt32) (e i:USize) (x:Array UInt32): HK f e i x=HI f e i x:=by unfold HK split ·rename_i b by_cases a:iSubmission.Gw true v sw tw) ((ch+1)*hw).toUSize (ch*hw).toUSize x HL c hw s t (ch+1) x else x termination_by c-ch def HM (c hw:Nat) (s t:Array UInt32) (ch:Nat) (x:Array UInt32):Array UInt32:= if chSubmission.Gw false v sw tw) ((ch+1)*hw).toUSize (ch*hw).toUSize x HM c hw s t (ch+1) x else x termination_by c-ch def HN (relu:Bool) (c hw:Nat) (s t:Array UInt32) (ch:Nat) (x:Array UInt32):Array UInt32:= if relu then HL c hw s t ch x else HM c hw s t ch x def HO (relu:Bool) (c hw:Nat) (s t:Array UInt32) (ch:Nat) (x:Array UInt32):Array UInt32:= if chSubmission.Gw relu v sw tw):=by funext v simp only[HH,Bool.false_and,Bool.false_eq_true,ite_false] lemma FF (c b:Nat) (s t:Array UInt32):∀d ch x,c-ch=d→ HL c b s t ch x=HO true c b s t ch x:=by intro d;induction d using Nat.strong_induction_on with | h d ih=> intro ch x f by_cases a:ch simp only[e,Bool.false_eq_true,ite_false,ite_true,FE] all_goals exact ih (c-(ch+1)) (by omega) (ch+1) _ rfl ·rw[HL,HO,if_neg a,if_neg a] lemma FG (c b:Nat) (s t:Array UInt32):∀d ch x,c-ch=d→ HM c b s t ch x=HO false c b s t ch x:=by intro d;induction d using Nat.strong_induction_on with | h d ih=> intro ch x f by_cases a:ch simp only[e,Bool.false_eq_true,ite_false,ite_true,FE] all_goals exact ih (c-(ch+1)) (by omega) (ch+1) _ rfl ·rw[HM,HO,if_neg a,if_neg a] lemma FH (relu:Bool) (c a:Nat) (s t:Array UInt32) (ch:Nat) (x:Array UInt32): HN relu c a s t ch x=HO relu c a s t ch x:=by cases relu ·simp only[HN,Bool.false_eq_true,ite_false] exact FG c a s t (c-ch) ch x rfl ·simp only[HN,ite_true] exact FF c a s t (c-ch) ch x rfl def HP (relu:Bool) (c hw:Nat) (x s t:Array UInt32):Array UInt32:= if x.size=c*hw∧x.size<2^32 then HN relu c hw s t 0 x else scaleShiftSpec relu c hw x s t section open ExactRuntime FloatLib.Floats.Formats.BinaryInterchange FloatLib.Floats open FloatLib.Floats.ExecFloat.Binary open Float.Model Float.Model.UnpackedFloat end lemma C1 (relu:Bool) (s:Float) (h:HG s≠0xFFFFFFFF):Submission.Ge relu (HG s)=act relu (HG s):=by apply Submission.EB;obtain ⟨S,ex,fr,e,f,g,c,-,-⟩:=BE _ _ h;have a:HG s=_:=c;intro d;have b:(expOf (HG s)).toNat=255:=by rw[d];rfl rw[Submission.BD,a,ш] at b;split at b<;>omega lemma Db (relu g:Bool) (sw tw w:UInt32) (j:g=true->Submission.FY sw=true∧Submission.FY tw=true):HH relu g sw tw (Submission.dv sw) (Submission.dv tw) w=Submission.Gd relu w sw tw:=by unfold HH;simp only [Submission.D9];split . rename_i k;obtain ⟨l,d⟩:=т.mp k;obtain ⟨e,f⟩:=j l;split;. rfl . rename_i m;have a:HG (Submission.dv w*Submission.dv sw+Submission.dv tw)≠0xFFFFFFFF:=λh=>m (beq_iff_eq.mpr h);have i:=Submission.CK _ d;have b:=Submission.CK _ e;have c:=Submission.CK _ f;rw[C1 _ _ a,Az _ (Submission.Gv w sw tw) (FB w sw tw d e f _ (Submission.EA _ _ _ i b c)) a,Submission.Gd,Submission.D7 _ _ _ i b c] . rfl lemma FI (relu:Bool) (c e:Nat) (s t:Array UInt32) (d:Nat): ∀(ch:Nat) (x:Array UInt32),ch+d=c->x.size=c*e->x.size<2^32→ (HO relu c e s t ch x).size=x.size∧∀q,q intro ch x i _ _ rw[HO,if_neg א] refine ⟨rfl,λq f=>?_⟩ rw[if_neg (by rw[(א:ch=c)];omega)] | succ d ih=> intro ch x i j k rw[HO,if_pos א] dsimp only rw[FD] have o:(ch+1)*e<=c*e:=З _ א have p:(ch+1)*e=ch*e+e:=ذ _ _ have e1:((ch+1)*e).toUSize.toNat=(ch+1)*e:=Submission.CU _ א have e0:(ch*e).toUSize.toNat=ch*e:=Submission.CU _ א obtain ⟨g,l⟩:=Submission.Dy (λ_=>HH relu (Submission.FY s[ch]! &&Submission.FY t[ch]!) s[ch]! t[ch]! (Submission.dv s[ch]!) (Submission.dv t[ch]!)) (L:=HI _ ((ch+1)*e).toUSize) (λ_ _=>by rw[HI];rfl) e (ch*e).toUSize x א א k obtain ⟨m,n⟩:=ih (ch+1) _ א (g.trans j) א refine ⟨m.trans g,λq f=>?_⟩ rw[n q f,l,e0,e1,Db _ _ _ _ _ (λh=>т.mp h)] by_cases a:(ch+1)*e<=q . rw[if_pos a,if_neg א,if_pos א] . rw[if_neg a];by_cases b:ch*e<=q;. rw[if_pos ⟨b,by omega⟩,if_pos b,Nat.div_eq_of_lt_le b א] . rw[if_neg א,if_neg b] lemma DG:HP=scaleShiftSpec:=by funext relu c d x s t;unfold HP;simp only [FH];split . rename_i h;obtain ⟨a,g⟩:=h;obtain ⟨e,j⟩:=FI relu c d s t c 0 x א a g;apply ъ;. simp[scaleShiftSpec,e,a] . intro i f k;have b:i