library colibrilib.stdq — module QBitsThe bits of a rational in lowest terms: its value n 2^e when the denominator is a power of 2, and the test of a numerator or a denominator of at least k bits (for fp_conv.Env)
module QBits923use int.Int924use int.Power925use int.Abs926use option.Option927use real.RealInfix928use real.FromInt929use colibrilib.pow2r.Pow2r930use colibrilib.zarith.Q as ZQ931use colibrilib.zarith.Zbit as Zbit932use colibrilib.zbit.ZbitInt933use StdQ as Q934
q as n 2^e when its denominator is a power of 2
Valid (71ms) (colibri2)let dyadic (q: Q.t) : option (int, int)937ensures { match result with938| Some (n, e) -> Q.real q = from_int n *. pow2r e939| None -> true end }940= let z = Q.to_zarith q in941{proof…} Q.num_den q; {qed}942let k = Zbit.trailing_zeros z.ZQ.den in943if z.ZQ.den = lsl_int 1 k then begin944{proof…}945Zbit.lsl_mul 1 k;946assert { pow2r (-k) = 1.0 /. from_int (power 2 k) };947assert { from_int z.ZQ.num /. from_int z.ZQ.den948= from_int z.ZQ.num *. (1.0 /. from_int (power 2 k)) };949{qed}950Some (z.ZQ.num, -k)951end else None952
q as the fraction n / d in lowest terms, 0 < d
Valid (42ms) (colibri2)let num_den (q: Q.t) : (int, int)955returns { (n, d) -> n = Q.num q /\ d = Q.den q /\ 0 < d /\956Q.real q = from_int n /. from_int d }957= let z = Q.to_zarith q in958{proof…} Q.num_den q; {qed}959(z.ZQ.num, z.ZQ.den)960
The numerator or the denominator of q in lowest terms is at least 2^k
Valid (404ms) (cvc5)let big (k: int) (q: Q.t) : bool964requires { 0 <= k }965ensures { result <-> power 2 k <= abs (Q.num q) \/ power 2 k <= Q.den q }966= let z = Q.to_zarith q in967{proof…}968Q.num_den q;969Zbit.numbits_lsl k; Zbit.lsl_mul 1 k;970let lemma bits (n: int) : unit971requires { 0 <= n }972ensures { Zbit.numbits n > k <-> power 2 k <= n }973= if pure { power 2 k <= n } then Zbit.numbits_ge_pos (power 2 k) n974else if pure { Zbit.numbits n > k } then begin975Zbit.numbits_lt_lsl n k; absurd976end in977bits (abs z.ZQ.num); bits z.ZQ.den;978{qed}979Zbit.numbits (abs z.ZQ.num) > k || Zbit.numbits z.ZQ.den > k980end981