library colibrilib.stdq — module PowRoundThe powers and the roundings to a smaller number
module PowRound655use int.Int656use int.Power as IP657use real.RealInfix658use real.FromInt659use real.PowerInt as RP660use mach.int.Int63661use colibrilib.zarith.Z as Z662use colibrilib.zarith.Q as Q663use colibrilib.zarith.Zbit as Zbit664use colibrilib.zbit.ZbitInt665use int.EuclideanDivision as E666use StdQ'impl667use colibrilib.spec.Value668Valid (175ms) (colibri2)669let rec ghost from_int_power (a:int) (n:int) : unit670requires { 0 <= n }671ensures { from_int (IP.power a n) = RP.power (from_int a) n }672variant { n }673= if n > 0 then begin674from_int_power a (n - 1);675assert { IP.power a n = a * IP.power a (n - 1) };676assert { RP.power (from_int a) n = from_int a *. RP.power (from_int a) (n - 1) }677end678Valid (352ms) (colibri2)679let rec ghost power_div (x y:real) (n:int) : unit680requires { 0 <= n }681requires { y <> 0. }682ensures { RP.power (x /. y) n = RP.power x n /. RP.power y n }683ensures { RP.power y n <> 0. }684variant { n }685= if n > 0 then begin686power_div x y (n - 1);687assert { RP.power (x /. y) n = (x /. y) *. RP.power (x /. y) (n - 1) };688assert { RP.power x n = x *. RP.power x (n - 1) };689assert { RP.power y n = y *. RP.power y (n - 1) }690end691
The power q^n (Std.Q.pow)
Valid (101ms) (colibri2 23) (split_vc) (depth 1)let pow (q:Q.t) (n:int63) : Q.t694requires { 0 <= n \/ Q.real q <> 0. }695requires { -0x4000000000000000 < n }696ensures { value1 Q.real (fun x -> if 0 <= n then RP.power x n else 1. /. RP.power x (- n)) q result }697= let ghost x = from_int q.Q.num in698let ghost y = from_int q.Q.den in699if n < 0 then begin700let m = - n in701assert { q.Q.num <> 0 };702let a = Z.pow q.Q.den m in703let b = Z.pow q.Q.num m in704from_int_power q.Q.den (to_int m);705from_int_power q.Q.num (to_int m);706power_div x y (to_int m);707power_div y x (to_int m);708assert { RP.power x m <> 0. by x <> 0. };709assert { b <> 0 by from_int b = RP.power x m };710let r = Q.make a b in711assert { RP.power (y /. x) m = 1. /. RP.power (x /. y) m712by RP.power (y /. x) m = RP.power y m /. RP.power x m713/\ RP.power (x /. y) m = RP.power x m /. RP.power y m714/\ RP.power y m <> 0. };715r716end else begin717let a = Z.pow q.Q.num n in718let b = Z.pow q.Q.den n in719from_int_power q.Q.num (to_int n);720from_int_power q.Q.den (to_int n);721power_div x y (to_int n);722assert { b <> 0 by from_int b = RP.power y n };723Q.make a b724end725
A positive integer with fewer bits than den (Std.Q.smaller_den); the test 0 < r never fails, it gives the positivity without the bits
Valid (99ms) (colibri2)let smaller_den (max_size_bit:int) (den:int) : int729requires { 0 < den }730ensures { 0 < result }731= let s = Zbit.numbits den in732let remaining =733if s > max_size_bit then E.div max_size_bit 4 else E.div s 4 in734if remaining = 0 then 1735else736let r = ZbitInt.asr_int den (s - remaining) in737if r > 0 then r else 1738
A number below q with a smaller denominator (Std.Q.round_down_to_small_number when q is big)
Valid (393ms) (colibri2 4) (cvc5) (split_vc) (depth 1)let round_down_to_small (max_size_bit:int) (q:Q.t) : Q.t742ensures { Q.real result <=. Q.real q }743= let d = smaller_den max_size_bit q.Q.den in744assert { Gcd.gcd 1 d = 1 by D.divides (Gcd.gcd 1 d) 1 /\ Gcd.gcd 1 d <> 0 };745round_down_to q (Q.make_exact 1 d)746Valid (391ms) (colibri2 4) (cvc5) (split_vc) (depth 1)747let round_up_to_small (max_size_bit:int) (q:Q.t) : Q.t748ensures { Q.real q <=. Q.real result }749= let d = smaller_den max_size_bit q.Q.den in750assert { Gcd.gcd 1 d = 1 by D.divides (Gcd.gcd 1 d) 1 /\ Gcd.gcd 1 d <> 0 };751round_up_to q (Q.make_exact 1 d)752end753