Common — library colibrilib.stdq — module QBits

The 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)

923
module QBits
924
use int.Int
925
use int.Power
926
use int.Abs
927
use option.Option
928
use real.RealInfix
929
use real.FromInt
930
use colibrilib.pow2r.Pow2r
931
use colibrilib.zarith.Q as ZQ
932
use colibrilib.zarith.Zbit as Zbit
933
use colibrilib.zbit.ZbitInt
934
use StdQ as Q

q as n 2^e when its denominator is a power of 2

  Valid (71ms) (colibri2)
937
let
dyadic
(q: Q.t) : option (int, int)
938
ensures { match result with
939
| Some (n, e) -> Q.real q = from_int n *. pow2r e
940
| None -> true end }
941
= let z = Q.to_zarith q in
942
{proof…} Q.num_den q; {qed}
943
let k = Zbit.trailing_zeros z.ZQ.den in
944
if z.ZQ.den = lsl_int 1 k then begin
945
{proof…}
946
Zbit.lsl_mul 1 k;
947
assert { pow2r (-k) = 1.0 /. from_int (power 2 k) };
948
assert { from_int z.ZQ.num /. from_int z.ZQ.den
949
= from_int z.ZQ.num *. (1.0 /. from_int (power 2 k)) };
950
{qed}
951
Some (z.ZQ.num, -k)
952
end else None

q as the fraction n / d in lowest terms, 0 < d

  Valid (42ms) (colibri2)
955
let
num_den
(q: Q.t) : (int, int)
956
returns { (n, d) -> n = Q.num q /\ d = Q.den q /\ 0 < d /\
957
Q.real q = from_int n /. from_int d }
958
= let z = Q.to_zarith q in
959
{proof…} Q.num_den q; {qed}
960
(z.ZQ.num, z.ZQ.den)

The numerator or the denominator of q in lowest terms is at least 2^k

  Valid (404ms) (cvc5)
964
let
big
(k: int) (q: Q.t) : bool
965
requires { 0 <= k }
966
ensures { result <-> power 2 k <= abs (Q.num q) \/ power 2 k <= Q.den q }
967
= let z = Q.to_zarith q in
968
{proof…}
969
Q.num_den q;
970
Zbit.numbits_lsl k; Zbit.lsl_mul 1 k;
971
let lemma bits (n: int) : unit
972
requires { 0 <= n }
973
ensures { Zbit.numbits n > k <-> power 2 k <= n }
974
= if pure { power 2 k <= n } then Zbit.numbits_ge_pos (power 2 k) n
975
else if pure { Zbit.numbits n > k } then begin
976
Zbit.numbits_lt_lsl n k; absurd
977
end in
978
bits (abs z.ZQ.num); bits z.ZQ.den;
979
{qed}
980
Zbit.numbits (abs z.ZQ.num) > k || Zbit.numbits z.ZQ.den > k
981
end